ARC Round#140

赛时没做出来 D，结果似乎比较简单……

赛时进度：ABC Accepted，Penalty：59：56，Rank：291，Rating：1995 -> 2006。

改题进度：ABCDE Accepted。

A

题意：给定字符串 $S$ ，可以修改其中的 $k$ 个字符，问可以得到的最小循环节。 $| S | \leq 2000$ 。

直接暴力枚举循环节是否合法，这样每一个对应的位置需要变成一个字符，统计众数出现次数即可。计算众数的时候可以做到线性。

由于循环节最多只有 $O (\sqrt{n})$ 种，所以得到时间复杂度 $O (n \sqrt{n})$ 。

int solve(int st, int d)
{
	int res = 0;
	for (int i = st; i <= n; i += d) chkmax(res, ++ cnt[s[i] - 'a']);
	for (int i = st; i <= n; i += d) -- cnt[s[i] - 'a'];
	// printf("%d %d %d\n", st, d, res);
	return res;
}

int main()
{
	std::cin >> n >> k >> (s + 1);
	for (int i = 1; i <= n; ++ i) {
		if (n % i) continue;
		int res = n;
		for (int j = 1; j <= i; ++ j) res -= solve(j, i);
		if (res <= k) printf("%d\n", i), exit(0);
	}
	return 0;
}

B

题意：给定只有 A、R、C 的字符串，奇数次操作可以 ARC -> R，偶数次操作可以 ARC -> AC，问最多可以进行的操作次数。 $| S | \leq 2 \times 10^{5}$ 。

容易发现我们每一段是独立的，因为 ARC -> AC 后两边都不能再合并，只有 AA...ARC...CC 可以通过只有奇数次变换可以得到 ARC，最后一次任选。

这样我们可以将原串的有用部分压缩为 AA...ARC...CC 中 $min {l e n_{A}, l e n_{C}}$ ，容易发现这一定是可以的，多出来的部分是无法操作的。

这样奇数操作就是对数列中的一个非零数 -1，偶数操作就是将一个非零数变为 0。问最多多少次操作。

这其实是可以贪心的：我每次将尽量靠近 1 又不是 1 的一个数用奇数操作，直到他变成 1，这样偶数操作删除这个数的时候代价是最小的。我赛时的代码就是这个。

考虑两个上界：

偶数次操作最多只有 ARC出现的次数，因为一个偶数次一定会消耗一个 ARC 而不会再次出现。
总操作最多只有压缩后数列的和，因为操作一次，至少会减 1。

从偶数操作容易推出所有操作的一个上界： $2 \times c n t$ （不可能最后一次是一个奇数操作，因为这样的话，我们预估的 $c n t$ 就可以 +1

直接取 $min$ 即可。代码是贪心，时间复杂度 $O (n \log n)$ 。

int main()
{
	scanf("%d%s", &n, s + 1);
	for (int i = 1; i <= n; ++ i) {
		if (s[i] ^ 'R') continue;
		int len = 1;
		while (i > len && i + len <= n && s[i - len] == 'A' && s[i + len] == 'C') len ++;
		if (len > 2) al.push_back(len - 1);
		else cnt += len == 2;
	}
	std::sort(al.begin(), al.end());
	sz = al.size();
	int ans = 0, i = 0, j = 0;
	while (1) {
		++ ans;
		if (ans & 1) {
			while (i < sz && al[i] <= 1) ++ i;
			if (i >= sz) break;
			al[i] --;
		} else {
			if (cnt) {
				-- cnt;
				continue;
			}
			if (j >= sz) {
				break;
			}
			al[j ++] = 0;
		}
	}
	-- ans;
	int cur = 0;
	for (int &x : al) assert(x >= 0 && x <= 1), cur += x;
	printf("%d\n", ans + cur + cnt);
	return 0;
}

C

题意：给定 $n, x$ ，要求构造长度为 $n$ 的排列 $p$ 使得 $p_{1} = x$ 且 $a_{i} = | p_{i} - p_{i + 1} |$ 序列的最长严格上升子序列最大。

