CSP-S 2023 题解
T1 密码锁
观察到锁的状态数量很少,可以考虑暴力搜索每一个状态判断合法性。令 \(k=10\),时间复杂度 \(O(10^k\times k)\)。
code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int kmax = 15;
struct V {
int a[6];
} v[kmax];
int n;
int res;
int p[kmax];
bool C(int id) {
int tot = 0;
for(int i = 1; i <= 5; i++) {
tot += (p[i] == v[id].a[i]);
}
if(tot == 5) return 0; // 完全相同
if(tot == 4) return 1; // 只有一个不同
if(tot < 3) return 0; // 超过两个不同
for(int i = 1; i < 5; i++) { // 枚举相同的两位
if(p[i] != v[id].a[i] && p[i + 1] != v[id].a[i + 1]) {
int x = (p[i] + 1) % 10, y = (p[i + 1] + 1) % 10;
for(; x != p[i]; x = (x + 1) % 10, y = (y + 1) % 10) { // 暴力枚举变化量
if(x == v[id].a[i] && y == v[id].a[i + 1]) return 1;
}
}
}
return 0;
}
bool Check() {
for(int i = 1; i <= n; i++) {
if(!C(i)) return 0;
}
return 1;
}
void Dfs(int x) {
if(x > 5) {
res += Check();
return;
}
for(int i = 0; i < 10; i++) {
p[x] = i;
Dfs(x + 1);
}
}
int main() {
// freopen("lock.in", "r", stdin);
// freopen("lock.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 5; j++) {
cin >> v[i].a[j];
}
}
Dfs(1); // 暴搜
cout << res << '\n';
return 0;
}
T2 消消乐
考虑dp。定义 \(p_i\) 表示离 \(i\) 最近的满足 \(s(p_i,i)\) 是一个合法串的位置,\(f_i\) 表示以 \(i\) 这个位置结尾的合法串的数量,那么有转移 \(f_i=f_{p_i-1}+1\),表示这个串要么单独成串,要么接在最近的合法串后面。答案就是 \(ans=\sum f_i\),时间复杂度 \(O(n^2)\)。
考虑优化,重新定义 \(p_{i,j}\) 表示对于前 \(i\) 个字符而言,离 \(i\) 最近的满足 \(s_{p_{i,j}}=j\) 且 \(s(p_{i,j}+1,i)\) 是一个合法串的位置,那么对于一个位置 \(i\),它能匹配 \(s(p_{i-1,s_i}, i)\)。转移从 \(f_{p_{i-1,s_i}}\) 转移过来。因为 \(s(p_{i-1,s_i}, i)\) 匹配成了一个合法串,并且将 \(s(p_{i-1,s_i}+1, i-1)\) 中的所有合法子串合并成了一个合法串,那么接下来所有的匹配的位置 \(p\) 只能 \(< p_{i-1,s_i}\),对每一种字符继承一下即可。记 \(m=26\),时间复杂度 \(O(nm)\)。
常数还是有点大,发现瓶颈在于要枚举每种字符。发现跳 \(p\) 的过程是一条链,用数组 \(lst\) 维护每条链的链头,每次只需要修改链头即可。时间复杂度 \(O(n)\)。
code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int kmax = 2e6 + 3;
const int kmaxM = 26;
int n, a[kmax][kmaxM], f[kmax];
int lst[kmax];
string str;
long long res;
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
cin >> n >> str;
str = ' ' + str;
for(int i = 1; i <= n; i++) {
lst[i] = i;
int pre = a[lst[i - 1]][str[i] - 'a'];
if(pre) {
// cout << "***\n";
lst[i] = lst[pre - 1];
f[i] = f[pre - 1] + 1;
}
a[lst[i]][str[i] - 'a'] = i;
res += f[i];
}
cout << res << '\n';
return 0;
}
T1 密码锁
观察到锁的状态数量很少,可以考虑暴力搜索每一个状态判断合法性。令 \(k=10\),时间复杂度 \(O(10^k\times k)\)。
T1 密码锁
观察到锁的状态数量很少,可以考虑暴力搜索每一个状态判断合法性。令 \(k=10\),时间复杂度 \(O(10^k\times k)\)。