算法基础50题模拟题单 | 123hh2 = Keep moving forward

题单链接

JC0101. Suffix Three

题目大意

给出 $n$ 个字符串，根据字符串结尾输出每个字符串对应的语言

思路

纯模拟

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
signed main()
{
    int n=read();
    while(n-->0)
    {
        string awa;
        cin>>awa;
        int l=awa.length();
        if(awa[l-1]=='o') puts("FILIPINO");
        if(awa[l-1]=='u') puts("JAPANESE");
        if(awa[l-1]=='a') puts("KOREAN");
    }
    return _123hh2;
}

JC0102. Dreamoon and Ranking Collection

题目大意

给出 $n$ 个数和 $x$ 次添数操作，求添完 $x$ 个数后使得整数数列 $1到n$ 的 $n$ 最大

思路

从小往大填空缺的数，模拟

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=205;
int awa[maxn];
void init() {for(int i=1;i<=200;i++) awa[i]=0;}
signed main()
{
    int t=read();
    while(t-->0)
    {
        init();
        int n=read(),x=read(),ans=0;
        for(int i=1;i<=n;i++) awa[read()]=1;
        for(int i=1;i<=200,x;i++)
        {
            if(!awa[i]) x--,awa[i]=1;
        }
        for(int i=1;i<=201;i++) if(!awa[i]) {ans=i-1;break;}
        write(ans),puts("");
    }
    return _123hh2;
}

JC0103. Symmetric Matrix

题目大意

给定 $n$ 种22大小的矩阵，问是否能用以上任意种矩阵填满大小为 $m m$ 的矩阵使得该矩阵 $s$ 满足 $s[i][j]=s[j][i]$

思路

模拟填矩阵，发现填完之后的大矩阵是关于从左上到右下的斜对角线对称的，将这个对称性转移到每个小矩阵上可以看出小矩阵必须满足和大矩阵一样的对称性质，所以我们只需要找到一个这样的小矩阵就能构造出一个满足条件的大矩阵

显然，当m为奇数时无解

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),m=read(),f=0;
        for(int i=1;i<=n;i++)
        {
            int a=read(),b=read(),c=read(),d=read();
            if(b==c) f=1;
        }
        if(f&&m%2==0) puts("YES");
        else puts("NO");
    }
    return _123hh2;
}

JC0104. Happy Birthday, Polycarp!

题目大意

求 $[1,n]$ 中每位数字都相同的数的个数

思路

一眼模拟，发现对于不管几位数，都有 $9$ 种每位数字都相同的数，所以答案为 $n$ 的位数所对应的每位数字都相同的个数加上剩下位数的个数*9即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
int solve(int x)
{
    int awa=0,ws=0,now=x;
    while(x) x/=10,ws++,awa=awa*10+1;
    return (ws-1)*9+now/awa;
}
signed main()
{
    int t=read();
    while(t-->0) write(solve(read())),puts("");
    return _123hh2;
}

JC0105. A New Technique

题目大意

有一个 $n * m$ 的矩阵，给出从左到右每一行元素和从上到下每一列的元素，但是行和列的顺序不一样，求原矩阵，保证每个元素都不一样

思路

既然每个元素都不一样，我们知道在某一行的元素所在的列数一定是确定的，在某一列的元素所在的行数也是一定确定的，我们可以由此来还原原矩阵

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=5e2+1;
int awa[maxn][maxn];
map<int,int> qwq;
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),m=read();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int x=read();
                qwq[x]=j;
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int x=read();
                awa[j][qwq[x]]=x;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cout<<awa[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    return _123hh2;
}

JC0106. Reachable Numbers

题目大意

给你一个函数 $f(x)$，作用为将 $x+1$ 后，去掉末尾的所有0，现在给定一个数 $n$，求对 $n$ 进行多次 $f(n)$ 操作所能得到多少不同的数，包括 $n$ 自己

思路

