mydcwfy's Blog

CF Educational Round#125

Posted on
Symbols count in article: 5.8k Reading time ≈ 13 mins.

赛时偷瞄 F 难度，不小心看到了做法，结果还是不会……

A

题意：$T(T\leq 3000)$ 给定 $x, y$，问在每步距离只能走整数长度情况下，最少游走几步能从 $(0, 0)$ 走到 $(x, y)$。$0\leq x, y\leq 50$。

容易发现答案不超过 2，因为 $(0, 0)\to (0, y)\to (x, y)$ 就可以两步完成。一步和不走的情况判一下就可以了。

B

题意：有一个长度为 $n + 1$ 的序列 $a$，已知 $a_0 = 0$，$a_i$ 只能在 $a_{i - 1}$ 的基础上加 $x$ 或者减 $y$，并且每一项不能超过 $B$，求最大和。$n\leq 2\times 10 ^ 5$，$1\leq x, y, B\leq 10 ^ 9$。

容易发现一个贪心：能加则加，否则减。简单的证明一下：容易发现反面就是 $a_{i - 1} + x\leq B$，但是 $a_i = a_{i - 1} - y$。这时如果找不到后面的一个 $j$ 是 $a_{j - 1} + x$ 的话，显然可以把这一步替换成 $+x$。否则的话，我们交换 $i, j$ 的操作，容易发现 $[i, j)$ 这一段是递减的，$a_i\leq B$，那么所有都符合 $\leq B$ 的条件，而 $a_j$ 不变。

C

题意：给定一个 $n$ 的括号序列，要求每次找到一个好的最短前缀，然后删除这个前缀。一个括号序列是好的当且仅当它是一个合法的括号序列或者是一个回文串且长度不小于 2。问会删除多少次，最后剩下长度是多少。$\sum n\leq 5\times 10 ^ 5$。

容易发现我们拿一个指针向前扫，然后实时判断该段区间是否合法，即可做到 $O(n)$ 次询问一段区间是否合法。

首先第一个条件，由于是双指针，$r$ 右指针的变化量是 $O(1)$ 的，可以动态维护是不是合法的括号序列。当且仅当 $cnt = 0$，且任意时刻 $cnt\geq 0$，表示左括号减右括号。

第二个条件随便 Hash 一下即可。

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
int gethash1(int l, int r)
{
	return (hash1[r] + (LL) (Mod - pw3[r - l + 1]) * hash1[l - 1]) % Mod;
}
 
int gethash2(int l, int r)
{
	return (hash2[l] + (LL) (Mod - pw3[r - l + 1]) * hash2[r + 1]) % Mod;
}
 
bool check(int l, int r)
{
	if (l == r) return false;
	int mid = (l + r) >> 1;
	if ((r - l + 1) & 1) return gethash1(l, mid) == gethash2(mid, r);
	else return gethash1(l, mid) == gethash2(mid + 1, r);
}
 
void work()
{
	scanf("%d%s", &n, s + 1);
	pw3[0] = 1;
	for (int i = 1; i <= n; ++ i) pw3[i] = pw3[i - 1] * 3LL % Mod;
	for (int i = 1; i <= n; ++ i)
		hash1[i] = (hash1[i - 1] * 3LL + (s[i] == ')')) % Mod;
	hash2[n + 1] = 0;
	for (int i = n; i; -- i)
		hash2[i] = (hash2[i + 1] * 3LL + (s[i] == ')')) % Mod;
	int i, j, cnt = 0;
	for (i = 1; i <= n; i = j + 1)
	{
		int top = 0, flag = 1;
		j = i;
		while (j <= n && !check(i, j))
		{
			top += s[j] == '(' ? 1 : -1;
			if (top < 0) flag = 0;
			if (top == 0 && flag) break;
			++ j;
		}
		if (j > n) break;
		cnt ++;
	}
	printf("%d %d\n", cnt, n - i + 1);
}

D

