专栏文章

CSP-J 2024题解

ccompaq
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipij49o
此快照首次捕获于
2025/12/03 12:34
3 个月前
此快照最后确认于
2025/12/03 12:34
3 个月前
查看原文

T1

排序，计数器。
测试点1:
n = 1时，答案为51。
测试点2～4:
判断出输入的牌各不相同后，答案为52 - n。
测试点5～7:
判定出牌以升序出现后，用每张牌和前一张作比较的道重复牌数，答案是52减去不重复牌数。
测试点8～10:
从保证升序的性质B获得启发，可以直接按字典序对牌排序，再统计不重复牌数。答案是52减去不重复牌数。

T2

二维数组，模拟。
测试点1～4:
k = 1时，只有一次操作，如果到达点没有越界且不是障碍物，则答案是2，否则答案为1。
测试点5、7:
地图均为空地，则执行k次操作， 只要没有越界，则可以前进，否则向右转。统计途径了几个点，即为答案。
其他测试点：
模拟kk次操作，只要下一个格子不越界且不是障碍物，则可以前进，否则向右转。边走边打标记，答案即为途径的格子数。

T3

贪心，规律，分类讨论
测试点1:
n≤20n \le 20时，可以从小到大枚举各数值，计算每个数值所需的木棍数。
测试点2:
注意到每个数字所需木棍数为[6,2,5,5,4,5,6,3,7,6] [6,2,5,5,4,5,6,3,7,6]，为了使得所拼出数值尽量小，首先位数要尽可能少，则逐位需要尽量多使用木棍，即尽可能填 88。n≤50n≤50 时，最终数值至多 ceil (50/7)=8 位。可以预先打表：从小到大枚举范围内所有数值，计算各数值所需木棍总数，并维护各木棍总数下的最小拼出值；再依次回答每个问题。
测试点3～5:
当 nn 是 77 的倍数时，因为数字 88 需 77 根木棍，所以各位全填 88 就是最小方案 。
测试点6～8:
当 nn 模 77 余 11 时，若n==1n==1, 则输出−1-1,否则前两位填 11 和 00（共 88 根木棍 ），剩下木棍数是 77 的倍数，后续数位全填 88 得最小方案。
测试点9～10:
根据上述分析，要想最小化最终数值，逐位需要尽量填88。记 k=n/7k = n / 7 。继续对77的余数进行讨论。
若余数为22时，则答案为：1+k1 + k个88；
若余数为33时，若n==3n == 3, 则答案为77，否则答案为200+k−2200 + k - 2个88；
若余数为44时，若n==4n == 4，则答案为44，否则20+(k−1)20 + (k-1)个88；
若余数为55时，则答案为2+k2 + k个88
若余数为66时，则答案为6+k6 + k个88

T4

有 nn个人，每个人都有一个数字序列。有 𝑞𝑞 次询问，每次询问给出 rr 和 cc，问是否存在 rr次接龙的方法，使得最后一次接龙的数字是以数字 𝑐𝑐结尾。每一次接龙需要满足下面三个条件：
  • 接龙序列一定是某一个人的数字序列中的一段连续子序列
  • 接龙序列的长度在 [2,k][2,k]之间
  • 不能出现连续两次接龙是同一个人的情况T

5分做法