不难发现，对于给定的数 $n$，我们最多操作次数不超过 $n$ 的位数*8+3，所以我们可以不带脑子大胆模拟

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
int solve(int x)
{
    map<int,bool> awa;
    awa[x]=1;x++;
    while(x)
    {
        if(x%10==0) {x/=10;continue;}
        if(awa.find(x)==awa.end()) awa[x]=1;
        else break;
        x++;
    }
    return awa.size();
}
signed main()
{
    write(solve(read())),puts("");
    return _123hh2;
}

JC0107. Collecting Packages

题目大意

给出平面直角坐标系上的 $n$ 个坐标，要求你从原点出发，在每次移动只能向上或向右移动一个单位长度的情况下是否能经过给出的所有坐标

思路

先对给出的坐标按 $x$ 轴从小到大排序，$y$ 轴也从小到大排序，然后优先向右移动，再向上移动，如果我们发现原先经过的最大 $y$ 值大于当前 $y$ 值时，则无解

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e3+1;
struct A {int x,y;}awa[maxn];
bool cmp(A x,A y)
{
    if(x.x==y.x) return x.y<y.y;
    else return x.x<y.x;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),x=0,y=0,f=0;string qwq="";
        for(int i=1;i<=n;i++) awa[i].x=read(),awa[i].y=read();
        sort(awa+1,awa+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            while(x<awa[i].x) qwq+='R',x++;
            if(awa[i].y<y) {f=1;break;}
            while(y<awa[i].y) qwq+='U',y++;
        }
        if(f) {puts("NO");continue;}
        puts("YES");cout<<qwq<<endl;
    }
    return _123hh2;
}

JC0108. Yet Another Crosses Problem

题目大意

给定一个矩阵，矩阵有白有黑，求至少将几个白格子涂成黑色才能使某一行某一列全为黑

思路

模拟，找出每行每列的最少白色块数，当所涂的格子包含在所需要的行和列之中，答案要减去1

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=5e5+1;
int awa[maxn],qwq[maxn];
string a[maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),m=read(),ans=1e9;
        for(int i=1;i<=n;i++) awa[i]=0;
        for(int i=1;i<=m;i++) qwq[i]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            for(int j=1;j<=m;j++)
            {
                if(a[i][j-1]=='.') awa[i]++,qwq[j]++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans=min(ans,awa[i]+qwq[j]-(a[i][j-1]=='.'?1:0));
            }
        }
        write(ans),puts("");
    }
    return _123hh2;
}

JC0109. RGB Substring (easy version)

题目大意

给定一个长为 $n$ 的字符串，你有 $q$ 次修改机会，每次可以修改字符串中任意一个字符，问至少进行多少次修改操作才能使这个字符串的某一子串是字符串 $RGBRGB……$ 的某一字串且长度大于 $k$

思路

$n$ 的范围很小，想什么算法，直接上字符串暴力匹配

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),k=read(),ans=1e8;
        string awa;cin>>awa;int l=awa.size();
        for(int i=0;i<=l-k;i++)
        {
            int cnt=0;char x='R';
            for(int j=i;j<i+k;j++)
            {
                if(awa[j]!=x) cnt++;
                if(x=='R') {x='G';continue;}
                if(x=='G') {x='B';continue;}
                if(x=='B') {x='R';continue;}
            }
            ans=min(ans,cnt),cnt=0,x='G';
            for(int j=i;j<i+k;j++)
            {
                if(awa[j]!=x) cnt++;
                if(x=='R') {x='G';continue;}
                if(x=='G') {x='B';continue;}
                if(x=='B') {x='R';continue;}
            }
            ans=min(ans,cnt),cnt=0,x='B';
            for(int j=i;j<i+k;j++)
            {
                if(awa[j]!=x) cnt++;
                if(x=='R') {x='G';continue;}
                if(x=='G') {x='B';continue;}
                if(x=='B') {x='R';continue;}
            }
            ans=min(ans,cnt);
        }
        write(ans),puts("");
    }
    return _123hh2;
}

JC0110. System Testing

题目大意

有 $n$ 份代码，评测姬可以同时评测 $k$ 份代码，第 $i$ 份代码的测试点数量为 $a_i$，每个测试点评测需要1秒钟，定义 $d = \lfloor \frac{100m}{n}+0.5 \rfloor$，$m$ 是已经评测完的*代码数量，统计若某代码正在评测第 $p$ 个评测点且 $p=d$ 的数量