首先，如果不管 $p_{1}$ 的话，我们有一个最长上升字符列为 $n - 2$ 的答案。如果 $n$ 是偶数，我们构造即为 ${\frac{n}{2}, \frac{n}{2} + 1, \frac{n}{2} - 1, \frac{n}{2} + 2 \dots}$ 或 ${\frac{n}{2} + 1, \frac{n}{2}, \frac{n}{2} + 2, \frac{n}{2} - 1 \dots}$ ，相邻两个差是 ${1, 2, \dots}$ ，这达到了上界。如果是奇数，构造即为 ${\frac{n + 1}{2}, \frac{n + 1}{2} + 1, \frac{n + 1}{2} - 1, \frac{n + 1}{2} + 2 \dots}$ ，容易证明这个也是达到了上界的。

现在考虑加入 $p_{1} = x$ 。第一种方案是我们不管 $p_{1}$ ，后面原来 $\geq x$ 的加 1 即可。第二种方案是我们先将 $p_{1}$ 按照上面的构造尽可能摆放，剩下的随便摆。容易发现如果 $x$ 不是上面最优情况的开头，第二个一定不优。

剩下的随便分类讨论即可。

int main()
{
	std::cin >> n >> x;
	if (n & 1 && x == (n + 1) / 2) {
		printf("%d ", x);
		for (int i = 2, j = (n + 1) / 2 - 1, k = (n + 1) / 2 + 1; i <= n; ++ i)
			if (i & 1) printf("%d ", k ++);
			else printf("%d ", j --);
		return 0;
	} else if (!(n & 1) && x == n / 2) {
		printf("%d ", x);
		for (int i = 2, j = n / 2 + 1, k = n / 2 - 1; i <= n; ++ i)
			if (!(i & 1)) printf("%d ", j ++);
			else printf("%d ", k --);
		return 0;
	} else if (!(n & 1) && x == n / 2 + 1) {
		printf("%d ", x);
		for (int i = 2, j = n / 2 + 2, k = n / 2; i <= n; ++ i)
			if (i & 1) printf("%d ", j ++);
			else printf("%d ", k --);
		return 0;
	}
	if (n & 1) {
		for (int i = 2, j = n / 2 + 1, k = n / 2; i <= n; ++ i)
			if (i & 1) p[i] = j ++;
			else p[i] = k --;
	} else {
		for (int i = 2, j = n / 2 + 1, k = n / 2; i <= n; ++ i)
			if (!(i & 1)) p[i] = k --;
			else p[i] = j ++;
	}
	printf("%d ", x);
	for (int i = 2; i <= n; ++ i) printf("%d ", p[i] + (p[i] >= x));
	return 0;
}

D

题意：给定一个无向图， $i$ 会和 $x_{i}$ 连边，有些 $x_{i}$ 未定，问所有可能的 $x_{i}$ 无向图连通块个数之和。 $n \leq 2000$ 。

观察 1：容易发现确定 $x_{i}$ 后的图一定是基环树森林，连通块的个数就是环的个数（包括自环）

观察 2：还没有形成基环树的连通块一定是树，每棵树中 $x_{i}$ 不确定的点有且只有 1 个。

观察 3：一旦形成了环，这个连通块的贡献就固定了，和其他的有没有联通过来没有关系（因为统计的是环的数量）

有了上面的发现，其实就比较好做了。

首先如果我们确定了 $k$ 棵树，总共有 $c n t$ 个点 $x_{i}$ 未确定，每棵的大小为 $a_{i}$ ，互相连接，并形成了环，那么对应的贡献应该是

(k - 1)! n^{c n t - k} \prod_{i = 1}^{k} a_{i}

发现答案和 $k$ 和 $\prod$ 有关，那么直接考虑 DP，即目前个数为 $k$ 的所有树的组合的乘积和。直接 $O (n^{2})$ 转移即可。

对于原来就是基环树的，我们已经形成了环，不参加 DP，直接贡献为 $n^{c n t}$ 。加和即可，时间复杂度 $O (n^{2})$ 。

