mydcwfy's Blog

CF Round#785

Posted on
Symbols count in article: 4.6k Reading time ≈ 10 mins.

E 想出来了，不过只有最后 5 min 了，以后还是得更快给出做法。

vp 赛时：ABCDF Accepted，Score：6734，Rank：38。

改题进度：All Accepted。

A

题意：给定字符串，字符权值为 $a\to z, 1\to 26$，每次轮流选，先手只能选长度为偶的子串拿走，后手只能选长度为奇的子串拿走，问最后谁得分高，高多少。

首先长度为偶数一定直接拿走。

长度为奇数直接选择少的一个不选即可。

B

题意：判断一个字符串是否满足以下条件：

设该字符串字符集为 $\sum$，那么任意子串均满足 $\forall c_1, c_2\in \sum, |\text{occ}(c_1) - \text{occ}(c_2)| \leq 1$，$\text{occ}(c)$ 表示 $c$ 在子串中出现的次数。

爆搜或者观察样例，容易发现一定是一个周期为 $\sum$ 的循环出现，否则一定不合法。

如果有打破规律的，那么一定是 $c_1c_2\dots c_1$ 而没有包括 $c_{\sum}$，这样出现次数差一定大于 1。

这个串合法是显然的。所以证明了这个是充分必要的。

C

题意：$T$ 组询问，给出一个数 $n$ 求使其由“回文数”加和的方案数。注意没有顺序，可以选择相同的数。$T\leq 10 ^ 4, n\leq 4\times 10 ^ 4$。

暴力 DP $O(n ^ 2)$ 似乎过不去，但是容易发现回文数的个数一定不多，打个表看题解发现只有不超过 500 个，随便完全背包即可。时间复杂度 $O(nm)$，$m$ 表示回文数的个数。

另外的问题：如果是有序的怎么做？没想到什么好的做法，只有记录有多少个 binom 一下，似乎是 $O(n^2 m)$。

D

题意：给定两个有限递增等差数列 $B, C$，求有多少个有限递增等差数列 $A$ 满足 $A\cap B = C$。有无穷多个输出 -1。$T(T\leq 100)$ 组询问，

首先考虑无解情况：如果 $d_B$ 不整除 $d_C$，显然无解。如果 $d_B$ 不整除 $st_C - st_B$，无解。如果 $C$ 的首尾项超出了 $B$ 的范围，无解。

接下来考虑无穷的情况。如果 $C$ 的尾项后面一项超出了 $B$ 的范围，那么 $A$ 的尾项就可以无限延伸，就是无穷。首项前面同理。

如果 $\text{lcm}(d_A, d_B)\not= d_C$，显然是不可能的，所以我们可以暴力判断 $d_C$ 的所有因子是否合法。时间是允许的。

如果是合法的，那么 $A$ 的首项应该在 $C$ 的首项和 $C$ 首项前一项之间，尾项同理。贡献就是 $(\dfrac {d_C}{d_A}) ^ 2$。

直接暴力计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve(int ad)
{
	if (Lcm(ad, bd) != cd) return;
	res = (res + (LL) (cd / ad) * (cd / ad)) % Mod;
}
 
void work()
{
	std::cin >> bst >> bd >> bn >> cst >> cd >> cn;
	res = 0;
	if (cd % bd || (cst - bst) % bd) return void(puts("0"));
	if (cst + (LL) cd * (cn - 1) > bst + (LL) bd * (bn - 1) || cst < bst)
		return void(puts("0"));
	if (cst + (LL) cd * cn > bst + (LL) bd * (bn - 1) || cst - cd < bst)
		return void(puts("-1"));
	for (int i = 1; i <= cd / i; ++ i) {
		if (cd % i) continue;
		solve(i);
		if (i != cd / i) solve(cd / i);
	}
	printf("%d\n", res);
}

E

题意：给定 $n$ 的序列 $a_i = 2 ^ {b_i}$，可以在中间加入 $\oplus$ 或者是 $\texttt{Power}$，然后按照优先级计算，至少加入 $k$ 个 $\oplus$，问所有插入方式的计算答案的 $\oplus$，对 $2 ^ {2 ^ {20}}$ 取模，2 进制输出。$n\leq 2 ^ {20}, 1\leq b_i < 2 ^ {20}$。

可能与 tutorial 做法不一样。

考虑，然后按照一段区间算贡献。容易发现一段不包含 $\oplus$ 区间的答案只有可能是 $2 ^ x$ 的形式，于是看贡献次数是否是 2 的倍数。

考虑如果我们已经确定了一段区间，怎样计算贡献次数。如果两边都没有到头，那么相当于我们已经选择了两个端点，又强制一些不能选，那么就是 $\binom {len - 1}{k - 2}$，$len$ 表示没有被选择的区间。至少有 $k$ 个，就是 $\displaystyle \sum_{i = k - 2} ^ {len - 2} \binom{len - 2}{i}$（自己手玩一下。如果覆盖了一端，那么就是 $\displaystyle \sum_{i = k - 1} ^ {len - 1}\binom{len - 1}{i}$。覆盖了两端当且仅当 $k = 0$ 合法。

