mydcwfy's Blog

ARC Round#132

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

vp 的时候降智了，简单的 D 题没做出来，被吊锤了。

赛时进度：ABC Accepted，Score：1400，Penalty：83：02。

改题进度：ABCDF Accepted。

A

题意：给定 $n\times n$ 的矩阵，已知每行有 $r_i$ 个 1，每列有 $c_i$ 个 1，且 $r, c$ 均为排列。$q$ 次询问某个点是否是 1。$n, m\leq 10 ^ 5$。

如果我们需要构造的话，那么 $r_i = n, c_j = n$ 的行列是可以全部赋值为 1 的，然后 $r_i = 1, c_j = 1$ 的行列除了已赋值的全部赋值为 0，然后 $r_i = n - 1, c_j = n - 1$……

这样行列相当于是一个要将他赋值为 1，一个需要将他赋值为 0，就看谁的优先级高。假设询问 $(x, y), r_x > c_y$，容易发现行的优先级可以用 $n - r_x$，列的优先级可以用 $c_y$，这样行的优先级小于等于列的优先级那么就是 1，否则是 0。

整理一下，就是 $n - r_x\leq c_y$，即 $r_x + c_y\geq n$。

1
2
3
4
5
6
7
8
9
int main()
{
    while (Q --) {
		scanf("%d %d", &x, &y);
		int mn = std::min(a[x], b[y]), mx = std::max(a[x], b[y]);
		if (mn - 1 < n - mx) putchar('.');
		else putchar('#');
	}
}

B

题意：给定一个排列 $p_{1, \dots, n}$，每次可以将第一个数移到最后，或是反转整个数列，问至少多少次才能变为 $1, 2, \dots, n$。给出的排列保证可以变为 $1, 2, \dots, n$。$n\leq 10 ^ 5$。

如果将原序列看作是一个环的话，那么环的本质没有变，这样序列一定就是 $x, x - 1, \dots, 1, n, n - 1, \dots, x + 1$ 或者是 $x, x + 1, \dots, n, 1, 2, \dots, x - 1$。

下面用 $pos$ 表示 1 的位置。

对于第一种情况，我们必须翻转，如果最开始就翻转的话，那么答案就是 $n - pos + 1$，如果是最后翻转的话，答案就是 $(n - pos) + 1$，二者取 $\min$ 即可。

对于第二种情况，我们可以不翻转，答案就是 $pos - 1$，也可以翻转两次（一次最先，一次最后），答案就是先到 $(n - pos + 1) + 2$，二者取 $\min$ 即可。可以自己手玩一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) scanf("%d", p + i);
	for (int i = 1; i <= n; ++ i) nw[p[i]] = i;
	if (n == 1) return puts("0"), 0;
	int flag = -1;
	for (int i = 1; i <= n; ++ i)
		if (p[(i + n - 2) % n + 1] != 1 && p[i] != 1) {
			if (!~flag) flag = p[i] > p[(i + n - 2) % n + 1];
			else assert(flag == (p[i] > p[(i + n - 2) % n + 1]));
		}
	// std::cout << flag << std::endl;
	if (flag == 1) printf("%d\n", std::min(nw[1] - 1, 3 + n - nw[1]));
	else printf("%d\n", std::min(n - nw[1] + 1, nw[1] + 1));
	return 0;
}

C

题意：给定 $n, d$，求满足 $|p_i - i|\leq d$ 的排列的数量，某些 $p_i$ 确定，未确定用 -1 表示。$n\leq 500, d\leq 5$。

排列的 DP 一般有两种：第一种是按顺序填入，哪个位置填 $n$，哪个位置填 $n - 1$，类推。还有一种是先将前 $i$个构成排列，然后枚举 $i + 1$ 的数 $x$，将前面原来 $\geq x$ 的数加 1。

如果方向选的是第二种的话，这道题就不好做，因为你需要维护前 5 个的数分别是什么，这样才能判断 +1 后是否合法。

