CSP-S 题解

非考场上想出来的会标星号。

T1 密码锁

鲜花：我看到这道题的时候满脑子想的都是春测的 lock。

考虑到只有五个拨圈，每个拨圈只有 \(10\) 个状态，\(n\le 8\)，那么直接暴力枚举每个状态即可。

考场代码：

// 15: 00
// 15: 24.

#include<bits/stdc++.h>
using namespace std;

const int maxN = 10;
int n, a[6], b[maxN][6];

bool reach(int k) {
#define c b[k]
	// turn exactly one circle. Only one circle are not the same.
	int cnt = 0;
	for(int i = 1; i <= 5; i++) cnt += (a[i] != c[i]);
	if(cnt == 1) return true;
	if(cnt > 2) return false;
	// turn two circle. Only two circle are not the same;
	int idx1 = -1, idx2 = -1;
	for(int i = 1; i <= 5; i++) {
		if(a[i] != c[i]) {
			(~idx1 ? idx2 : idx1) = i;
		}
	}
	if(idx2 != idx1 + 1) return false;
	return (c[idx2] - a[idx2] + 10) % 10 == (c[idx1] - a[idx1] + 10) % 10;
#undef c
}

int main() {
	freopen("lock.in", "r", stdin);
	freopen("lock.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 5; j++) cin >> b[i][j];
	}
    int ans = 0;
	for(int i = 0; i < 10; i++) {
		a[1] = i;
		for(int j = 0; j < 10; j++) {
			a[2] = j;
			for(int k = 0; k < 10; k++) {
				a[3] = k;
				for(int x = 0; x < 10; x++) {
					a[4] = x;
					for(int y = 0; y < 10; y++) {
						a[5] = y;
						bool flag = true;
						for(int w = 1; w <= n; w++)
							flag &= reach(w);
						ans += flag;
					}
				}
			}
		}
	}
	cout << ans;
}

T2 消消乐

考虑所有合法串的结构，一个合法串要么是最小的，要么是由很多个最小的合法串前后拼接而成。我们令 \(pre_i\) 为以 \(i\) 结尾的最短合法串的头下标（形式化的，\(pre_I=\max(j, s[j:i]\text{合法})\)），那么定义 \(dp_i\) 为以 \(i\) 结尾的合法串数量，必然有 \(dp_i=dp_{pre_i-1}+1\)，所求即为 \(\sum_{i=1}^ndp_i\)。

所以问题转为求 \(pre_i\)。初看似乎从前到后用栈模拟，弹出去的就是 \(pre_i\)，但其实用 aaa 可以轻松 hack 掉。事实上，我们应当考虑的是，从 \(pre_i\) 到 \(i\) 之间（不包括两端）的字符串是由若干合法串连接而成的，我们要做的无非就是依次跳这些串，直到串的前一个字符是当前要求 \(pre\) 的字符，或者没有 \(pre\)。

初看这个跳的过程复杂度是 \(O(n^2)\) 的，因此可以优化跳的过程。记 \(jmp_{i,j}\) 为从 \(i\) 开始跳到字符 \(j\) 的最近下标，转移是容易的。复杂度 \(\Theta(n\Sigma)\)。

但其实直接暴力跳的复杂度也是对的。我们容易发现，最差情况下每个字符不会跳超过均摊 \(\Sigma\) 次，因此时间复杂度也为 \(\Theta(n\Sigma)\)。
考场代码：

// 15: 24
// let dp[i] is the count of good substrings that end with i.
// then the answer is \sum dp[i]
// We noticed that, for every good substrings that end with i, 
// if we let pre[i] is the last(nearest && < i) index that
// pre[i] ~ i can be a good substring, dp[i] = dp[pre[i] - 1] + 1.
// Because good substrings are either mininum or maximum, and the latter
// perfectly covered the previous one(s).
// Then the problem is how we can find pre[i].
// In classical thought, some index has pre[i], and some index only have nxt[i].
// Is that right? Or say are those indexes always have dp[pre[i] - 1] = 0?
// I'd say it is right. We noticed that, the order that we delete chars is not important.
// Then for every good substrings, we can always find a way to split it into some pieces,
// that every (minimum) pieces is good.