思路

直接模拟，暴力枚举每一秒，复杂度 $O(a \frac{n^2}{k})$，最多 $1.5*10^8$，CF神机能过~~CCF就不一定了~~

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e3+1;
int awa[maxn],qwq[maxn];
bool a[maxn],b[maxn];
signed main()
{
    int n=read(),k=read(),m=0,now=0,ans=0,sum=0;
    for(int i=1;i<=n;i++) awa[i]=read(),sum+=awa[i];
    now=k;
    for(int i=1;i<=sum;i++)
    {
        int newadd=0,d=floor((100.0*m)/n+0.5);
        for(int j=1;j<=min(now,n);j++)
        {
            if(!a[j]&&!b[j]&&i-qwq[j]==d) ans++,b[j]=1;
            if(i-qwq[j]==awa[j]) newadd++,a[j]=1;
        }
        m+=newadd,now+=newadd;
        for(int j=1;j<=min(now,n);j++) if(!qwq[j]&&j>k) qwq[j]=i;
    }
    write(ans),puts("");
    return _123hh2;
}

JC0111. Busy Robot

题目大意

你有一个初始位置在数轴原点上的机器人，每秒他能移动一个单位长度

给定 $n$ 条指令，每个指令的格式为在第 $t_i$ 秒移动到 $x_i$，如果下达指令时机器人在移动，指令无效

定义当且仅当第 $[ti,t{i+1}]$ 秒内机器人到达过 $x_i$，求有多少指令是有效的

注意： $t_{i+1}$ 设为正无穷

思路

题中数据让我们放弃了暴力枚举秒数的想法，但是我们可以维护

机器人停止移动的时间
机器人收到指令的时刻
机器人开始移动的位置
机器人停止移动的位置

我们遍历指令，若当前读到的 $t_i$ 大于等于我们维护的机器人停止移动的时间，说明我们可以执行这条指令并更新以上维护的四种状态，边读入指令边统计答案即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e5+10;
int awa[maxn],qwq[maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read();awa[n+1]=1e10;
        int nexttime=0,lasttime=0,st=0,ed=0,ans=0;
        for(int i=1;i<=n;i++) awa[i]=read(),qwq[i]=read();
        for(int i=1;i<=n;i++)
        {
            if(awa[i]>=nexttime)
            {
                nexttime=awa[i]+abs(qwq[i]-ed);
                lasttime=i,st=ed,ed=qwq[i];
                if(awa[i+1]>=nexttime) ans++;
            }
            else
            {
                int l=st-(st>=ed?1:-1)*(awa[i]-awa[lasttime]);
                int r=(st>=ed?max(ed,st+awa[lasttime]-awa[i+1]):min(ed,st+awa[i+1]-awa[lasttime]));
                if(l>r) swap(l,r);
                if(qwq[i]>=l&&qwq[i]<=r) ans++;
            }
        }
        write(ans),puts("");
    }
    return _123hh2;
}

判断指令有效的条件看起来繁琐，实际上只是针对机器人向左/向右走进行一个判断，然后给出目标时间段机器人走过的路径的做右端点然后再进行判断就可以了

JC0112. 神奇的幻方

题目大意

给一个数 $n$，构造一个 $n*n$ 的矩阵使每行每列及两对角线上的数字之和均相同

思路

题目直接给出了构造方法，按构造方法模拟即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=51;
int awa[maxn][maxn];
signed main()
{
    int n=read(),x=1,y=n/2+1;awa[x][y]=1;
    for(int i=2;i<=n*n;i++)
    {
        if(x==1&&y!=n) x=n,y++;
        else if(y==n&&x!=1) y=1,x--;
        else if(x==1&&y==n) x++;
        else if(!awa[x-1][y+1]) x--,y++;
        else x++;
        awa[x][y]=i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<awa[i][j]<<" ";
        }
        cout<<endl;
    }
    return _123hh2;
}

JC0113. 时间复杂度

题目大意