注意到第 11个测试点 r=1r=1 的情况，这意味着我们只需要判断 nn 个人里面是否存在一个连续子序列以数字 11开头，并且以数字 𝑐𝑐 结尾。我们可以暴力枚举连续子序列的左右端点，判断是否符合要求即可。 注意：在枚举左右端点的过程中需要保证距离不超过 kk。
单次询问的复杂度为 O(∑L×min(n,∑L)O(∑L×min(n,∑L)，一共 qq 次询问，会超时。使用箱排序预处理，用 ans[c]ans[c] 表示以数字 cc结尾的连续子序列是否存在，就可以每次 O(1)O(1)地判断 ans[c]ans[c] 的值来回答询问。
CPP
#include<bits/stdc++.h>
using namespace std;

void solve(){
	int n, k, q;
	cin >> n >> k >> q; 
	vector<int>L(n);
	vector<vector<int>> a(n);
	for(int i = 0; i < n; i++){
		cin >> L[i];
		a[i].resize(L[i]);
		for(int j = 0; j < L[i]; j++)
			cin >> a[i][j];
	}
	const int M = 2e5 + 10;
	vector<bool>ans(M);
	for(int i = 0; i < n; i++){
		for(int r = 0; r < L[i]; r++){
			for(int l = 0; l < r; l++){
				if(r - l + 1 <= k && a[i][l] == 1)
					ans[a[i][r]] = true;		
			}
		}
	}
	while(q--){
		int r, c;
		cin >> r >> c;
		cout << ans[c] << '\n';
	}
}
int main(){
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

另外10分做法

(dfsdfs暴力搜索) 注意到第 2、32、3个数据点的小数据范围：∑L⩽20∑L⩽20，这提示我们可以使用 dfsdfs.暴力搜索每一次接龙的结尾是哪个数字，同时还需要枚举一下当前这一次接龙开头的数字是哪一个，判断一下开头的数字是否和上一次接龙结尾的数字相同。
但是我们还需要注意到的一个条件就是：连续两次接龙的人不能是同一个。因此，在 dfsdfs 的过程中除了需要记录上一次接龙的结尾数字是多少，还需要记录上一次接龙的人是哪一个。
至此，我们可以这样设计暴力搜索的函数去回答每一次询问：bool dfs(int t,int last,int x)bool \ dfs(int \ t, int \ last, int \ x) 表示进行了 tt次接龙，上一次接龙的人是 lastlast，并且上一次接龙结尾的数字是 xx。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
bool dfs(int t, int last, int x){
	if(t == r) return x == c;
	
	for(int i = 0; i < n; i++){
		if(i == last) continue;
		for(int rr = 0; rr < L[i]; rr++){
			for(int ll = rr - 1; ll >= 0; ll--){
				if(rr - ll + 1 > k) break;
				if(a[i][ll] == x && dfs(t + 1, i, a[i][rr]))
					return true;
			}
		}
	}
	return false;
}

void solve(){
	
	cin >> n >> k >> q; 
	L.resize(n);
	for(int i = 0; i < n; i++){
		cin >> L[i];
		a[i].resize(L[i]);
		for(int j = 0; j < L[i]; j++){
			cin >> a[i][j];
		}
	}

	while(q--){
		cin >> r >> c;
		if(dfs(0, -1, 1)) puts("1");
		else puts("0");
	}
}
int main(){
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

另外55分做法

(动态规划、降维、暴力枚举、特殊性质B) 回想一下暴力搜索的过程，如果我们知道第 tt轮，以第 lastlast个人的数字 xx结尾的方法是存在的，那么对应的我们就能求出第 t+1t+1轮，以其他人的其他数字结尾的方法。这很明显是一个由“本轮”递推到“下一轮”的过程，有递推的性质，我们就可以尝试往动态规划的方向去思考。 按照 dfsdfs 函数的三个参数，设计出 dpdp 的状态：dp[r][i][c]dp[r][i][c] 表示第 𝑟𝑟 轮接龙以第 ii个人的数字 cc结尾的方法是否存在，这是一个三维的 boolbool 数组。注意到 4∼5、7∼8、11∼12、15∼174∼5、7∼8、11∼12、15∼17这 99个测试点，它们的数据范围：r⩽10，n⩽1000r⩽10，n⩽1000，但是每个数字的范围最大是 2e52e5，没有足够的空间去定义 dpdp 数组。
对于第 1、31、3维，它们对应的是每一次询问给出的 tt和 cc，因此最好的选择是将第 22 维作为dpdp 数组降维后的值。至此，我们可以设计出一个新的 dpdp 状态：dp[r][c]dp[r][c] 表示第 rr 轮接龙以数字 cc结尾的是哪一个人。
若 dp[r][c]=−1dp[r][c]=−1，则表示不存在能够接龙的人 若 dp[r][c]=idp[r][c]=i，则表示能够接龙的人是 i，并且是唯一的 若 dp[r][c]=∞dp[r][c]=∞，则表示能够接龙的人有两个及以上
接下来，我们需要所有状态对应的 dpdp 值：枚举 rr表示第几轮接龙，枚举 ii表示第几个人来接龙，枚举这个人的每一个数字 cc表示以它作为接龙结尾的数字，接着再枚举另一个数字 xx 表示接龙开头的数字。于是，我们可以得出如下的状态转移方程：
当 dp[r][c]=−1dp[r][c]=−1且 dp[r−1][x]=−1dp[r−1][x]=−1时，dp[r][c]=−1dp[r][c]=−1 当 dp[r][c]=−1dp[r][c]=−1且 dp[r−1][x]≠−1dp[r−1][x]≠−1时，dp[r][c]=idp[r][c]=i 当 dp[r][c]≠−1dp[r][c]≠−1且 dp[r][c]≠idp[r][c]≠i 且 dp[r−1][x]≠−1dp[r−1][x]≠−1时，dp[r][c]=∞dp[r][c]=∞
注意：如果上一轮接龙的人选如果是同一个人，那么是需要跳过当次转移的！
这个做法的时间复杂度是 O(r×∑L×min(k,∑L))O(r×∑L×min(k,∑L))
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
int dp[110][N];

void solve(){
	
	cin >> n >> k >> q; 
	L.resize(n);
	for(int i = 0; i < n; i++){
		cin >> L[i];
		a[i].resize(L[i]);
		for(int j = 0; j < L[i]; j++){
			cin >> a[i][j];
		}
	}
	
	memset(dp, -1, sizeof dp);
	dp[0][1] = n; // 第0轮以1为结尾是可行，且方案很多。 
	
	for(int t = 1; t <= 10; t++){//第t轮 
		for(int i = 0; i < n; i++){//第i个人 
			for(int rr = 0; rr < L[i]; rr++){ // 右端点
				for(int ll = rr - 1; ll >= 0; ll--){ //左端点 
					if(rr - ll + 1 > k) break;
					int cc = a[i][rr], x = a[i][ll];
					
					if(dp[t - 1][x] == i) continue; //上一轮同一个人 
					
					if(dp[t][cc] == -1){
						if(dp[t - 1][x] != -1)
							dp[t][cc] = i;
					}
					else if(dp[t][cc] != i && dp[t - 1][x] != -1){	
						dp[t][cc] = n;
					}
				}
			}
		}
	}	
	while(q--){
		cin >> r >> c;
		if(dp[r][c] >= 0) puts("1");
		else puts("0");
	}
}
int main(){
	int T;
	cin >> T;
	while(T--)
		solve();
	
	return 0;
}

满分做法

到目前为止，动态规划的时间复杂度过高，瓶颈在于需要暴力枚举上一轮以哪一个数字为结尾，才能转移到本轮的状态。我们的做法是枚举每个人的区间，时间复杂度为∑L×min(∑L,k)\sum L \times min(\sum L, k)。
能不能不枚举区间？
现在考虑第tt轮, 当前枚举到第ii个人的第x个位置的数值cccc能否成为结尾。
若在上一轮(第t−1t - 1轮)中，dp[t−1][cc]!=idp[t - 1][cc] ! = i 并且dp[t−1][cc]!=−1 dp[t - 1][cc] != -1， 即上一轮能以cccc为结尾，且不是同个人，则在这一轮当中，从cccc的位置xx出发，可以向后面不超过k−1k-1个位置转移。
例如
第t−1t-1轮，有dp[t−1][1]>=0dp[t - 1][1] >=0, 即可以以11为结尾。
那么第tt轮，假设第ii个人的数值为：{1,2,1,2,3,4}\{1,2, 1,2,3,4\}，k=3k = 3若dp[t−1][1]!=idp[t - 1][1] ! = i 并且dp[t−1][1]!=−1 dp[t - 1][1] != -1, 则第一个1能管后面22个位置，都能dp[t][2],dp[t][1]dp[t][2], dp[t][1]，枚举到第二个1，又可以管住后面22个位置。
整体时间复杂度为 O(r×∑L)O(r×∑L)
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, q;
vector<int>L;
vector<int> a[N];

int r, c; 
int dp[110][N];

void solve(){
	
	cin >> n >> k >> q; 
	L.resize(n);
	for(int i = 0; i < n; i++){
		cin >> L[i];
		a[i].resize(L[i]);
		for(int j = 0; j < L[i]; j++){
			cin >> a[i][j];
		}
	}
	
	memset(dp, -1, sizeof dp);
	dp[0][1] = n; // 第0轮以1为结尾是可行，且方案很多。 
	
	for(int t = 1; t <= 100; t++){//第t轮 
		for(int i = 0; i < n; i++){//第i个人 
			int cnt = 0; // 能往后转移的长度 
			for(int x = 0; x < L[i]; x++){  
					int cc = a[i][x]; 
					
					if(cnt-- > 0) {
						if(dp[t][cc] == -1)
							dp[t][cc] = i;
						else if(dp[t][cc] != i)
							dp[t][cc] = n;
					}
					
					if(dp[t - 1][cc] != i && dp[t - 1][cc] != -1)
						cnt = k - 1;	
			}
		}
	}	
	while(q--){
		cin >> r >> c;
		if(dp[r][c] >= 0) puts("1");
		else puts("0");
	}
}
int main(){
	int T;
	cin >> T;
	while(T--)
		solve();
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...