mydcwfy's Blog

CF Round#791

Posted on
Symbols count in article: 6.3k Reading time ≈ 14 mins.

A 吃了发罚时……

赛时进度：ABCDE Accepted，Score：6025，Rank：7，Rating：1987 -> 2189。

改题进度：All Accepted。

A

题意：给定 $n$，拆分成 4 和 6，问最多有多少个 4、最多有多少个 6，或报告无解。

容易发现 $n$ 是奇数或 $n = 2$ 的时候显然无解。剩下的按余数那么随便分讨一下即可。

1
2
3
4
5
6
7
8
9
10
void work()
{
	LL n;
	scanf("%lld", &n);
	if ((n & 1) || n < 4) return void(puts("-1"));
	if (n % 6 == 2) printf("%lld ", n / 6 + 1);
	else printf("%lld ", (n + 2) / 6);
	if (n % 4 == 2) printf("%lld\n", n / 4);
	else printf("%lld\n", n / 4);
}

B

题意：给定一个序列 $n$ 和 $q$ 次操作，单点修改或是整体赋值。问操作后的和。$n\leq 2\times 10 ^ 5, q\leq 2\times 10 ^ 5$。

给出线性做法。

考虑每个数最后被覆盖 / 单点修改的时间，如果单点修改的时间晚于整体赋值的时间，那么就是 $a_i$，否则值就是最后的 $cov$。用增量法维护和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
	std::cin >> n >> Q;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++ i) sum += a[i];
	int pos, x, op;
	for (int cs = 1; cs <= Q; ++ cs) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d %d", &pos, &x);
			if (t[pos] < ct) sum += x - cov;
			else sum += x - a[pos];
			t[pos] = cs, a[pos] = x;
		} else {
			scanf("%d", &x);
			sum = (LL) n * x;
			cov = x, ct = cs;
		}
		printf("%lld\n", sum);
	}
	return 0;
}

C

给出 $n\times n$ 的方格，有些位置有关键点，$q$ 次操作，设立关键点，删除关键点，询问一个子矩阵所有的格子都被关键点所覆盖。覆盖是将一行 / 一列的点覆盖。$n, q\leq 2\times 10 ^ 5$。

考虑结论：想要覆盖一个子矩阵，当且仅当所有行 / 所有列都被覆盖。

于是我们可以将 行 / 列 分开，分别判断 行 / 列 是否分别合法，一个合法就都可以了。

于是随便使用树状数组判断区间是否合法即可。具体的，如果覆盖的时候这个位置覆盖次数为 0，就在这个位置 +1；如果删除后这个位置覆盖次数为 0，就在这个位置 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
	int n, Q, t, x, y, sx, sy;
	std::cin >> n >> Q;
	while (Q --) {
		scanf("%d %d %d", &t, &x, &y);
		if (t == 1) row.add(x, !r[x] ++), col.add(y, !c[y] ++);
		else if (t == 2) row.add(x, -(!-- r[x])), col.add(y, -(!-- c[y]));
		else {
			scanf("%d %d", &sx, &sy);
			puts((row.ask(sx) - row.ask(x - 1)) == sx - x + 1 || (col.ask(sy) - col.ask(y - 1)) == sy - y + 1 ? "Yes" : "No");
		}
	}
	return 0;
}

D

给出 $n$ 个点 $m$ 条边的有向图，点带权，任选点数为 $k$ 的路径使得最大点权最小。$n, m\leq 2\times 10 ^ 5, k\leq 10 ^ {18}$。

最大最小，果断二分。

二分后，有一些点不再能走，那么转化为了在现有图上走出 $k$ 个点。

首先容易发现如果有环的话，那么任意 $k$ 都是可以的。对于剩下的情况，直接拓扑排序做一下最长路径即可。拓扑排序的时候可以同时判断有没有环。判断时间复杂度线性。

总复杂度 $O((n + m)\log a)$。

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
bool check(int mid)
{
	std::queue<int> q;
	for (int i = 1; i <= n; ++ i) deg[i] = d[i] = 0;
	for (int x = 1; x <= n; ++ x) {
		if (a[x] > mid) continue;
		for (int v : g[x])
			if (a[v] <= mid) deg[v] ++;
	}
	for (int i = 1; i <= n; ++ i)
		if (!deg[i] && a[i] <= mid) q.push(i), d[i] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int v : g[x])
			if (a[v] <= mid) {
				chkmax(d[v], d[x] + 1);
				if (!-- deg[v]) q.push(v);
			}
	}
	for (int i = 1; i <= n; ++ i)
		if (deg[i] || d[i] >= k) return true;
	return false;
}
 
int main()
{
	std::cin >> n >> m >> k;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1, u, v; i <= m; ++ i) {
		scanf("%d %d", &u, &v);
		g[u].pb(v);
	}
	if (!check(1e9 + 10)) return puts("-1"), 0;
	int l = 0, r = 1e9 + 10;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	std::cout << l << std::endl;
	return 0;
}

E

题意：给定长度为 $n$ 的字符串，满足每一个都属于 $\{a, b, c\dots, p, q\}$ 17 个字符，有一些待填，用 ? 表示，$q$ 次给定可以将 ? 变成的字符的集合，问所有填法回文串个数的和。$n\leq 1000, q\leq 2\times 10 ^ 5$。

容易发现 $n\leq 1000$，我们可以考虑枚举出所有可能的回文串，然后判断是否可能变为回文串。注意我们需要增量枚举，否则是 $O(n ^ 3)$ 的。

考虑现在新加入的两边字符：

  1. 两边都是 ?，这样答案就乘上 $|\sum|$。这样我们还需要枚举 $\sum$ 的大小贡献答案。
  2. 有一边是 ?，这样字符集中需要有另一边的字符。
  3. 两边都不是 ?，这样需要两边字符一样，否则直接停止。

