2023年信息学奥赛CSP-S2提高组复赛题解

2023年信息学奥赛CSP-S2提高组复赛题解

进阶比赛代码量比较大了

零、背景

今天来看看 2023 CSP-S 的题解吧。

A: 枚举

B: 动态规划、next函数、前缀hash、前缀矩阵

C: 模拟

D: 二分套二分+数学公式

一、密码锁（lock）

题意：密码锁有五个拨圈，每个拨圈有 10 个数字，分别是 0 到 9。

假设正确密码是 X，加锁时会使用规则1或者规则2随机转动一次密码锁，从而得到锁车后的密码。

现在告诉你 N 个锁车后的密码（都是使用正确密码按规则得到的），问可能的正确密码有多少个。

规则1：选择一个拨圈转动一个角度

规则2：选择相邻的拨圈转动相同的角度。

思路：枚举

由于锁车后密码不能是自己，所以转动的位置只能是其他 9 个位置。

规则1共有5*9=45种转动方式。

规则2共有4*9=36种转动方式。

unordered_map<ll, ll> h; vector<ll> base = {1, 10, 100, 1000, 10000, 100000}; const int N = 5; const int M = 9; ll Flap(const ll num, int i, int j) { int v = (num / base[i]) % 10; ll V = (v + j) % 10; return num - v * base[i] + V * base[i]; } void SolverOne(const ll num) { // 1 个 for (int i = 0; i < N; i++) { for (int j = 1; j <= M; j++) { const ll newNum = Flap(num, i, j); h[newNum]++; } } // 转动两个 for (int i = 1; i < N; i++) { for (int j = 1; j <= M; j++) { const ll newNum = Flap(Flap(num, i - 1, j), i, j); h[newNum]++; } } }

对于每个锁车后的密码，枚举所有规则的转法，得到疑似的正确密码。

最后统计所有疑似的正确密码，如果都可以有 N 个锁车后密码得到，则就是可能的正确密码。

ll ans = 0; for (auto [k, v] : h) { if (v == n) { ans++; } } printf("%lld\n", ans);

二、消消乐（game）

题意：给一个数组，每次可以消除相邻相同的元素，问所有非空子串中，有多少个子串是可以消除的。

思路：多种解法

一个字符串是否可消除

先思考，对于一个字符串，什么时候是可以消除的。

显然可以贪心，使用一个栈来保存剩余的未消除的前缀或后缀的字符。

如果到最后栈为空，则可以全部消除，否则不可以全部消除。

暴力解法

枚举子串的结束位置，维护一个待消除的栈，每次栈为空时，就代表当前子串是可消除的。

复杂度：O(n2)O(n^2)O(n2)

得分：50分