当前位置：首页 > news >正文

8.23CF训练题解

news 来源：原创 2024/9/20 13:42:44

A题Painting the Ribbon题解
其实这是一个经典的数学思维题，飘带有N段，每段可以着色，有M种颜色可以选择，另一个人有K次修改颜色的机会，问有没有方式使得飘带在K次修改后都无法变为单一颜色？

其实最简单的方法就是1–M颜色以此涂色，这样子各种颜色出现的又多又均衡，那么另一个人只能选择最多的一种颜色作为最终颜色，其他颜色全部修改。经过计算可以知道最多的那种颜色会有
N/M向上取整个，所以需要N- 向上取整(N/M)次机会才能变为单一颜色

#include<bits/stdc++.h>
using namespace std;
int main() {int a;cin>>a;for(int i=1;i<=a;i++){int n,m,k;int d=1;int s=0;cin>>n>>m>>k;d=n-(n/m);if(n%m!=0){d--;}if(d<=k){cout<<"NO";}else{cout<<"YES";}cout<<endl;}return 0;
}

B - Special Characters
简单题，按题目意思构造即可

#include<bits/stdc++.h>
using namespace std;
int main() {int a;cin>>a;for(int i=1;i<=a;i++){int b;cin>>b;int c=0;if(b%2==1){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;while(c!=b/2){if(c%2==1){cout<<"BB";}else{cout<<"AA";}c++;}cout<<endl;}}return 0;
}

C题题解
注意一开始给我们的就是美丽的数组，说明它能够最终变为一样的
我们根据题目的规则来思考，能变成最终一样的，一定能得到首元素跟末尾元素是相同的结论
因此我们的删除方式可以有以下方法:
1 删除开头一段连续的A[1]长度
2 删除末尾一段连续的A[1]长度
3 寻找两个不等于A1的值，删除他们中间的所有数字
以上三种方式都可以让数组变得不美丽求最短即可

#include<bits/stdc++.h>
using namespace std;
int A[300010];
int main() {int a;cin>>a;for(int i=1;i<=a;i++){int b;cin>>b;int len=0;int x=1e9;for(int j=1;j<=b;j++){cin>>A[j];if(A[j]==A[1]){len++;}else{x=min(x,len);len=0;}}x=min(x,len);if(x==b){cout<<"-1"<<endl;}else{cout<<x<<endl;}}return 0;
}

D题题解
每个数字其实要么拆，要么不拆
我们考虑倒着处理，先把A[n]存进去，不拆，因为A[n]是最后一个元素，不拆它相当于后方有个较大的。对于每个数字，如果A[i]< 上一次存的数，那么我们不拆直接放进去，否则就正常拆掉，最终检查是不是按顺序来的

#include<bits/stdc++.h>
using namespace std;
int A[100];
int B[1000];
int main() {int a;cin>>a;for(int i=1;i<=a;i++){int b;cin>>b;for(int j=1;j<=b;j++){cin>>A[j];}int len=0;B[++len]=A[b];for(int j=b-1;j>=1;j--){if(A[j]<=B[len]){B[++len]=A[j];}else{B[++len]=A[j]%10;B[++len]=A[j]/10%10;}}int c;bool ok=true;for(int j=2;j<=len;j++){c=B[j-1];if(c<B[j]){cout<<"NO"<<endl;ok=false;break;}}if(ok==true){cout<<"YES"<<endl;}}return 0;
}

E题题解

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
const int N=2e5+5;
char a[N],b[N];
int T;
int main(){cin>>T;while(T--){cin>>a>>b;int lena=strlen(a);int lenb=strlen(b);int op=0;for( int i=0;i<lena;i++ ){if(op==0){if(a[i]<b[i]) swap(a[i],b[i]);if(a[i]>b[i]) op=1;}else if(op==1){if(a[i]>b[i]) swap(a[i],b[i]);}}cout<<a<<'\n'<<b<<'\n';}return 0;
}

F题题解
模拟题，按题目意思写就行了控制好坐标位置

#include<bits/stdc++.h>
using namespace std;
int n;char s[2][200010];
void Main(){cin>>n;scanf("%s%s",s[0]+1,s[1]+1);int f=0;for(int i=2;i<=n;i+=2)if(s[0][i]=='<'&&(s[1][i-1]=='<'||i<n-1&&s[1][i+1]=='<')){f=1;break;}if(f)cout<<"NO\n";else cout<<"YES\n";
}signed main(){int T;cin>>T;while(T--)Main();return 0;
}