// So we pre-calc the array pre[i], use stack tech.
// then dp.

// Weird things happened that I passed no large samples.
// Is my conclusion right????
// I thought it is right obviously!!!

// **** it. hack: ppoopp. (7)
// The fault is in fact the poped can find its pre[i].
// Then we consider to "jump". We know that what we want to find is
// have the form of AaaabbbcccdddA, which means the middle substrings are all 
// compose of pre[i] ~ i. So, we let pre[i] = i at first, 
// and i -> pre[i] -> pre[pre[i] - 1] (if pre[i] - 1 != i)
// -> pre[... - 1] (if pre[i] - 1 != i)
// until pre[i] = -1. we can compress the path to fasten this process.

// I did not compress the path, but I think it's enough to pass this prob.
// I trust the data strength.
// 16: 25

// Hit by T3 and T4.
// seems that this algo is not beyond O(n\log n).

#include<bits/stdc++.h>
using namespace std;

const int maxN = 2e6 + 10;
int n, pre[maxN], dp[maxN];
int jmp[maxN][26];
char s[maxN];

int main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	cin >> n >> (s + 1);
	memset(jmp, -1, sizeof jmp);
	memset(pre, -1, sizeof pre);
	stack<pair<char, int>> stk;
	for(int i = 2; i <= n; i++) {
		pre[i] = i - 1;
		while(pre[i] > -1 && s[pre[i]] != s[i])
			pre[i] = pre[pre[i]] - 1;// , cout << pre[i] << " ";
		pre[i] = max(pre[i], -1);
	}
	for(int i = 1; i <= n; i++) {
		if(~pre[i]) dp[i] = dp[pre[i] - 1] + 1;
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += dp[i];
	}
	cout << ans;
}

T3 结构体

鲜花：（拿到压缩包）什么题会叫 struct 呢？
看到大样例：我草。
素材来自同机房大佬。

按照题意模拟即可。

内存对齐，吐了。本人因为过菜，场上没调出来，自闭。

T4 种树

显然答案可以二分，下面考虑如何快速 check 答案的合法性。

首先我们需要贪心的选取要求快速种植的树，我们先去种那样的树不会影响结果。这是因为，对于每棵树而言，先种植什么地方无关紧要，只要能在规定时间种植自己就好。换言之，在两棵树要求的种植时间之间，随意地打乱种植顺序（需要保证合法）不会对答案造成影响；同时，我们种植的区域都是必须要先种的地方，如果一个地方不种就会导致目标无法完成。因此我们证明了贪心的正确性。

那么一个答案不合法，就当且仅当我们没有足够的时间种植。或者说我们依次做以下操作：

• 计算从该点到根上的未被覆盖的个数。如果大于与前一棵树种植的时间差，说明任务无法完成。
• 将该树到根上的所有树全部种植。

这是一个显然的树剖，需要写树剖和区间覆盖区间和线段树，时间复杂度 \(O(n\log^3n)\)，其中一个 \(\log\) 为树剖贡献，适当卡常应该是足以通过此题的。

考场上因为时间所剩不多，料定自己写不完而放弃此题。

(*)考虑到所有操作全部向根，显然有更优解法。注意到若一个点被覆盖，那么这个点到根路径上所有点都覆盖了。那么我们暴力的一个一个父亲找上去，一直到第一个被覆盖的点为止，计数即为所求。因为每个节点被访问 \(O(1)\) 次，因此 check 复杂度为 \(O(n)\)，总复杂度 \(n\log n\)。

CSP-S 丢大分了。我已在 LA 群里定了 NOIp 的目标，因为害怕不能过审就没放在博客里。祝大家 NOIp rp++！