题意：有 $n$ 种剑，每一种有每秒攻击力 $d_i$ 和 生命值 $h_i$，以及单价 $c_i$ 金币。有 $m$ 只怪兽，每秒攻击力为 $D_i$，生命值为 $H_i$。攻击一个怪兽只能买一种剑，但个数不限。攻击时间是连续的，也就是说击败时间可以不是整数。你能获胜当且仅当怪兽死亡的时间严格比你任意一把剑死亡的时间短。问能否在 $C$ 个金币内买剑，使得你一定能获胜，如果能输出最小金币数。$n, m\leq 3\times 10 ^ 5$，$C\leq 10 ^ 6$，$d_i, h_i, D_i\leq 10 ^ 6$，$H_i\leq 10 ^ {12}$。

注意到能获胜当且仅当 $cnt\times d_i\times h_i > D\times H$，$cnt$ 表示买的数量。一下把 $cnt\times d_i\times h_i$ 称作权值。

很明显 $d, h$ 范围都很大，无法做文章。看到 $C$ 很小，考虑变换思路，设 $s_i$ 表示 $i$ 个金币内最多能买到的权值。

我们有了 $s_i$ 过后，可以去更新他的倍数，这样我们可以在 $O(C\log C)$ 的时间内得到 $s$。

后面直接在 $s$ 上二分查找第一个大于怪兽权值的位置即可，注意特判无法做到的情况。

时间复杂度 $O(n + (m + C)\log C)$，可以通过。

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
int main()
{
	int n, m, C;
	std::cin >> n >> C;
	for (int i = 1, c, d, h; i <= n; ++ i)
	{
		scanf("%d %d %d", &c, &d, &h);
		chkmax(mx[c], (LL) d * h);
	}
	for (int i = 1; i <= C; ++ i)
	{
		chkmax(mx[i], mx[i - 1]);
		for (int d = 2; i * d <= C; ++ d)
			chkmax(mx[i * d], mx[i] * d);
	}
	std::cin >> m;
	LL d, h;
	while (m --)
	{
		scanf("%lld %lld", &d, &h), d *= h;
		if (mx[C] <= d) printf("-1 ");
		else printf("%lld ", std::upper_bound(mx + 1, mx + C + 1, d) - mx);
	}
	return 0;
}

E

题意：问有多少张点数为 $n$ 的带边权完全图，边权 $\in [1, k]$，并且以 1 为根的菊花是原图的一棵最小生成树，对 998244353 取模。$n, k\leq 250$，4s。

简单计数题。

容易发现我们把 $(1, i)$ 的连边的权值放在 $i$ 上，相当于 $w(i, j)\geq \max\{a(i), a(j)\}$，考虑顺序枚举 $[1, k]$ 中出现的次数，然后用 EGF 类似的形式计算答案。记录 $f_{i, s}$ 表示当前最大值为 $i$，且已经有 $s$ 个点被选的方案数。大力转移，随便做做满足 $w(x, y)\geq i$ 的个数即可。时间复杂度 $O(n ^ 2k)$ 或 $O(n ^ 2k\log n)$，可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	init();
	std::cin >> n >> k, -- n;
	f[0] = 1;
	for (int i = 1; i <= k; ++ i)
	{
		for (int s = 0; s <= n; ++ s) g[s] = 0;
		for (int s = 0; s <= n; ++ s)
			for (int nxt = 1; nxt + s <= n; ++ nxt)
				g[s + nxt] = (g[s + nxt] + (LL) f[s] * infact[nxt] % Mod *
					qpow(k - i + 1, nxt * s + (nxt - 1) * nxt / 2)) % Mod;
		for (int s = 0; s <= n; ++ s) adj(f[s] += g[s] - Mod);
	}
	for (int s = 0; s <= n; ++ s) f[s] = (LL) f[s] * fact[s] % Mod;
	std::cout << f[n] << '\n';
	return 0;
}

F