而用第一种就体现出优势了：我们只需要维护和这个数距离不超过 5 的位置是否已经有数即可。这样就很好做了，时间复杂度 $O(nd2 ^ {2d})$，可以通过。

代码有些繁琐，有一点难写。

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
int main()
{
	std::cin >> n >> d;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++ i)
		if (~a[i]) nw[a[i]] = i;
	int sta = 0, lim = d << 1 | 1;
	for (int j = 0; j < lim; ++ j)
		if (j > d || ~a[n + j - d]) sta |= 1 << j;
	f[n + 1][sta] = 1;
	for (int i = n + 1; i > 1; -- i)
		for (int s = 0; s < (1 << lim); ++ s) {
			if (!f[i][s]) continue;
			int cur = f[i][s];
			// printf("%d %d %d\n", i, s, cur);
			if (nw[i - 1]) {
				int to = nw[i - 1] - i + 2 + d;
				int &trs = f[i - 1][((s << 1) | (1 << to) | (i <= d + 2 || ~a[i - d - 2])) & ((1 << lim) - 1)];
				adj(trs += cur - Mod);
				continue;
			}
			for (int nxt = 0; nxt < lim; ++ nxt) {
				if (s >> nxt & 1) continue;
				// printf("Trs %d\n", nxt);
				int &trs = f[i - 1][((s << 1) | (1 << (nxt + 1)) | (i <= d + 2 || ~a[i - d - 2])) & ((1 << lim) - 1)];
				adj(trs += cur - Mod);
			}
		}
	std::cout << f[1][(1 << lim) - 1] << std::endl;
	return 0;
}

D

题意：给定两个长度相同、1 个数相同的串 $s, t$，定义 $d(s, t)$ 为最少邻项交换的次数。定义一个字符串的权值为相邻字符相同的个数。求所有满足 $d(s, t) = d(s,u) + d(u, t)$ 中 $u$ 的最大权值。$|s|\leq 3\times 10 ^ 5$。

sb 贪心题。

容易发现 $u$ 的第 $i$ 个 1 一定在 $s$ 的第 $i$ 个 1 和 $t$ 的第 $i$ 个 1 之间。那么我们如果前面已经填好了，新加入一个字符我们就可以判断新的是否合法。注意还需要判断 0 是否合法，即 $u$ 的 0 在 $s$ 对应的 0 和 $t$ 对应的 0 之间。

剩下的直接贪心，考虑如果能和前一个相同就填相同的，否则就填不同的。注意第一个位置无法填入，随便枚举一下即可。

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
int solve(int st)
{
	auto valid = [&](int pos, int x) {
		if (x < std::min(cnta[pos], cntb[pos]) || x > std::max(cnta[pos], cntb[pos]))
			return false;
		return x + (n + m - pos) >= cnta[n + m] && x <= cnta[n + m];
	};
	if (a[1] != st + '0' && b[1] != st + '0') return 0;
	int cnt = st, ls = st, res = 0;
	// printf("Solve %d\n", st);
	for (int i = 2; i <= n + m; ++ i)
	{
		// printf("%d %d %d\n", cnt, cnta[i - 1], cntb[i - 1]);
		if (valid(i, cnt + ls)) cnt += ls, res ++;
		else cnt += !ls, ls = !ls;
	}
	// printf("%d %d %d\n", cnt, cnta[n + m], cntb[n + m]);
	// puts("");
	return res;
}

int main()
{
	std::cin >> n >> m >> (a + 1) >> (b + 1);
	for (int i = 1; i <= n + m; ++ i) cnta[i] = cnta[i - 1] + (a[i] ^ 48);
	for (int i = 1; i <= n + m; ++ i) cntb[i] = cntb[i - 1] + (b[i] ^ 48);
	printf("%d\n", std::max(solve(0), solve(1)));
	return 0;
}

F

见 ARC132F。