2024年4月赛丙组

T1：最大公因数

数论
模板题，辗转相除法。

#include<bits/stdc++.h>  
using namespace std;  
int x,y;  
int main()  
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin>>x>>y;  
    while(x%y!=0)  
    {  
        int r = x % y;  
        x = y;  
        y = r;  
    }  
    cout<<y<<endl;  
        return 0;  
}

T2：子序列的判定

模拟
想象成两根手指分别指向字符串$P$和$t$的第一个字符，然后比对，如果相等，则两根手指都往后移动一个位置；如果不同，则指向$t$的手指往后移动一个位置，然后继续比对当前指向的字符。
扫描结束后，如果指向$P$的手指扫描完字符串$P$，则说明能在$t$中找到$P$的子序列，反之则表示不能。
时间复杂度为$O(|t|)$，$|t|$表示字符串$t$的长度。

#include<bits/stdc++.h>  
using namespace std;  
string p,t;  
int main()  
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin>>p>>t;  
    int j = 0;  //j表示指向p的手指
    for(int i = 0; i < t.size(); i++){  //i表示指向t的手指
        if(j<p.size() && t[i]==p[j]) j++;  
    }  
    if(j==p.size()) cout<<"Yes";  
    else cout<<"No";  
        return 0;  
}

T3：交换的次数

递推+模拟
题意要求$0$移到前面，$1$移到后面，实际交换的时候，只考虑$0$或$1$就可以了。
这里，我假设目标是所有的$0$，那么对$0$而言，左边$1$的个数，就是它会经过的次数，也是交换的次数。所以，先把$0$左边$1$的个数统计出来，然后把所有$0$应该交换的次数累加即可，时间复杂度$O(|s|)$。

#include<bits/stdc++.h>  
using namespace std;  
const int MX = 3e5+5;  
string s;  
long long f[MX],ans;  
int main()  
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin>>s;  
    int n = s.size();  
    s = ' ' + s;  
    for(int i = 1; i <= n; i++)  //递推求出从左往右1的个数
        if(s[i]=='1') f[i] = f[i-1] + 1;  //如果1，则个数加1
        else f[i] = f[i-1];  //如果0，传递前面1的个数
    for(int i = 1; i <= n; i++)  
        if(s[i]=='0') ans += f[i];  //累加1的个数，即交换次数
    cout<<ans;  
    return 0;  
}

T4：排序分数

快排
题目一看就很明显要根据分数值排序，所以可以设计一个结构体，用来储存分子、分母和分数值，然后按分数值从小到大排序。

struct node{  
    double x;  //分数值
    int fz,fm;  //分子和分母
    bool operator < (const node& rhs) const{  
        return x < rhs.x;  //按分数值从小到大排序
    }  
}a[150000];

数组的到小如何计算？当$\mathrm{分}\mathrm{母}=1$的时候，$0$个真分数；$\mathrm{分}\mathrm{母}=2$的时候，1个真分数；$\mathrm{分}\mathrm{母}=3$的时候，2个真分数...当$\mathrm{分}\mathrm{母}=500$的时候，$499$个真分数。
所以当$n=500$的时候，真分数个数为$1+2+3...+499=(1+499)\ast 499/2=124750$。
题目还有一个限制，要求是最简分数，所以要用$T1$的最大公因数算法，用来判断是否最简分数。

#include<bits/stdc++.h>  
using namespace std;  
struct node{  
    double x;  
    int fz,fm;  
    bool operator < (const node& rhs) const{  
        return x < rhs.x;  
    }  
}a[150000];  
int gcd(int x, int y)  
{  
    while(x%y!=0)  
    {  
        int r = x % y;  
        x = y;  
        y = r;  
    }  
    return y;  
}  
int n,m;  
int main()  
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin>>n;  
    for(int i = 2; i <= n; i++){  
        for(int j = 1; j < i; j++){  
            if(gcd(i,j)==1){  //最大公因数1，表示最简分数
                m++;  
                a[m].x = j*1.0/i;  
                a[m].fz = j;  
                a[m].fm = i;  
            }  
        }  
    }  
    sort(a+1,a+1+m);  
    for(int i = 1; i <= m; i++)  
        cout<<a[i].fz<<"/"<<a[i].fm<<"\n";  
    return 0;  
}

T5：数字迷宫

BFS宽搜
差不多是模板题了，只不过移动步数计算上变一下即可。

#include<bits/stdc++.h>  
using namespace std;  
const int MX = 1005;  
struct node{  
    int x,y,s;  //坐标和步数
};  
int n,m,a[MX][MX];  
int dx[]={1,-1,0,0};  
int dy[]={0,0,1,-1};  
bool v[MX][MX];  //记号数组，也可以不使用，走过的地方标为0即可
queue<node> q;  
int main()  
{  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin>>n>>m;  
    for(int i = 1; i <= n; i++)  
        for(int j = 1; j <= m; j++)  
            cin>>a[i][j];  
    v[1][1] = 1;  
    q.push({1,1,0});  
    while(q.size()){  
        int x = q.front().x;  
        int y = q.front().y;  
        int s = q.front().s;  
        q.pop();  
        if(x==n && y==m){  
            cout<<s<<endl;  
            return 0;  
        }  
        for(int i = 0;i < 4; i++){  
            int tx = x + dx[i] * a[x][y];  
            int ty = y + dy[i] * a[x][y];  
            if(tx > 0 && tx <= n && ty > 0 && ty <= m && v[tx][ty]==0){  
                v[tx][ty] = 1;  
                q.push({tx,ty,s+1});  
            }  
        }  
    }  
    cout<<"No Solution"<<endl;  
    return 0;  
}