题意：在一棵 $n$ 个点的树上，每个点可以选择一个字符，有 $q$ 个限制：$(x_i, y_i)$ 的路径组成的串，要么是 $s_i$，要么是 $s_i$ 翻转，记作 $\overline s$。问是否存在一种合法的解，若存在则给出一组。$n, q, \sum s_i\leq 4\times 10 ^ 5$，9s。

注意到”要么……要么……“，想一想发现这其实是一个 2-SAT 的模型。考虑对每一个限制设一个 bool 变量，表示是否翻转。但是如果我们把 26 个字母在同一个点上都设出来，显然不是一个 2-SAT 模型了。

容易发现其实一个位置如果一旦被一个点覆盖，那么他一定最多只有两种字符选择，那么这时就可以转化成一个 2-SAT 模型。设 $c_{i, j}$ 表示 $i$ 位置的 $j$ 选择，如果 $c_{i, j}$ 不对应 $s$，那么就会连向 $\overline s$，而反过来 $s$ 就会连向 $c_{i, \neg j}$。其他同理。于是需要开 $2\times n + 2\times m$ 个点，跑一下是否满足条件即可。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
void tarjan(int x)
{
	dfn[x] = low[x] = ++ *dfn, ins[stk[++ top] = x] = true;
	for (int i = h[x], v; ~i; i = ne[i])
		if (!dfn[v = e[i]]) tarjan(v), chkmin(low[x], low[v]);
		else if (ins[v]) chkmin(low[x], dfn[v]);
	if (low[x] ^ dfn[x]) return;
	int cur;
	++ *bel;
	do bel[cur = stk[top --]] = *bel, ins[cur] = false; while (cur != x);
}

void dfs(int x, int fa = 0)
{
	dep[x] = dep[fa] + 1, f[x] = fa;
	for (int v : g[x])
		if (v != fa) dfs(v, x);
}

std::vector<int> getpath(int u, int v)
{
	std::vector<int> pth1, pth2;
	while (u != v)
	{
		if (dep[u] > dep[v]) pth1.push_back(u), u = f[u];
		else pth2.push_back(v), v = f[v];
	}
	pth1.push_back(u);
	std::reverse(pth2.begin(), pth2.end());
	for (int &x : pth2) pth1.push_back(x);
	return pth1;
}

int main()
{
	int m;
	std::cin >> n >> m;
	for (int i = 1; i <= 2 * n + 2 * m; ++ i) h[i] = -1;
	for (int i = 1, u, v; i < n; ++ i)
	{
		scanf("%d %d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	auto getid = [&](int u, char c) {
		if (!gt[u][0]) gt[u][0] = c;
		if (gt[u][0] == c) return 0;
		if (!gt[u][1]) gt[u][1] = c;
		if (gt[u][1] == c) return 1;
		return -1;
	};
	dfs(1);
	for (int id = 1, u, v; id <= m; ++ id)
	{
		scanf("%d%d%s", &u, &v, s);
		auto path = getpath(u, v);
		int sz = path.size();
		for (int i = 0; i < sz; ++ i)
			for (int x = 0; x < 2; ++ x)
			{
				if (getid(path[i], s[i]) != x) {
					add(path[i] + x * n, 2 * n + id);
					add(2 * n + m + id, path[i] + !x * n);
				}
				if (getid(path[i], s[sz - i - 1]) != x) {
					add(path[i] + x * n, 2 * n + m + id);
					add(2 * n + id, path[i] + !x * n);
				}
			}
	}
	for (int i = 1; i <= n; ++ i)
	{
		if (!gt[i][0]) gt[i][0] = 'a';
		if (!gt[i][1]) gt[i][1] = 'a';
	}
	for (int i = 1; i <= 2 * n + 2 * m; ++ i)
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; ++ i)
		if (bel[i] == bel[i + n]) return puts("NO"), 0;
	for (int i = 2 * n + 1; i <= 2 * n + m; ++ i)
		if (bel[i] == bel[i + m])
			return puts("NO"), 0;
	
	puts("YES");
	for (int i = 1; i <= n; ++ i) putchar(gt[i][bel[i + n] < bel[i]]);
	return 0;
}