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分