void dfs(int x, int fa = 0)
{
	vis[x] = 1, sz ++;
	for (int v : g[x])
		if (v ^ fa) {
			if (vis[v]) {
				flag = 1;
				continue;
			}
			dfs(v, x);
		}
}

int main()
{
	std::cin >> n;
	fact[0] = 1;
	for (int i = 1; i <= n; ++ i) fact[i] = (LL) fact[i - 1] * i % Mod;
	for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++ i) {
		if (!~a[i]) continue;
		g[a[i]].pb(i), g[i].pb(a[i]);
	}
	int excnt = 0, res = 0, mul;
	for (int i = 1; i <= n; ++ i) excnt += !~a[i];
	mul = qpow(n, excnt);
	std::vector<int> vad;
	for (int i = 1; i <= n; ++ i) {
		if (vis[i]) continue;
		sz = 0, flag = 0, dfs(i);
		if (flag) {
			adj(res += mul - Mod);
			continue;
		}
		vad.pb(sz);
	}
	int cnt = vad.size();
	f[0] = 1;
	for (int x : vad)
		for (int j = cnt - 1; ~j; -- j)
			if (f[j]) f[j + 1] = (f[j + 1] + (LL) f[j] * x) % Mod;
	for (int i = 1; i <= cnt; ++ i)
		if (f[i]) res = (res + (LL) f[i] * qpow(n, cnt - i) % Mod * fact[i - 1]) % Mod;
	std::cout << res << std::endl;
	return 0;
}

E

题意：构造 $n \times m$ 的网格，每个数在 $[1, 25]$ ，要求 $\forall x_{1}, x_{2} \in [1, n], y_{1}, y_{2} \in [1, m]$ ， $a_{x_{1}, y_{1}}, a_{x_{1}, y_{2}}, a_{x_{2}, y_{1}}, a_{x_{2}, y_{2}}$ 不全相等。 $n, m \leq 500$ 。

不是很好构造，虽然代码不超过 20 行：

const int B = 23;

int main()
{
	int n, m;
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i, puts(""))
		for (int j = 1; j <= m; ++ j) printf("%d ", ((i / B) * (j / B) + i + j) % B + 1);
	return 0;
}

看到 $25$ 和 $\sqrt{n}$ 同级，果断分块。

暂定为 $\sqrt{n} \times \sqrt{n}$ 的分块，那么需要考虑块内和块间的不同情况。

块内的话，需要我们每两个相同的数字得不在一行一列，否则同行 / 列的块内可能会出现对应的情况导致不合法。

既然不在一行一列，这要求我们需要每行每列都是排列，这样的话，我们按照如下构造即可：

[\begin{matrix} 1 & 2 & 3 & \dots & 22 & 23 \\ 2 & 3 & 4 & \dots & 23 & 1 \\ 3 & 4 & 5 & \dots & 1 & 2 \\ \dots & \dots & \dots & \dots & \dots & \dots \\ 23 & 1 & 2 & \dots & 21 & 22 \end{matrix}]

那么块间像块内一样是否合法呢？、

首先看 $B = 3, n = m = 9$ 的示范样例输出：

1 2 1 2 3 2 3 1 
2 3 2 3 1 3 1 2 
3 1 3 1 2 1 2 3 
2 3 2 3 1 3 1 2 
3 1 3 1 2 1 2 3 
1 2 1 2 3 2 3 1 
3 1 3 1 2 1 2 3 
1 2 1 2 3 2 3 1 
2 3 2 3 1 3 1 2 

容易发现第 4 行和第 2 行是一样的，是怎么回事呢？

我们发现，当第 1 行变为第 4 行的时候，我们将 1 2 3 的排列变成了 2 3 1，变为第 2 行的时候也是这样，导致第 2 行的输出和第 4 行完全相同。

这启示我们需要找到另外的方式，使得不会产生不合法情况。

给出结论：使用块行编号和纵编号的乘积。

手玩一下发现是不会冲突的。于是就是上面的那个代码（别问我是怎么~~看题解~~想到的