20231101题解

发表于 分类于 ， 阅读次数：

xor

思路分析

例行打表。发现整个表是一个分形的样子：

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
 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 16  1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 32
 2  -  4  -  2  -  8  -  2  -  4  -  2  - 16  -  2  -  4  -  2  -  8  -  2  -  4  -  2  - 32  -
 1  4  -  -  1  8  -  -  1  4  -  -  1 16  -  -  1  4  -  -  1  8  -  -  1  4  -  -  1 32  -  -
 4  -  -  -  8  -  -  -  4  -  -  - 16  -  -  -  4  -  -  -  8  -  -  -  4  -  -  - 32  -  -  -
 1  2  1  8  -  -  -  -  1  2  1 16  -  -  -  -  1  2  1  8  -  -  -  -  1  2  1 32  -  -  -  -
 2  -  8  -  -  -  -  -  2  - 16  -  -  -  -  -  2  -  8  -  -  -  -  -  2  - 32  -  -  -  -  -
 1  8  -  -  -  -  -  -  1 16  -  -  -  -  -  -  1  8  -  -  -  -  -  -  1 32  -  -  -  -  -  -
 8  -  -  -  -  -  -  - 16  -  -  -  -  -  -  -  8  -  -  -  -  -  -  - 32  -  -  -  -  -  -  -
 1  2  1  4  1  2  1 16  -  -  -  -  -  -  -  -  1  2  1  4  1  2  1 32  -  -  -  -  -  -  -  -
 2  -  4  -  2  - 16  -  -  -  -  -  -  -  -  -  2  -  4  -  2  - 32  -  -  -  -  -  -  -  -  -
 1  4  -  -  1 16  -  -  -  -  -  -  -  -  -  -  1  4  -  -  1 32  -  -  -  -  -  -  -  -  -  -
 4  -  -  - 16  -  -  -  -  -  -  -  -  -  -  -  4  -  -  - 32  -  -  -  -  -  -  -  -  -  -  -
 1  2  1 16  -  -  -  -  -  -  -  -  -  -  -  -  1  2  1 32  -  -  -  -  -  -  -  -  -  -  -  -
 2  - 16  -  -  -  -  -  -  -  -  -  -  -  -  -  2  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -
 1 16  -  -  -  -  -  -  -  -  -  -  -  -  -  -  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -
16  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 2  -  4  -  2  -  8  -  2  -  4  -  2  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  4  -  -  1  8  -  -  1  4  -  -  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 4  -  -  -  8  -  -  -  4  -  -  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  2  1  8  -  -  -  -  1  2  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 2  -  8  -  -  -  -  -  2  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  8  -  -  -  -  -  -  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 8  -  -  -  -  -  -  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  2  1  4  1  2  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 2  -  4  -  2  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  4  -  -  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 4  -  -  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1  2  1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 2  - 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
 1 32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
32  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -

看上去很有规律，是吧。

仔细一想其实一点也不好算。

所以我们从复杂中抓住简单：如果我们只看 1 的位置呢？

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
1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - 1 - - - 1 - - - 1 - - - 1 - - - 1 - - - 1 - - - 1 - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - - - - - 1 - 1 - - - - - 1 - 1 - - - - - 1 - 1 - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - - - - - 1 - - - - - - - 1 - - - - - - - 1 - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - 1 - 1 - - - - - - - - - 1 - 1 - 1 - 1 - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - 1 - - - - - - - - - - - 1 - - - 1 - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - - - - - - - - - - - - - 1 - 1 - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - - - - - - - - - - - - - 1 - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - 1 - - - 1 - - - 1 - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - - - - - 1 - 1 - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - - - - - 1 - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - 1 - 1 - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - 1 - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

仍然是分形！这启发我们枚举 2 的整数次幂，然后算贡献。

我们先考虑大小为 \(2^k \times 2^k\) 的矩阵：设这个贡献是 \(k\)，则由于分形， \(cnt_k = 3cnt_{k-1}\)。显然 \(cnt_{1}=1\)。

这个贡献可以按位计算：首先找到 \(n\) 最大的二进制位，如果是 \(i\)，那么就有 \(cnt_i\) 的贡献。

然后，如果下一个二进制位为 \(j\)，则 \(2^j \times 2^j\) 大小的矩阵就有 \(2^{i-j}\) 个。另外，下方和右方是对称的，所以贡献还要乗二。

如果还有二进制位 \(k\)，则 \(2^k \times 2^k\) 大小的矩阵数量是 \(2^j \times 2^j\) 的 \(2^{j-k-1}\) 倍。

以此类推。2、4、8 等的贡献同理。自己打个表好了。

但仍然有一些细节：比如 \(2\times 2\) 的矩阵有 1 个贡献，但如果 \(n\) 正好是奇数呢？最后一排怎么计算呢？

