2024 CSP-J 题解

2024 CSP-J题解

扑克牌

​ 题目给出了一整套牌的定义，但是纯粹在扯淡，完全没有必要去判断给出的牌的花色和点数，我们用一个循环来依次读入每一张牌，如果这个牌在之前出现过，我们就让答案减一。这里建议用map、unordered_set或者给每一种牌一个编号，然后用数组存储也可以。

#include <bits/stdc++.h>using namespace std;int n;int main()
{map<string, bool> M;int ans = 52;cin >> n;for (int i = 1; i <= n; i++){string tmp;cin >> tmp;if (!M[tmp])ans--, M[tmp] = 1;}cout << ans;return 0;
}

地图探险

​ 纯粹的记忆化搜索，用数组存储对于每一个方向下一步坐标的差值，每次要执行移动操作之前，我们都要不停地执行右转的操作，直到下一步的坐标合法为止。

​ 我们可以开辟一个二维数组来记录每一次搜索经过的位置，每次走到一个之前没走过的位置，我们就让答案加一。

#include <bits/stdc++.h>using namespace std;const int maxn = 1e3 + 5;
int mx[4] = {0, 1, 0, -1}, my[4] = {1, 0, -1, 0}, ans; // mx 和 my 用来存储每一个方向对应的变化值
char Map[maxn][maxn];                                  // 储存整个地图
bool vis[maxn][maxn];                                  // 记录每个地方都有没有被遍历过
int n, m, k, x_0, y_0, d;void dfs(int x, int y, int d)
{if (!vis[x][y]) // 如果这个位置还没有走过，就让答案加一ans++;vis[x][y] = 1;int X = x + mx[d], Y = y + my[d];                                   // 下一步要走的位置while ((X < 1 || X > n || Y < 1 || Y > m || Map[X][Y] == 'x') && k) // 下一步不合法，并且还需要执行操作，那么我们右转d = (d + 1) % 4, k--, X = x + mx[d], Y = y + my[d];             // k 一定要减一if (k == 0)                                                         // 后面没有操作要进行了return;k--;dfs(X, Y, d); // 移动到下一步
}void solve()
{cin >> n >> m >> k;cin >> x_0 >> y_0 >> d;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> Map[i][j];dfs(x_0, y_0, d);cout << ans << '\n'; // 因为多组样例，这几行都是清空的操作ans = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)vis[i][j] = 0;
}int main()
{int T;cin >> T;while (T--){solve();}return 0;
}

小木棍

​ 数学（dabiao）题，可以先简单找找规律。

​ 首先对于 0~9 每一种数字，如果要用火柴拼出来的话，他们分别需要 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 根木条。根据数据范围，我们可以得到一点提示，这题反正是跟 7 脱不了关系。

​ 其次有一个很显而易见的道理，因为 8 这个数字需要的火柴最多，整个数字的长度就越短，也就越小，那么当 n 是 7 的倍数时，那么 $(n/7)$ 个 8 组成的数字就是最小的。

除此之外：

如果 n % 7 = 1:

​ 因为一根火柴什么数字都拼不出来，所以需要去牺牲从前往后第二个数字来凑出一个数来（想不出来可以打表）。结果就是 10 + 很多个 8。

​ 但是需要特判 n = 1 的时候，结果是 -1。

如果 n % 7 = 2:

​ 两根火柴可以组成一个 1，后面全部填 8。

如果 n % 7 = 3:

​ 需要特判 n = 3 和 n = 10，答案分别是 7 和 22，其他情况，答案是 200 + 很多个 8。

如果 n % 7 = 4:

​ 特判 n = 4，答案是 4，其他情况答案是 20 + 很多个 8。

​

如果 n % 7 = 5:

​ 结果是 2 + 很多个 8。

如果 n % 7 = 6:

​ 结果是 6 + 很多个 8。

#include <bits/stdc++.h>using namespace std;int n, T;int main()
{cin >> T;while (T--){cin >> n;int type = n % 7;if (type == 0){for (int i = 1; i <= n / 7; i++)cout << 8;cout << '\n';continue;}if (type == 1){if (n == 1)cout << -1 << '\n';else{cout << 10;for (int i = 1; i <= n / 7 - 1; i++)cout << 8;cout << '\n';}continue;}if (type == 2){cout << 1;for (int i = 1; i <= n / 7; i++)cout << 8;cout << '\n';continue;}if (type == 3){if (n == 3)cout << 7 << '\n';else if (n == 10)cout << 22 << '\n';else{cout << 200;for (int i = 1; i <= (n - 17) / 7; i++)cout << 8;cout << '\n';}continue;}if (type == 4){if (n == 4)cout << 4 << '\n';else{cout << 20;for (int i = 1; i <= (n - 11) / 7; i++)cout << 8;cout << '\n';}continue;}if (type == 5){cout << 2;for (int i = 1; i <= (n - 5) / 7; i++)cout << 8;cout << '\n';continue;}if (type == 6){cout << 6;for (int i = 1; i <= (n - 6) / 7; i++)cout << 8;cout << '\n';continue;}}return 0;
}