此外，其他的 ? 可以随便选，那么我们需要给出随意选的个数。容易发现贡献和 $|\sum|$ 有关，所以再枚举 $|\sum|$，这样我们需要在包含当前需要的字符集的字符集位置加上 $cnt ^ {|\sum|}$。这个可以使用 FMT 简单的实现。于是总时间复杂度 $O(|\sum| ^ 22 ^ {|\sum|} + n ^ 2|\sum|)$。

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
int main()
{
	scanf("%d%s", &n, str + 1);
	for (int j = 1; j <= 17; ++ j)
		for (int i = pw[j][0] = 1; i <= n; ++ i) pw[j][i] = (LL) pw[j][i - 1] * j % Mod;
	int totcnt = 0;
	for (int i = 1; i <= n; ++ i) totcnt += str[i] == '?';
	for (int mid = 1; mid <= n; ++ mid) {
		int len = 0, sta = 0, cnt = 0, excnt = totcnt;
		while (mid > len && mid + len <= n) {
			int i = mid - len, j = mid + len;
			if (str[i] != '?' && str[j] != '?') {
				if (str[i] != str[j]) break;
			} else if (str[i] == '?' && str[j] == '?') cnt ++;
			else sta |= 1 << ((str[i] == '?' ? str[j] : str[i]) - 'a');
			excnt -= (str[i] == '?') + (str[j] == '?');
			if (i == j && str[i] == '?') excnt ++;
			// printf("1 : %d %d %d %d\n", mid, len, cnt, sta);
			for (int j = 1; j <= 17; ++ j) adj(ans[j][sta] += pw[j][cnt + excnt] - Mod);
			len ++;
		}
	}
	for (int mid = 1; mid <= n; ++ mid) {
		int len = 1, sta = 0, cnt = 0, excnt = totcnt;
		while (mid >= len && mid + len <= n) {
			int i = mid - len + 1, j = mid + len;
			if (str[i] != '?' && str[j] != '?') {
				if (str[i] != str[j]) break;
			} else if (str[i] == '?' && str[j] == '?') cnt ++;
			else sta |= 1 << ((str[i] == '?' ? str[j] : str[i]) - 'a');
			// printf("2 : %d %d %d %d\n", mid, len, cnt, sta);
			excnt -= (str[i] == '?') + (str[j] == '?');
			for (int j = 1; j <= 17; ++ j) adj(ans[j][sta] += pw[j][cnt + excnt] - Mod);
			len ++;
		}
	}
	for (int j = 1; j <= 17; ++ j) FMT(ans[j]);
	std::cin >> Q;
	while (Q --) {
		scanf("%s", tmp + 1);
		int sta = 0;
		for (int j = 1; tmp[j]; ++ j) sta |= 1 << (tmp[j] - 'a');
		printf("%d\n", ans[popcount(sta)][sta]);
	}
	return 0;
}

F

题意：给定长度为 $n$ 仅包含 $0\sim 9$ 的字符串相同，给定 $m$ 个交换，相邻两个出现在里面时可以交换。如果两个字符串可以互相交换得到，则称两个字符串相同。问本质不同的字符串有多少个。$n\leq 50000$。

首先我们定义代表元为本质相同的字符串中字典序最小的。这样，如果我们存在满足中间某些位是 $(d_1, d_2, d_3\dots, d_k)$ 并且 $(d_i, d_{i + 1})$ 中间可以交换，$d_1 > d_k$，那么这个字符串就不是最小的。记录前面可以互相交换的 $d_1,\dots, d_k$，如果存在一个 $d$ 满足 $d > nxt$ 并且 $nxt$ 中可以有转移 $(d, nxt)$，那么加入 $nxt$ 之后就不是最小的了。（注意前面的都可以放到 $d_k$ 这个位置来和 $nxt$ 交换，如果存在 $d > nxt$，可以将 $nxt$ 交换到 $d_k$ 的位置，$d$ 交换到 $nxt$ 的位置，就不是最小的

注意到我们只需要哪些元素出现没有，并不需要出现的次数及顺序。于是直接状压，将 $sta$ 记作前面 $d_1\dots, d_k$ 的并集。转移的时候观察存在 $(nxt, d)$ 且 $nxt < d$ 的 $nxt$ 无法转移，其余均可。转移到的就是 $sta$ 中能和 $nxt$ 交换的数和 $nxt$ 本身。判断大于的有没有记录一下大于 $nxt$ 的所有转移，压一下状态即可。

时间复杂度 $O(n|\sum|2 ^ {|\sum|})$，可以通过。

注意寻找代表元的做法统计本质不同个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
	std::cin >> n >> m;
	for (int i = 1, u, v; i <= m; ++ i)
	{
		std::cin >> u >> v;// assert(u < v);
		A[u] |= 1 << v, B[u] |= 1 << v, A[v] |= 1 << u;
	}
	for (int i = 0; i < 10; ++ i) f[1][1 << i] = 1;
	for (int i = 2; i <= n; ++ i) {
		for (int s = 0; s < S; ++ s) f[i & 1][s] = 0;
		for (int s = 0, cur; s < S; ++ s) {
			if (!(cur = f[(i - 1) & 1][s])) continue;
			for (int nxt = 0; nxt < 10; ++ nxt)
				if (!(B[nxt] & s)) adj(f[i & 1][(A[nxt] & s) | (1 << nxt)] += cur - Mod);
		}
	}
	int res = 0;
	for (int i = 0; i < S; ++ i) adj(res += f[n & 1][i] - Mod);
	std::cout << res << std::endl;
	return 0;
}