怎样快速计算这个呢？根据 Lucas 定理，那么相当于 $i\odot (len - 1) = i$ 贡献才为 1，那么我们可以使用 FMT 前缀和一下，就可以得到了。

直接暴力枚举区间是 $O(n ^ 2)$，但是容易发现不超过 20 次就会超出模数范围，也就是说，区间长度最多只有 20。于是暴力枚举即可，注意分讨。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main()
{
	std::cin >> n >> k;
	for (int i = std::max(0, k - 2); i < n; ++ i) ans[i] = 1;
	for (int i = std::max(0, k - 1); i < n; ++ i) ans2[i] = 1;
	FMT(ans, 20), FMT(ans2, 20);
	for (int i = 1; i <= n; ++ i) scanf("%d", b + i);
	for (int st = 2; st <= n; ++ st)
	{
		int cur = st;
		LL mul = b[st];
		while (cur <= n && !(mul >> 20))
		{
			if (cur ^ n) {
				if (ans[n - 2 - (cur - st + 1)]) res[mul] ^= 1;
			} else {
				if (ans2[n - 1 - (cur - st + 1)]) res[mul] ^= 1;
			}
			++ cur;
			if (b[cur] >= 20) break;
			mul <<= b[cur];
		}
	}
	int cur = 1;
	LL mul = b[1];
	while (cur <= n && !(mul >> 20))
	{
		if (cur ^ n) {
			if (ans2[n - 1 - cur]) res[mul] ^= 1;
		} else {
			if (k == 0) res[mul] ^= 1;
		}
		++ cur;
		if (b[cur] >= 20) break;
		mul <<= b[cur];
	}
	for (int i = N - 1, flag = 0; ~i; -- i) {
		flag |= res[i] || !i;
		if (flag) putchar(res[i] | 48);
	}
	return 0;
}

F

题意：$n\times n$ 的网格，合理设计四联通相邻的网格边权，使得从任意已知起点走到任意点都能通过边权异或值得到终点位置。$n\leq 32$，边权和不得超过 $48000$。

比较有意思的位运算题目。一下默认 0 开始标号。

首先考虑 1D 情况，我们需要把大的 $bit$ 出现次数尽量小，那么比如 $n = 32$，我们就在 $15\to 16$ 的边上放上 16，此外都不放 16，这样我就能判断是在 $[0, 15]$ 还是 $[16, 31]$。向下同理，可以发现需要的边权和就是 $16 + 8\times 2 + 4\times 4 + 2\times 8 + 1\times 16 = 64$。

放到 2D 上，一个显然的想法是我们将两维分开，两维互不干扰，于是 $x$ 维上使用 $0, 1, 2, 3, 4$ 位，$y$ 维上使用 $5, 6, 7, 8, 9$ 位，这样整个的代价就是 $32\times 64 + 32\times 2048 = 67584$，不能通过。

$y$ 维上全是高位，贡献组合较大，我们可以考虑交叉使用，$x$ 维使用 $0, 2, 4, 6, 8$，$y$ 维使用 $1, 3, 5, 7, 9$，这样跑一下程序发现是 $47616$，于是可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main()
{
	auto tr1 = [&](int x) {
		int res = 0;
		for (int i = 0; i <= 4; ++ i)
			if (x >> i & 1) res |= 1 << (i * 2);
		return res;
	};
	auto tr2 = [&](int x) {
		int res = 0;
		for (int i = 0; i <= 4; ++ i)
			if (x >> i & 1) res |= 1 << (i * 2 + 1);
		return res;
	};
	int n, T, res = 0;
	std::cin >> n >> T;
	for (int i = 0; i < n; ++ i, std::cout << '\n')
		for (int j = 1; j < n; ++ j) std::cout << tr1(j & -j) << ' ', res += tr1(j & -j);
	for (int i = 1; i < n; ++ i, std::cout << '\n')
		for (int j = 0; j < n; ++ j) std::cout << tr2(i & -i) << ' ', res += tr2(i & -i);
	// std::cout << res << std::endl;
	std::cout.flush();
	int cur = 0, lx = 0, ly = 0; // x, y is exchanged
	while (T --) {
		std::cin >> cur;
		for (int i = 8, ls = 0; i >= 0; i -= 2)
			if ((cur >> i & 1) ^ ls) lx ^= 1 << (i / 2), ls = 1;
			else ls = 0;
		for (int i = 9, ls = 0; i >= 0; i -= 2)
			if ((cur >> i & 1) ^ ls) ly ^= 1 << (i / 2), ls = 1;
			else ls = 0;
		std::cout << ly + 1 << ' ' << lx + 1 << std::endl;
	}
	return 0;
}