给出多个以 $F$ 或 $E$ 开头语句，$F \, x \, y \, z$ 表示 for(int x=y;x<=z;x++)，当 $z=n$ 是，该循环复杂度为 $O(n)$，$E$ 表示最近的一个循环结束，循环结构可以进行嵌套使复杂度更高，现给出若干语句和一个时间复杂度，问这些语句的复杂度是否与给出的时间复杂度一样

注意，当给出的语句有以下语法错误时，输出 $ERR$

$F和E$ 不匹配
新建的变量已经存在

思路

模拟，边读入语句边进行模拟，只有 $z=n \&\& y!=n$ 的情况下，该循环复杂度为$O(n)$，其余情况当作 $O(1)$ 处理，对于语法错误，我们判断 $F和E$ 的数量是否一样即可，新建变量可以用桶和单调栈记录

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e2+1;
bool tong[27],check[maxn],ok[maxn];
char zhan[maxn];
void init()
{
    for(int i=1;i<=26;i++) tong[i]=0;
    for(int i=1;i<=100;i++) zhan[i]=0,check[i]=0,ok[i]=0;
}
int pre(string qwq)
{
    char ch=qwq[4];int x=0,p=4;
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=qwq[++p];}
    return x;
}
int pre2(string qwq)
{
    char ch=qwq[0];int x=0,p=0;
    while(ch>='0'&&ch<='9'&&p<qwq.size()) {x=(x<<3)+(x<<1)+(ch^48);ch=qwq[++p];}
    return x;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        init();
        int n=read(),cnt=0,flg=0,ans=0,p=0,sum2=0;string awa;cin>>awa;
        while(n-->0)
        {
            string a,b,c,d;cin>>a;
            if(a[0]=='E')
            {
                if(cnt<0||flg) {flg=1;continue;}
                if(ok[p]) sum2--;check[p]=0,ok[p]=0;
                tong[zhan[p]-'a'+1]=0,p--,cnt--;
            }
            else
            {
                cin>>b>>c>>d;cnt++;
                if(tong[b[0]-'a'+1]) {flg=1;continue;}
                zhan[++p]=b[0],tong[b[0]-'a'+1]=1;
                if(c[0]!='n'&&d[0]=='n') check[p]=1,ok[p]=1,sum2++;
                else if((c[0]=='n'&&d[0]!='n')||pre2(c)>pre2(d)) continue;
                else ok[p]=1,sum2++;
                if(p==sum2)
                {
                    int sum1=0;
                    for(int i=1;i<=p;i++)
                    {
                        if(ok[i]) {if(check[i]) sum1++;}
                        else break;
                    }
                    ans=max(sum1,ans);
                }
            }
        }
        if(cnt||flg) puts("ERR");
        else
        {
            if(awa.size()==4)
            {
                if(!ans) puts("Yes");
                else puts("No");
            }
            else
            {
                if(pre(awa)==ans) puts("Yes");
                else puts("No");
            }
        }
    }
    return _123hh2;
}

后记：这道题不难，但是错了挺多次的~~还写了一堆冗余变量和函数~~，主要是没有注意题中没有说明的一些隐含条件，直接上去莽题了，越错越急，越急越错，以后还是要先通读题面，挖掘一下题面中的隐含条件，形成清晰的思路再动手

完结撒花

模拟

JC0101. Suffix Three

题目大意

思路

代码

JC0102. Dreamoon and Ranking Collection

题目大意

思路

代码

JC0103. Symmetric Matrix

题目大意

思路

代码

JC0104. Happy Birthday, Polycarp!

题目大意

思路

代码

JC0105. A New Technique

题目大意

思路

代码

JC0106. Reachable Numbers

题目大意

思路

代码

JC0107. Collecting Packages

题目大意

思路

代码

JC0108. Yet Another Crosses Problem

题目大意

思路

代码

JC0109. RGB Substring (easy version)

题目大意

思路

代码

JC0110. System Testing

题目大意

思路

JC0111. Busy Robot

题目大意

思路

代码

JC0112. 神奇的幻方

题目大意

思路

代码

JC0113. 时间复杂度

题目大意

思路

代码

浅谈珂朵莉树

CF1899E Queue Sort