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

寒假集训思维训练5题解

article 2025/2/12 11:45:31

A - Full House 2
简单来说就是判断题，可以用讨论，也可以用数组来统计再枚举

#include<bits/stdc++.h>
using namespace std;
int vis[20];
int main() {
	int x;
	for(int i=1;i<=4;i++){
		cin>>x;
		vis[x]++;
	}
	//3     2   - >  3   1       2   2
	for(int i=1;i<=13;i++){
		for(int j=1;j<=13;j++){
			if(i==j)continue;
			if(vis[i]==3&&vis[j]==1||vis[i]==2&&vis[j]==2){
				cout<<"Yes";return 0;
			}
		}
	}
	cout<<"No";
	return 0;
}

B - Calculator
注意判断 $00$ 的情况就行了，如果是 $00$ 记得要跳过一个0的位置。

#include<bits/stdc++.h>
using namespace std;
char s[1010];
int main() {
	cin>>s+1;
	int n=strlen(s+1);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(s[i]!='0')ans++;
		else {
			if(s[i+1]=='0'){
				i++;
				ans++;
			}
			else{
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

C - Operate 1
仔细想想，如果两个字符串长度的差大于等于2，那么一定无解
如果两个字符串长度一样，我们可以依次枚举每个位置的字符来检查，看看是否至多只有一个位置不一样，因为如果有一个位置不一样，我们可以修改。

如果 $S$ 的长度刚刚是 $T 的长度 + 1$ ，我们可以考虑S当中删除一个
假设 $S$ 字符串 $[1 到 l e n]$ 我们还是去做匹配，当遇到一个位置 $x$ 满足 $S [x]! = T [x]$ 接下来考虑删除 $S [x]$ ，那么接下来就要由 $S [x + 1] 去匹配 T [x]$ ; $S [x + 2] 去匹配 T [x + 1]$ ; $S [x + 3] 去匹配 T [x + 2]$ ;以此类推，所以同学们只需要写另一个循环来枚举就行了。

如果S的长度比T短1，实际上插入我们是不好思考的，因为不知道在哪里插入。我们可以反向思考，S插入一个相当于T删除一个，那么问题变为了检查T字符串删除一个能不能变为S字符串，用上面的方法就行了

#include<bits/stdc++.h>
using namespace std;
char s[500010];
char t[500010];
int main() {
	int k;
	cin>>k;
	cin>>s+1;
	cin>>t+1;
	int n=strlen(s+1);
	int m=strlen(t+1);
	if(abs(m-n)>1){
		cout<<"No";
		return 0;
	}
	if(n==m){
		//长度一样但是字符串不一样
		int op=0;//修改次数 
		for(int i=1;i<=n;i++){
			if(s[i]!=t[i]){
				op++;
			}
		} 
		if(op<=1){
			cout<<"Yes";return 0;
		}
		else {
			cout<<"No";return 0;
		}
	}
	if(n==m+1){
		//只能考虑删一个  
		int pos;
		for(int i=1;i<=n;i++){
			if(s[i]!=t[i]){
				pos=i;break;
			}
		}
		for(int i=pos+1,j=pos;i<=n;i++,j++){
			if(s[i]!=t[j]){
				cout<<"No";return 0;
			}
		} 
		cout<<"Yes";return 0;
	}
	if(n==m-1){
		//只能考虑插入一个  等价于T串删除一个位置 
		int pos;
		for(int i=1;i<=m;i++){
			if(s[i]!=t[i]){
				pos=i;break;
			}
		}
		for(int i=pos+1,j=pos;i<=m;i++,j++){
			if(s[j]!=t[i]){
				cout<<"No";return 0;
			}
		} 
		cout<<"Yes";return 0;
	}
	return 0;
}

D - Equally
其实那么三个数一样，要么把两个小一点的放在一块，来检查。所以排序就行了

#include<bits/stdc++.h>
using namespace std;
int A[5];
int main() {
	for(int i=1;i<=3;i++){
		cin>>A[i];
	}
	sort(A+1,A+1+3);
	if(A[1]==A[3]||A[1]+A[2]==A[3]){
		cout<<"Yes";
	}
	else{
		cout<< "No";
	}
	return 0;
}

E - Santa Claus 1
这个问题简单来说就是，你控制的人在 $(x, y)$ 位置，接下来有一系列指令 $T$ 字符串，你要按指令去走格子，吃糖果(我视为@ 是糖果，吃了之后修改为 . 点)
注意不要越界

#include<bits/stdc++.h>
using namespace std;
char s[110][110];
char T[10010];
int main() {
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++){
		cin>>s[i]+1;
	}
	cin>>T+1;
	int len=strlen(T+1);
	int ans=0;
	for(int i=1;i<=len;i++){
		if(T[i]=='U'){
			if(s[x-1][y]=='.'||s[x-1][y]=='@'){
				x--;
				if(s[x][y]=='@'){
					ans++;
					s[x][y]='.';
				}
			}
		}
		else if(T[i]=='D'){
			if(s[x+1][y]=='.'||s[x+1][y]=='@'){
				x++;
				if(s[x][y]=='@'){
					ans++;
					s[x][y]='.';
				}
			}
		}
		if(T[i]=='L'){
			if(s[x][y-1]=='.'||s[x][y-1]=='@'){
				y--;
				if(s[x][y]=='@'){
					ans++;
					s[x][y]='.';
				}
			}
		}
		if(T[i]=='R'){
			if(s[x][y+1]=='.'||s[x][y+1]=='@'){
				y++;
				if(s[x][y]=='@'){
					ans++;
					s[x][y]='.';
				}
			}
		}
	}
	cout<<x<<" "<<y<<" "<<ans;
	return 0;
}

F - Illuminate Buildings
其实，我们可以来枚举从哪个灯开始，接下来依次枚举间隔，来检查最大值就行了

即我先枚举从第 $i$ 个灯开始，接下来 $i 到 N$ 的灯都有可能选，接下来枚举间隔 $j = 1, 2, 3... (n - i)$
来检查每间隔 $j$ ，是不是还是第 $i$ 个灯一样的灯最后保留最大值

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int h[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>h[i];
	int ans=1;
	for(int t=1;t<=n;t++){//暴力枚举间隔
		for(int i=1;i<=t;i++){
			int sum=0;
			for(int j=i;j<=n;j+=t){
				ans=max(ans,sum);
				if(j==i||h[j]==h[j-t])sum++;
				else sum=1;
				ans=max(ans,sum);
			}//求出最长的合法序列
		}
	}
	cout<<ans<<"\n";
}

G题H题不讲了

I - Perfect Standings
题目是这样子的，一场比赛有 $A, B, C, D, E$ 五道题，每道题的分数给我们了
题目想让我们输出，在所有的解题情况当中，前31名的做题情况。
即先按做题得到的总分排序，如果总分一样的两个人，按做题的题目编号来排序，类似于如果小明做了ABC题得分跟小刚做了BCD题一样，那么按字典序来排序的话(字典序指的是，两个字符串从前往后做比较，谁第一次比另一个小了，谁的字典序就更小)。按字典序排序，应该先输出小明的做题情况ABC，再输出BCD。

所以这个题首先我们得记录所有可能的做题情况，即对于5道题目，所有的做题可能，都要枚举出来，存下来。

如何枚举5道题目的做题情况呢? 可以考虑0，1 其中0表示没做出来
具体枚举方式请看下面代码。我分别用 $i, j, k, p, q 的值表示第 12345 道题目有没有解决$
然后来计算分数，统计到结构体里面，顺便记录一下这个人每道题的做题情况，即 $A [i] = 1 表示第 i 个题做出来了$

#include<bits/stdc++.h>
using namespace std;
struct node{
	int solve[6];
	int fen;
}A[50];
int B[10];
bool cmp(node x,node y){
	if(x.fen==y.fen){
		for(int i=1;i<=5;i++){
			if(x.solve[i]!=y.solve[i])return x.solve[i]>y.solve[i];
		}		
	}
	return x.fen>y.fen;
}
int main() {
	for(int i=1;i<=32;i++){
		for(int j=1;j<=5;j++){
			A[i].solve[j]=0;
			A[i].fen=0;
		}
	}
	for(int i=1;i<=5;i++){
		cin>>B[i];	
	}
	int num=0;
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			for(int k=0;k<=1;k++){
				for(int p=0;p<=1;p++){
					for(int q=0;q<=1;q++){
					num++;// num记录  哪一种做题情况 
					A[num].solve[1]=i;
					A[num].solve[2]=j;
					A[num].solve[3]=k;
					A[num].solve[4]=p;
					A[num].solve[5]=q;// solve[5] 表示第5个题的做题情况 
					for(int w=1;w<=5;w++){
						A[num].fen+=B[w]*A[num].solve[w];//计算当前这个情况的总分
						//B数组对应的是第w道题的分数
						//solve[w] 对应第w道题 当前有没有做出来
						//没做出来就是0去做乘法，所以拿不到这个题的分数  
					}	
							
					}
				}
			}
		}
	}
	sort(A+1,A+1+33,cmp);// 排序    注意要写好排序函数   分数一样的情况  
	for(int i=1;i<=31;i++){ //输出前31名的做题情况 
		for(int j=1;j<=5;j++){// 枚举当前这个人做了哪些题，按字母输出   
			if(A[i].solve[j]==1){ //检查当前这个人 第j道题有没有做出来   
				cout<<char('A'+j-1);
			}
		}
		cout<<'\n';
	}
	return 0;
}