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;
}