CSPJ2024第二轮题目

附加题

题解

1.poker

#include<bits/stdc++.h>
using namespace std;
int n;
set<string> s; 
string str;
int main(){
	freopen("poker.in","r",stdin);
	freopen("poker.out","w",stdout);
	cin>>n;
	while(n--){
		cin>>str;
		s.insert(str);
	}
	cout<<52-s.size();//可以用数组，但本题可以最暴力的set去重 
	return 0;
}

2.explore

#include<bits/stdc++.h>
using namespace std;
const int maxn=1E3+10;
int t,n,m,k,x_,y_,d_;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int steps[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//steps[0]东1南2西3北 
int main(){
	freopen("explore.in","r",stdin);
	freopen("explore.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		cin>>x_>>y_>>d_;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				vis[i][j]=false;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>mp[i][j];
			}
		}
		vis[x_][y_]=true;
		int x=x_,y=y_,d=d_,ans=1;
		while(k--){//这题纯模拟死板机器人走路，可以走回头路的 
			x+=steps[d][0];
			y+=steps[d][1];
			if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]=='.'){//可行 
				if(!vis[x][y])
					ans++;
				vis[x][y]=true;
			}else{//不能走这一步，只能转方向
				x-=steps[d][0];
				y-=steps[d][1];
				d=(d+1)%4; 
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

3.sticks

打表？打表？

/*
打表找到规律，七个一组看。最明显的贪心就是尽量用8位数少 
1 -1
2 1
3 7
4 4
5 2
6 6
7 8
8 10
9 18
10 22
11 20
12 28
13 68
14 88
15 108
16 188
17 200
18 208
19 288
20 688
21 888
22 1088
23 1888
24 2008
25 2088
26 2888
27 6888
28 8888
29 10888
30 18888
31 20088
32 20888
33 28888
34 68888
35 88888
36 108888
37 188888
38 200888
39 208888
*/
//#include<bits/stdc++.h>
//using namespace std;
////         0,1,2,3,4,5,6,7,8,9
//int w[10]={6,2,5,5,4,5,6,3,7,6};
//int t,n;
//long long minn,num;
//void dfs(int use,int need,long long cur){//已经用了use根木棍，总共need根，从左往右拼了cur数 
//	if(use>need){
//		return; 
//	}else if(use==need){
//		minn=min(minn,cur);
//	}
//	if(cur!=0){//前导0和单0都不行 
//		dfs(use+w[0],need,cur*10+0);
//	}
//	for(int i=1;i<=9;i++){
//		dfs(use+w[i],need,cur*10+i);
//	}
//}
//int main(){
//	t=40,n=0;
//	while(t--){
////		cin>>n;
//		n++;
//		minn=LONG_MAX,num=0;
//		dfs(0,n,0);
//		cout<<n<<" ";
//		if(minn==LONG_MAX)
//			cout<<-1<<endl;
//		else
//			cout<<minn<<endl;
////		cout<<minn<<",";//打表初始化数组调试语句 
//	}
//	return 0;
//}

/*
#include<bits/stdc++.h>
using namespace std;
const int maxn=1E5+10;
//         0,1,2,3,4,5,6,7,8,9
int w[10]={6,2,5,5,4,5,6,3,7,6};
int ans[maxn]={-1,-1,1,7,4,2,6,8,10,18,22,20,28,68,88,108,188,200,208,288,688};
int t,n;
int main(){
	cin>>t; 
	while(t--){
		cin>>n;
		if(n<=20){
			cout<<ans[n]<<endl;
			continue;
		}
		int d=n/7;
		int m=n%7;
		if(m==0){
			while(d--){//这段代码是公用的
				cout<<'8';
			}
		}else if(m==1){
			cout<<"10";
			d-=1;
			while(d--){
				cout<<'8';
			}
		}else if(m==2){
			cout<<"1";
			while(d--){
				cout<<'8';
			}
		}else if(m==3){
			cout<<"200";
			d-=2;
			while(d--){
				cout<<'8';
			}
		}else if(m==4){
			cout<<"20";
			d-=1;
			while(d--){
				cout<<'8';
			}
		}else if(m==5){
			cout<<"2";
			while(d--){
				cout<<'8';
			}
		}else if(m==6){
			cout<<"6";
			while(d--){
				cout<<'8';
			}
		}
		cout<<endl;
	}
	return 0;
}
*/

//稍微压行（优化代码结构）
#include<iostream>
using namespace std;
const int maxn=1E5+10;
int w[10]={6,2,5,5,4,5,6,3,7,6};
int ans[maxn]={-1,-1,1,7,4,2,6,8,10,18,22,20,28,68,88,108,188,200,208,288,688};
int t,n;
int main(){
	freopen("sticks.in","r",stdin);
	freopen("sticks.out","w",stdout);
	cin>>t; 
	while(t--){
		cin>>n;
		if(n<=20){
			cout<<ans[n]<<endl;
			continue;
		}
		int d=n/7;
		int m=n%7;
		if(m==1){
			cout<<"10";
			d-=1;
		}else if(m==2){
			cout<<"1";
		}else if(m==3){
			cout<<"200";
			d-=2;
		}else if(m==4){
			cout<<"20";
			d-=1;
		}else if(m==5){
			cout<<"2";
		}else if(m==6){
			cout<<"6";
		}
		while(d--)
			cout<<'8';
		cout<<endl;
	}
	return 0;
}

4.chain很复杂啦

#include<bits/stdc++.h>
using namespace std;
const int maxs=2E5+10, maxr=1E2+10;
int T,n,k,q,r,c,maxs_value;
int dp[maxr][maxs];// r轮以c数字结尾可行？ 
int pre; 
int main(){
	ios::sync_with_stdio(false);//关同步synchronized
	cin.tie(0);//解绑输入，注意之后cin和scanf不要混用
	 freopen("chain.in","r",stdin);
	 freopen("chain.out","w",stdout);
	scanf("%d", &T);
	while(T--){
		scanf("%d%d%d", &n,&k,&q);
		int len; 
		vector<int> s[maxs];//开死的二维数组空间不够，要么一维加其他处理，要么用“变长数组”vector
		for(int p=1;p<=n;++p){//第p个person 
			scanf("%d", &len);
			int t;
			// s[p].clear();//天呐忘记测多组测试用例了，如果全局变量要清空历史vector!!!
			for(int ki=0;ki<len;++ki){// 第p个person的第ki个元素 
				scanf("%d", &t);
				s[p].emplace_back(t);//扔掉原元素的push_back
				maxs_value=max(maxs_value, t);
			}
		}
		for(int i=0;i<maxr;++i){
			for(int j=0;j<maxs;++j)	dp[i][j]=-1;
		}
		dp[0][1]=0;//dp第r=0轮以c=1轮结尾。-1不可行，0有多个人可选(只要有两个备选的话选另一个即可)，t>0只能是第t个人 
		for(r=1;r<maxr;++r){//轮次
			for(int p=1;p<=n;++p){//枚举人，第p个person  
				int c_st_index=-1;//对第p人枚举s选取的可行的连续序列， c_st是起点 
				for(int ki=0;ki<s[p].size();++ki){//枚举词库序列终点 
					c=s[p][ki]; 
					if(ki>=k&&(ki-k)==c_st_index){//当前枚举序列终点index为ki，若起点index为0则超过限定序列长度k 
						c_st_index=-1;//如果当前枚举序列起点c_st_index正好是超过k限制，则无效。由于窗口一步一步滑动的，所以如果有这种极端情况一定能枚举到。 
					}
					if(c_st_index!=-1){//前一轮以c_st结尾可行，且不是只能以当前第p人接龙 
						if(dp[r][c]==-1) 
							dp[r][c]=p;
						else if(dp[r][c]!=p)//一定要注意相邻两轮不能重复 
							dp[r][c]=0;
					} 
					if(dp[r-1][c]!=-1&&dp[r-1][c]!=p){//滑动接龙序列的起点，因为接龙序列长度[2,k]，所以正好先更新dp再判断满足条件置c_st_index 
						c_st_index=ki;
					}
				}
			}
		} 
		while(q--){
			scanf("%d%d", &r,&c);
			printf("%d\n", (dp[r][c]!=-1));
		}
	}
	return 0;
}

substring

//
////题目都有取模运算了，不动脑子都知道答案数很大，硬枚举所有搜索路径计数肯定不可行
////没思路还是先写搜索的搜法（加记忆化剪枝就变DP了），很容易想到dfs(i,j,cnt)表示到a串的第i个位置为止使用cnt个子串匹配b串前j位字符。
////由于是子串，所以每个cnt子串，i得连续，所以得再加一个状态记第i个字符选或者不选，目标串的每个元素b[j]都是肯定要选的
//#include<iostream>
//#include<cstring>
//using namespace std;
//const int maxn=1E3+10, maxm=2E2+10, mod=1000000007;//注意如果开int三次mod相加就够溢出了
//int n,m,k;
//char a[maxn],b[maxn];
//int f[maxn][maxm][maxm][2];
//int main(){
//	cin>>n>>m>>k;
//	cin>>a+1>>b+1;
//	// cout<<a+1<<" "<<b+1<<endl;
//	f[0][0][0][0]=1;//=f[0][0][0][1]=0;//注意初始化，串起始点是一种方案
//	for(int i=1;i<=n;i++){
//		f[i-1][0][0][0]=1;//=f[i-1][0][0][1]=0;//注意初始化，串起始点是一种方案
//		for(int j=1;j<=m;j++){
//			for(int c=1;c<=k;c++){
//				if(a[i]==b[j]){
//					f[i][j][c][1]=(f[i-1][j-1][c][1]/*a[i-1]和a[i]连着选*/ + (f[i-1][j-1][c-1][0]+f[i-1][j-1][c-1][1])%mod/*断开新一子串*/)%mod;
//				}else{
//					f[i][j][c][1]=0;//a[i]!=b[j]那还非得选这个字符，根本没这个方案
//				}
//				f[i][j][c][0]=(f[i-1][j][c][0]+f[i-1][j][c][1])%mod;
//			}
//		}
//	}
//	cout<<(f[n][m][k][1]+f[n][m][k][0])%mod;
//	return 0;
//}

//MLE了！果断滚动数组
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1E3+10, maxm=2E2+10, mod=1000000007;//注意如果开int三次mod相加就够溢出了
int n,m,k;
char a[maxn],b[maxn];
int f[2][maxm][maxm][2],turn=0;
vector<pair<pair<int,int>,int>> t;
int main(){
//	freopen("substring.in","r",stdin);
//	freopen("substring.out","w",stdout);
	cin>>n>>m>>k;
	t.emplace_back(make_pair(1,2),3);
	cin>>a+1>>b+1;
	for(int i=1;i<=n;i++){
		f[turn][0][0][0]=1;//=f[i-1][0][0][1]=0;//注意初始化，串起始点是一种方案
		turn^=1;
		for(int j=1;j<=m;j++){
			for(int c=1;c<=k;c++){
				if(a[i]==b[j]){
					f[turn][j][c][1]=(f[turn^1][j-1][c][1]/*a[i-1]和a[i]连着选*/ + (f[turn^1][j-1][c-1][0]+f[turn^1][j-1][c-1][1])%mod/*断开新一子串*/)%mod;
				}else{
					f[turn][j][c][1]=0;//a[i]!=b[j]那还非得选这个字符，根本没这个方案
				}
				f[turn][j][c][0]=(f[turn^1][j][c][0]+f[turn^1][j][c][1])%mod;
			}
		}
	}
	cout<<(f[turn][m][k][1]+f[turn][m][k][0])%mod;
	return 0;
}

C24yechenxi的explore错误答案

#include <iostream>
#include <cstring>
using namespace std;

struct rbt{
	int x,y,d;
}robot;
int n,m,k,T,ans;  // 错误1：ans定义为全局变量，多组数据会累积，没有重置
int x0,y0,d0;
char map[1005][1005];

bool check(int x,int y){
	if(x <= n && x >= 1 && y >= 1 && y <= m && map[x][y] != 'x')
		return 1;
	else return 0;
}

// 错误2：使用递归实现移动逻辑完全错误，会同时尝试所有方向，不符合题意
// 错误3：pre参数逻辑混乱，无法正确标记新访问的位置
void rbtwalk(int x,int y,int d,int dis,bool pre){
	if(pre){
		ans++;  // 错误4：直接累加ans，没有去重，同一位置会重复计数
	}
	if(dis == 0)
		return;
	
	// 错误5：四个方向的判断并列执行，而非根据当前方向选择一个执行
	// 机器人会同时向所有可能的方向"分身"移动，完全违背题意
	if(d == 0 && check(x,y+1) == 1)
		rbtwalk(x,y + 1,d,dis-1,0);
	else rbtwalk(x,y,(d+1)%4,dis - 1,1);
	
	if(d == 1 && check(x + 1,y) == 1)
		rbtwalk(x + 1,y,d,dis-1,0);
	else rbtwalk(x,y,(d+1)%4,dis - 1,1);
	
	if(d == 2 && check(x,y - 1) == 1)
		rbtwalk(x,y - 1,d,dis-1,0);
	else rbtwalk(x,y,(d+1)%4,dis - 1,1);
	
	if(d == 3 && check(x - 1,y) == 1)
		rbtwalk(x - 1,y,d,dis-1,0);
	else rbtwalk(x,y,(d+1)%4,dis - 1,1);
}

int main(){
	freopen("explore1.in","r",stdin);
	freopen("explore.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	for(int i = 0;i < T;i++){
		cin >> n >> m >> k;
		cin >> x0 >> y0 >> d0;
		// 错误6：地图读取方式错误，会导致行列对应关系混乱
		// 当输入是字符串时，这种逐个字符读取会破坏行结构
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= m;j++){
				cin >> map[i][j];
			}
		}
		
		// 错误7：没有初始化访问记录，无法统计不重复的位置
		// 错误8：调用递归函数的初始参数pre=0，会漏掉起始位置的计数
		rbtwalk(x0,y0,d0,k,0);

		cout << ans << "\n";  // 错误9：输出前没有重置ans，多组数据结果会累加
	}
	
	
	return 0;
}
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2022044963号-1
  3. Worker 0, 15ms
  4. Powered by Hydro v4.13.3 Community