假设当前分形的最小矩阵是 \(2^x \times 2^x\) 的，如果 \(n \equiv y \pmod{2^x}\)：

  • 当 \(y \ge 2^{x-1}\) 时，贡献正好 \(cnt_x\) 个。（其实你会发现 \(cnt_x = 2^{x-1}\)）
  • 否则贡献为 \(y\) 个。

另外，如果 \(n\) 的第一位 \(i\le x\)，则也要分类讨论：

  • 当 \(i=x\) 时，总贡献就是 \(cnt_x\)，不必再看更低的位。
  • 当 \(i=x-1\) 时，总贡献是 \((n-2^i)cnt_x\)。
  • 否则没有贡献。

AC 代码

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
57
58
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e3 + 10;
const long long mod = 1e9 + 7;
long long cnt[maxn][maxn], p[maxn], ans, inv_2 = (mod + 1) >> 1;
char s[maxn];
int n;

int main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	p[0] = 1;
	for (int i = 0; i <= 3000; i++) {
		cnt[i][i + 1] = p[i]; p[i + 1] = (p[i] << 1) % mod;
		for (int j = i + 2; j <= 3001; j++) {
			cnt[i][j] = (cnt[i][j - 1] * 3) % mod;
		}
	}
	scanf("%s", s); n = strlen(s);
	reverse(s, s + n);
	for (int i = 0; i <= 3000; i++) {
		long long sum = 0, fac = 0; int pj = -1;
		for (int j = n - 1; j >= 0; j--) {
			if (s[j] == '1') {
				if (pj == -1) {
					if (j <= i) {
						if (j == i) {
							(sum += p[i] * p[i]) %= mod;
							break;
						} else if (j == i - 1) {
							pj = i + 1; fac = 2;
						} else break;
					}
					else {
						(sum += cnt[i][j] * p[i]) %= mod;
						pj = j;
						fac = 2;
					}
				} else {
					if (j <= i) {
						(sum += (fac * inv_2) % mod * p[pj - (i + 1)] % mod * p[i] % mod * p[j] % mod * 2) %= mod;
						if (j == i) break;
					} else {
						(fac *= p[pj - j - 1]) %= mod;
						pj = j;
						(sum += (cnt[i][j] * p[i]) % mod * fac % mod * 2) %= mod;
					}
				}
			}
		}
		cerr << sum << endl;
		(ans += sum) %= mod;
	}
	printf("%lld\n", ans);
	return 0;
}

robot

诈骗题。

首先要看出来这是一颗树，而且是一颗以 \((1, 1)\) 为根的二叉树。

宽搜虽然是随机，但是仍然满足宽搜性质：深度从小到大。

然后我们发现 \((n, m)\) 是深度最大的。所以每个点都会被访问。次数就是 \(nm-1\)。

深搜也很简单。目标路径上的边肯定要经过的。非目标的子树如果进入就一定要遍历子树，有两倍边数，又因为是二叉树，概率是 \(50\%\)，期望就是边数。为 \(nm-1\)。

game

不会有比官方 sol 更简单的 sol 了。

考虑将边的贡献拆分到点上。对于边 \((u, v, w)\) 我们将 \(u\) 和 \(v\) 的点权都加上 \(\frac{w}{2}\) 由于我们只需算出两个人得分的差值，当一条边的端点分属于两个人的时候，对两个人的分差的贡献是 0。 因此，我们直接对所有更新完的点权排序依次选即可。

count

先考虑整个矩阵的最大值：它所在的那一行和那一列一定都是它。所以如果 \(\max\{a\} \ne \max\{b\}\) 就无解。

反过来，将 \(a\) 和 \(b\) 全部排在最大的点所在的那一行/列，一定是合法的。

剩下的就是尽可能小。如果 \(a,b\) 中有值相同，则一定可以通过一个点同时满足行和列。另一方面，不可能同时满足更多的行列了。

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
#include <bits/stdc++.h>
using namespace std;

int n, m, tid;
const int maxn = 3e5 + 5;
int a[maxn], b[maxn];
long long ans;

template <class T>
void read(T &r) {
	r = 0; int ch, f = 0;
	while (!isdigit(ch = getchar())) if (ch == 45) f ^= 1;
	while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
	if (f) r = -r;
}

int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	read(tid); read(n); read(m);
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int j = 1; j <= m; j++) read(b[j]);
	sort(a + 1, a + n + 1, [](int a, int b) -> bool { return a > b; });
	sort(b + 1, b + m + 1, [](int a, int b) -> bool { return a > b; });
	if (a[1] != b[1]) {
		printf("-1\n");
		return 0;
	}
	int i = 1, j = 1;
	while (i <= n || j <= m) {
		if (a[i] == b[j]) ans += a[i], i++, j++;
		else if (j > m || a[i] > b[j]) ans += a[i], i++;
		else ans += b[j], j++;
	}
	printf("%lld\n", ans);
	return 0;
}