成功由垫底转至中下水平。。

恭喜。。我？

$\text{score：55 + 0 + 0 = 55 rk：21/33}$

Problem A：猜想

题目描述

数据范围

对于所有测试数据，记 $l$ 表示 $n$ 的长度，则 $1 \le l \le 2 \times 10^5$，保证 $n$ 的最高位为 $1$，且除此之外的 $l - 1$ 位使用 $\text{std::mt19937}$ 随机生成

题解

考场上敲了个 $55$ 分的暴力，本来想说看能不能枚举每一位然后直接算它的状态，然后不行

出题人提供的题解没看懂，就看了看其他 $A$ 掉的人的思路

首先考虑分块，使分出的块尽量大，取块大小 $L = 24$，对每一块分别处理

处理当前块时先不考虑右移删 $0$ 的情况，先只考虑乘三加一的情况，最后只要在答案上加上二进制位总数即可

设第 $i$ 块储存的数为 $a_i$

类似线段树处理乘法时的操作，记两个变量 $mul, add$ 记录总共乘了多少，总共进位多少，那么转移到 $a_j$ 时则有 $a_j = mul * a_j + add$，以此类推

细节就看代码吧

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 2e05 + 10;
const int MAXL = 24 + 5;

const int L = 24;

int N;
char str[MAXN];

LL a[MAXN]= {0}, bn = 0;
inline LL lowbit (LL x) { return x & (- x); }
LL solve () {
	LL ans = 0;
	for (int i = 1; i < bn; i ++) {
		LL mul = 1, add = 0;
		while (a[i]) {
			mul *= 3, add *= 3;
			a[i] = a[i] * 3 + lowbit (a[i]); // 此处由于没删0故加上的是lowbit
			add += a[i] >> L; a[i] &= (1 << L) - 1; // 保持a[i]只有L位，同时计算进位add
			ans ++;
		}
		for (int j = i + 1; j <= bn; j ++) {
			a[j] = a[j] * mul + add;
			add = a[j] >> L; a[j] &= (1 << L) - 1;
		}
		while (add) { a[++ bn] = add & ((1 << L) - 1); add >>= L; }
		ans += L;
	}
	while (a[bn] ^ 1) {
		a[bn] = a[bn] & 1 ? a[bn] * 3 + 1 : a[bn] >> 1;
		ans ++;
	}
	return ans;
}

int main () {
	scanf ("%s", str + 1);
	N = strlen (str + 1);
	if (N == 1 && str[1] == '1') { puts ("0"); return 0; }
	reverse (str + 1, str + N + 1);
	for (int i = 1; i <= N; i ++) {
		if (! ((i - 1) % L)) bn ++;
		a[bn] |= (str[i] - '0') << ((i - 1) % L);
	}
	cout << solve () << endl;

	return 0;
}

Problem B：覆盖

题面

题解

连神仙都说神仙的神仙题

设 $S_i$ 表示点 $i$ 连接的点的集合

从小问题开始思考，考虑点 $1, 2$，若有 $S_1 - \{2\} \neq S_2 - \{1\}$，那么交换节点 $1, 2$ 的标号得到一张新无向图，可以发现它们的最小点覆盖一定是相同的，那么它们的贡献和在 $\text{mod} ~~ 2$ 的情况下一定是 $0$，也就是说，对答案有贡献的无向图一定满足 $\forall u, v, S_u - \{v\} = S_v - \{u\}$

接下来考虑 $S_1 - \{2\} = S_2 - \{1\}$ 的情况，分类讨论

  • 若存在边 $(1, 2)$，则说明 $1, 2$ 中必须存在至少一个点加入覆盖点，否则边 $(1, 2)$ 就一定不会被覆盖到，不妨强制标号小的那个加入覆盖点，再删去所有与之相连的边，那么局面就变成了 $n’ = n - 1, k’ = k - 1$ 继续搞最小点覆盖
  • 若不存在边 $(1, 2)$，那么可以选择 $S_1$ 中所有点加入覆盖点或 $1, 2$ 同时加入覆盖点，也就是说它们同时加入或不加入覆盖点，则它们可以合并成一个大点，并删去重复的边

