mydcwfy's Blog

CF Round#788

Posted on
Symbols count in article: 3.7k Reading time ≈ 8 mins.

vp Div2 差点把构造题想出来了，结果以为自己是错的（

赛时进度：ABCD Accpeted，Score：4091，Rank：923，Rating 无变化。

改题进度：All Accepted。

比赛传送门

A

题意：给定一个序列，问能否通过交换符号的方式使序列有序。没有 0。

容易发现负号一定在前面，随便判一下即可。

B

题意：给定一个字符串和一些关键字符，一次删除是将关键字符前面的字符删去，问有用的删除有多少次。

卡了比较久，写出来了，结果还被卡常了（（（

首先相当于是一个序列，每次所有数减 1，小于 0 的数删去，能减多少次。开头的可能不同，特判一下。证明即考虑每一段关键字符之间的段即可。

答案显然是 $\max a$ 再加 1，注意 +1 是前面的关键字符被删了，所以如果是开头就不能加 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void work()
{
	scanf("%d%s%d", &n, str + 1, &cnt);
	for (int i = 0; i < 26; ++ i) sp['a' + i] = false;
	for (int i = 1; i <= cnt; ++ i) {
		scanf("%s", tmp);
		sp[tmp[0]] = true;
	}
	int mx = 0;
	for (int i = 1, ls = 0; i <= n; ++ i) {
		if (!sp[str[i]]) continue;
		chkmax(mx, i - ls - 1 + !!ls), ls = i;
	}
	printf("%d\n", mx);
}

C

题意：给定两个排列 $a, b$，构造序列 $c$ 使得 $c_i\in\{a_i, b_i\}$ 且 $c$ 是排列的方案数有多少。部分 $c_i$ 给定，保证有解。

容易发现如果某一个没有选 $a_i$，那么 $b_j = a_i$ 的位置就得选 $b$，这样 $a_j$ 有没有选，这样就会轮下去，形成一个置换环。容易发现一个置换环只有两种选法。

题目保证有解，那么 $c_i$ 覆盖了的置换环有且仅有一种情况。计算有多少置换环没有被覆盖即可。注意长度为 1 的置换环贡献一定为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void work()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++ i) scanf("%d", b + i);
	for (int i = 1; i <= n; ++ i) nw[a[i]] = i;
	for (int i = 1; i <= n; ++ i) bel[i] = 0;
	int cnt = 0;
	for (int i = 1; i <= n; ++ i) {
		if (bel[i] || a[i] == b[i]) continue;
		++ cnt;
		int j = i;
		while (!bel[j]) bel[j] = cnt, j = nw[b[j]];
	}
	for (int i = 1; i <= cnt; ++ i) usd[i] = false;
	for (int i = 1, x; i <= n; ++ i) {
		scanf("%d", &x);
		if (x) usd[bel[i]] = true;
	}
	int und = 0;
	for (int i = 1; i <= cnt; ++ i) und += !usd[i];
	printf("%d\n", pw2[und]);
}

D

题意不好描述，看原题面吧。

主要是题意转化比较麻烦。

如果我们将一个正六边形看作是一个点的话，那么相当于是三个方向的直线交点的个数（三线相交算 3 个交点），那么假设三个方向的直线分别是 $a, b, c$，那么答案就是 $ab + bc + ac$。

如果总条数已经确定，那么答案就是将 $a, b, c$ 尽量平均即可。随便二分即可。

代码和题解略有不同，代码中是二分的 $\min\{a, b, c\}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void work()
{
	int n;
	std::cin >> n, n = (n + 1) >> 1;
	int l = 0, r = 100000;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (calc(mid, mid, mid) <= n) l = mid;
		else r = mid - 1;
	}
	if (calc(l, l, l) == n) printf("%d\n", 3 * l);
	else if (calc(l, l, l + 1) >= n) printf("%d\n", 3 * l + 1);
	else if (calc(l, l + 1, l + 1) >= n) printf("%d\n", 3 * l + 2);
	else printf("%d\n", 3 * l + 3);
}

E

题意：给定 $n = 2 ^ p$ 的树，要求给每个点 / 边设置权值，恰好覆盖 $0\sim 2 ^ {p + 1} - 1$ 的数，并选定根，使得每个点 / 边的前缀异或最大值最小。

本身想到了，结果以为菊花图将其卡掉，没认真想。

首先，观察样例可得答案应该为 $2 ^ p$，想一想为什么。

首先证明 $ans\geq 2 ^ {p}$，因为有一个 $\geq 2 ^ p$ 的数，如果答案都 $< 2 ^ p$，那么 $\oplus 2 ^ p$ 一定就 $\geq 2 ^ p$，与假设矛盾。

答案应该就是 $2 ^ {p}$，考虑构造。首先选择根是假的，任选都可以。

先将根设为 $2 ^ p$，然后每个节点假设父亲前缀异或是 $2 ^ p$，那么边就是 $x + 2 ^ p$，点的权值就是 $x$，这样该点的前缀异或也是 $2 ^ p$，可以递归下去。

所以这样答案就是 $2 ^ p$。

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
void dfs(int x, int fa, int ex)
{
	for (int i = h[x]; ~i; i = ne[i]) {
		if (e[i] == fa) continue;
		++ tot;
		w[i] = w[i ^ 1] = tot ^ (ex * n), val[e[i]] = tot ^ (!ex * n);
		dfs(e[i], x, !ex);
	}
}
 
void work()
{
	std::cin >> n, n = 1 << n, tot = 0;
	for (int i = 1; i <= n; ++ i) h[i] = -1;
	idx = 0;
	for (int i = 1, u, v; i < n; ++ i) {
		scanf("%d %d", &u, &v);
		add(u, v), add(v, u);
	}
	val[1] = n, dfs(1, 0, 1);
	puts("1");
	for (int i = 1; i <= n; ++ i) printf("%d ", val[i]);
	puts("");
	for (int i = 0; i < idx; i += 2) printf("%d ", w[i]);
	puts("");
}

F

题意：给定 $n, l, r, z$，求满足条件的 $a$ 序列使得 $\sum_{i = 1} ^ na_i\in [l, r], \oplus_{i = 1} ^ n a_i = z$。对 $10 ^ 9 + 7$ 取模。$n\leq 1000, l, r, z\leq 10 ^ {18}$。

一看显然的数位 DP，不过做法复杂了，赛时没写出来。

显然差分一下，只有上界。

记录 $f(bit, x)$ 表示处理到 $bit$ 位，最多可以放 $x$ 个 1。最后从 $f(61, 0)$ 开始最后到 $f(-1, *)$ 的方案数（因为 0 位考虑后答案放在 -1 了）。限制可以从上一位传下来，也可以通过这一位 $lim$ 为 1 得到。

直接转移即可，注意 chkmin(x, n)，因为 $x = n$ 后面相当于不限制了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int calc(LL lim)
{
	memset(f, 0, sizeof(f));
	f[62][0] = 1;
	for (int i = 61; ~i; -- i)
		for (int s = 0; s <= n; ++ s)
			for (int trs = z >> i & 1, ed = std::min((LL) n, (s << 1) + (lim >> i & 1)); trs <= ed; trs += 2)
			{
				int &nxt = f[i][std::min((LL) n, (s << 1) + (lim >> i & 1) - trs)];
				nxt = (nxt + (LL) f[i + 1][s] * C[n][trs]) % Mod;
			}
	int res = 0;
	for (int i = 0; i <= 1023; ++ i) adj(res += f[0][i] - Mod);
	return res;
}