​ 这种题目一般建议还是先打个表找找规律，或者直接写一个暴力看看比较小的数据点的答案。例如这个题目，可以先写一个 10 的某次方的暴搜，枚举每一位是多少。

接龙

​ 这里我没有想到特别简单的思路，要么就是空间不太正确，要么就是时间不太正确，目前的做法是 dp + 差分前缀和。

​ 我们预处理出 100 轮每一轮的答案，然后做个离线的输出，我们把所有的询问按照从小到大的顺序进行排序，因为预处理的时候我们是按照轮数从小到大的顺序进行 $dp$ 的，所以我们直接把答案全部记录下来就可以。

​ 然后就是 $dp$ 状态的设计，首先 $$dp[i][j]$$ 表示第 i 轮以元素 j 为结尾的答案。但是这里因为第 i 轮的答案只与前一轮有关，所以我们可以把 $dp$ 的前一个状态去掉，用两个 $dp$ 数组轮流使用就可以了。

​ 因为在接龙的时候，当前这一轮的人不能和上一轮一样，所以我们重新设计一下状态， dp[j] 表示当前这一轮以元素 j 结尾。

$dp[j]=-2$：当前这一轮以 j 结尾，没人能完成接龙；

$dp[j]=-1$：当前这一轮以 j 结尾，有两个人能完成接龙，根据题意，如果有两个人能完成接龙（使用的句子开头和结尾相同），那么接龙就一定可以完成，所以我们只用考虑两个人的情况就可以了，两个人以上不用考虑；

$dp[j]=i$（i 大于 0）：当前这一轮以 j 结尾，并且只有一个人能完成接龙，这个人的编号是 $i$。

状态转移方程：

​ 对于每一个人 i 遍历所有的 $S_{i,j}$ （第 $i$ 个人的词库里面的第 $j$ 个字符），当发现上一轮 $dp[S_{i,j}]$ 不等于 $-2$ 且不等于 $i$ 的时候（连续的两轮不能是同一个人），说明这个数后面的 k 个元素，可以在当前这一轮作为的最后一个元素完成接龙，因为是连续的一个区间，所以这里我们使用差分来进行维护，然后我们再进行前缀和，这样就可以看出来有哪些元素可以完成接龙了（对于 $i$ 这一个人来说），把找出来的元素的 $dp$ 值赋成 $i$。

​ 然后我们再去处理其他人，如果发现有一个元素已经被赋值了，说明有两个或者两个以上的人可以使用这个元素作为结尾完成这一轮接龙，$dp$ 值就是 -1。

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve()
{int n, k, q;cin >> n >> k >> q;vector<vector<int>> g(n); // 存储所有的 Svector<int> len(n); // 每个 S 对应的长度int maxn = -1;bool flag = false; // 如果没有 1，说明完全没有可能接龙，直接寄for (int i = 0; i < n; i += 1){cin >> len[i];g[i].resize(len[i]);for (int j = 0; j < len[i]; j += 1){cin >> g[i][j];maxn = max(maxn, g[i][j] + 1);if (g[i][j] == 1 && j != len[i] - 1)flag = true;}}vector<tuple<int, int, int>> a(q); // 储存询问int idx = 0, ma = 0;for (auto &[r, c, id] : a){cin >> r >> c;ma = max(ma, r);id = idx++;}idx = 0;sort(a.begin(), a.end()); // 按照轮数从小到大的顺序排列vector<int> ans(q); // 答案vector<int> dp(maxn, -2); // 先全部赋值成 -2，表示不能以 j 为结尾完成这一轮dp[1] = -1;vector<int> now(200000); // 差分数组for (int round = 1; round <= ma && flag; round += 1){vector<int> dp1(maxn, -2); // 当前这一轮的 dp 值for (int i = 0; i < n; i += 1) // 枚举第几个人{for (int j = 0; j < len[i]; j++) // 初始化now[j] = 0;for (int j = 0; j < len[i] - 1; j += 1) {int x = g[i][j];if (dp[x] != -2 && dp[x] != i) // dp 是上一轮的结果，如果 x 可以作为接龙的结尾，那么后面 k 个也可以 {int to = j + k; // 差分now[j + 1] += 1;if (to < len[i])now[to] -= 1;}}for (int j = 1; j < len[i]; j += 1){int x = g[i][j];now[j] += now[j - 1]; // 前缀和if (now[j] != 0 && dp1[x] != -1) // 如果这个数字被差分标记了并且没有两个以上的人标记了这个元素（如果是 -1 就不用管了）{if (dp1[x] == -2)dp1[x] = i;else if (dp1[x] != i) // 已经有别人标记过了dp1[x] = -1;}}}while (idx < q) // 给每一个询问提供一个答案{auto &[r, c, id] = a[idx];if (r != round)break;else{if (c >= maxn || dp1[c] == -2)ans[id] = 0;elseans[id] = 1;idx += 1;}}dp = dp1;}for (int i = 0; i < q; i += 1) // 离线输出结果cout << ans[i] << "\n";
}
int main()
{   ios::sync_with_stdio(0); // 怕被卡，关流一下 cin.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}

作者能力有限，如果有任何错误之处，还请各位指教。

​

​

​