很容易发现，每次合并的两个点实际具有的节点数目一定是相同的

暴力计算则需要枚举 $S_1, S_2$ 等，但实际上在合并 $1, 2$ 后，$S_1$ 是不会发生变化的，也就是说枚举 $S_1$ 是在后面过程完成的，在不断合并、消去点的过程中，最终我们一定可以得到图，使之满足条件，所以就不需要所谓枚举 $S_1$ 这样的步骤了

为了方便计算，不妨假定每次合并，选择由具有相同节点数目，且该数目最小的两个点，并且这个数目一定是 $2$ 的幂次，设当前找到的这两个点具有 $2^t$ 个节点，可以发现任意具有 $2^d (d < t)$ 个节点的点一定最多只有一个，且不存在具有 $2^{t + 2}$ 个节点的点，因为此时最多只会合并到 $2^{t + 1}$

那么设 $f_{n, k, t}$ 表示剩余节点数 $n$（即没加入覆盖点的剩余点的个数），还可以加入 $k$ 个覆盖点，$t$ 的意义如上所述

很明显在知道了 $n$ 之后我们就可以知道此时每种具有不同节点数的点的个数，此时有 $tot = n >> t$ 个由 $2^t$ 个节点组成的点，枚举在 $tot$ 中选择多少个进行留下、消失、合并的操作

设有 $r (r \in \{0, 1\})$ 个点留下，$m (0 \le m \le \frac{tot}2)$ 对点合并，那么可以计算出有 $d = tot - 2 * m - r$ 个点消失，计算方案数，即要在 $m + d$ 个位置中选择 $d$ 个位置消失，即方案数为 $\dbinom{m + d}d$，但实际上这是错误的，因为

若 $r = 0$ 则必须强制要求最后一组点必须合并，假如一个都不剩且最后是消失的话，那就相当于在操作前最后是只有一个点的，而这唯一的最后一个点在不与其它点组合的情况下它独自消失是没有意义的，这种情况实际上应该是被 $r = 1$ 时计算到的，故若 $r = 0$ 则须强制令最后一个操作是合并，故方案数应为 $\dbinom{m + d - [rem = 0]}d$

记忆化一下即可，递归到最后 $n$ 不足以或恰只能提供 $2^t$ 个节点时，若该状态产生贡献则其必须满足 $n \neq k \cap lowbit(n) = k$，这是因为最后剩下若干个点，发现只有最小点覆盖为最小点的时候答案才是奇数，若此时最小点覆盖大于一，则覆盖点之间可以任意连边，则答案会是 $2$ 的幂次；若不是最小点，比这个点小的点可以选择连或不连这个点，则答案亦是 $2$ 的幂次

时间复杂度 $O (n^2\log^2n)$

代码

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
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1000 + 10;

int f[MAXN][MAXN][20];
inline int lowbit (int x) { return x & (- x); }
int dp (int n, int k, int t) {
	if (n < 0 || k < 0) return 0;
	if (! k) return 1;
	if ((n >> t) <= 1) return n != k && lowbit (n) == k;
	if (~ f[n][k][t]) return f[n][k][t];
	f[n][k][t] = 0; int lim = n >> (t + 1), tot = n >> t;
	for (int mer = 0; mer <= lim; mer ++) // 合并
		for (int rem = 0; rem <= 1; rem ++) { // 留下
			int des = tot - mer * 2 - rem; // 消失
			if (des < 0) continue;
			int c1 = mer + des - (! rem), c2 = des;
			if ((c1 & c2) == c2) f[n][k][t] ^= dp (n - (des << t), k - (des << t), t + 1);
			// 对组合数 C (n, m) 若满足 (n & m) == m 则说明 C (n, m) 是奇数
		}
	return f[n][k][t];
}

int Q;

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	memset (f, - 1, sizeof (f));
	Q = getnum ();
	for (int Case = 1; Case <= Q; Case ++) {
		int n = getnum (), k = getnum ();
		printf ("%d\n", dp (n, k, 0));
	}

	return 0;
}