ACGO欢乐赛#52 全题解

复仇者_零

2025-07-27 22:00:02

发布于：浙江

51阅读

0回复

0点赞

T1.修改数字

思路分析：判断给定的三个数中，有多少个位置与目标序列 1 2 3 不同。若不同位置不超过 1 个，则最多一次修改能变为目标序列，输出 YES，否则输出 NO。

$时间复杂度：O(1)$
$空间复杂度：O(1)$

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
    cin>>a>>b>>c;
    if(a==1&&b==2&&c==3){
        cout<<"YES";
        return 0;
    }
    int t=0;
    if(a!=1)t++;
    if(b!=2)t++;
    if(c!=3)t++;
    if(t<=1)cout<<"YES";
    else cout<<"NO";
    return 0;
}

T2.小明的非递减数组

思路分析：从左到右遍历数组，若当前元素 a[i] 小于前一个元素 a[i-1]，说明需要将其增加到 a[i-1]，操作次数为 a[i-1] - a[i]，累加即为总操作次数。

$时间复杂度：O(n)$
$空间复杂度：O(1)【不考虑输入数组占用】$

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i]<a[i-1]){
            s+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    cout<<s;
    return 0;
}

T3.小明和视疲劳

思路分析：将两个字符串逐字符转为小写后比较，若每一位都相同则视为“小明看起来一样”，否则输出 NO。

$时间复杂度：O(n)$
$空间复杂度：O(1)【不开新空间，仅字符比较】$

#include<bits/stdc++.h>
using namespace std;
string s,t;
int main(){
	getline(cin,s);
	getline(cin,t);
	if(s.size()!=t.size()){
		cout<<"NO";
		return 0;
	}
	for(int i=0;i<s.size();i++){
		if(tolower(s[i])!=tolower(t[i])){
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

T4.卡牌

思路分析：为使总和最大，应优先选取数值高的卡牌（从 4 到 1）。依次取尽可能多的 4、3、2、1，直到选满 k 张卡牌为止。

$时间复杂度：O(1)$
$空间复杂度：O(1)$

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,k;
int main(){
    cin>>a>>b>>c>>d>>k;
    int s=0;
    int t=min(d,k);
    s+=4*t;
    k-=t;
    t=min(c,k);
    s+=3*t;
    k-=t;
    t=min(b,k);
    s+=2*t;
    k-=t;
    t=min(a,k);
    s+=1*t;
    cout<<s;
    return 0;
}

T5.小明和九宫格

思路分析：在原矩阵中枚举所有可能的 3×3 子矩阵，逐个与目标九宫格进行比对，若有一处完全匹配则输出 YES，否则输出 NO。

$时间复杂度：O((n−2)×(m−2)×9) ≈ O(n × m)$
$空间复杂度：O(n × m)【存储输入矩】$

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005],b[3][3];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin>>b[i][j];
    for(int i=0;i<=n-3;i++)
        for(int j=0;j<=m-3;j++){
            int f=1;
            for(int x=0;x<3;x++)
                for(int y=0;y<3;y++)
                    if(a[i+x][j+y]!=b[x][y])
                        f=0;
            if(f){
                cout<<"YES";
                return 0;
            }
        }
    cout<<"NO";
    return 0;
}

T6.进制转换

思路分析：将 a 和 b 转换为 r 进制字符串，数字 ≥10 用 A-Z 表示，然后直接比较两个字符串的字典序，输出较大的一个。

$时间复杂度：$ $O(\log_r a + \log_r b)$
$空间复杂度：$ $O(\log_r a + \log_r b)$

#include<bits/stdc++.h>
using namespace std;
int a,b,r;
string f(int x){
    string s;
    while(x){
        int t=x%r;
        if(t<10)s+=t+'0';
        else s+=t-10+'A';
        x/=r;
    }
    reverse(s.begin(),s.end());
    return s.empty()?"0":s;
}
int main(){
    cin>>a>>b>>r;
    string s1=f(a),s2=f(b);
    cout<<(s1>s2?s1:s2);
    return 0;
}