2023 年 5 月做题记录

2023-05-12

题解/做题记录

7.5k 词

感觉最近越来越摆了。

所以打算记录一下做到的好题。

联合省选 2023 Day1 T2 城市建造

称额外修建的道路连接的城市为标记点，容易发现任意两个标记点之间的边都必须是额外修建的道路。

题目要求在删除新增的道路后任意两个标记点不连通，所以对于任意一个点双，如果标记了两个点，则必须标记其余所有点。
关于为什么不是边双：

然后进一步观察发现，删除的点双必须是连通的。

于是考虑建圆方树 DP。

然后求助了 djwj233。

首先对于 $k = 0$ ，块的大小必须是 $n$ 的因数，只有 $O(\sqrt{n})$ 个。
对于 $k = 1$ ，块的大小只可能是 $\left\lfloor\dfrac{n}{s}\right\rfloor$ 或 $\left\lceil\dfrac{n}{s}\right\rceil$ （其中 $s$ 为任意正整数），简单分析发现也只有 $O(\sqrt{n})$ 种。
于是可以考虑枚举块的大小 $B$ ，再进行 DP。

我们发现树上连通块一定有一个深度最小的点，且其他点都在它的子树内。
于是考虑再在这个点上统计答案。

我们设 $dp_i$ 表示仅考虑以 $i$ 为根的子树，且 $i$ 为标记点的方案数。如果我们强制根是圆点，则可以产生贡献的点一定是圆点。

我们分别讨论当前点 $u$ 为方点和圆点的情况。

对于方点，其是标记点，显然其每个儿子都是标记点，故：

dp_u = \prod\limits_{v \text{ is a son of } u} dp_v

对于圆点，再分讨其儿子 $v$ 的子树的情况。

若 $siz_v < B$ ，则其必定与 $u$ 放在一起。
若 $siz_v = B$ ，在 $k = 0$ 的时候与下一种情况相同。在 $k = 1$ 的时候，其可以与根一起组成一个连通块，要求是不能有剩下的多余的点，及第一种情况的子树和祖先的那一块。
若 $siz_v > B$ ，则 $v$ 必须被标记。

故有：

dp_u = \prod\limits_{v \text{ is a son of } u, siz_v > B} dp_v

接下来的问题就是什么时候可以统计答案。
显然是剩余的点恰好为 $B$ 或 $B + 1$ 的时候。
对应一般情况和可以与某一个大小恰好为 $B$ 的子树组合成一个连通块的情况。

另外，对于第二种情况的方案数：

\sum\limits_{v \text{ is a son of } u, siz_v = B} \prod\limits_{w \text{ is a son of } u, w \ne v} dp_w

考虑怎么统计这个东西。
我们考虑将贡献拆成两部分，对于满足 $siz_v = B$ 的点 $v$ 统计其之前扫到的 $w$ 对它的贡献，对于满足 $siz_w \ge B$ 的点 $w$ 统计其对之前的 $v$ 的贡献。（这里用 $v$ 和 $w$ 分别表示两种节点，下同。）
对于当前点 $v$ ，所有在它之前被扫到的 $w$ 的总贡献就是当前的 $dp_u$ 。
对于当前点 $w$ ，相当于要之前的所有点的贡献都乘上 $dp_w$ ，也就是当前的总贡献乘上 $dp_w$ 。

// Think twice, code once.
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int mod = 998244353;

int n, m, k, cnt;
template<int N, int M>
struct graph {
	int tot, hd[N];
	int nxt[M], to[M];

	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return ;
	}
};
graph<100005, 400005> g;
graph<200005, 400005> tr;
int timer, dfn[100005], low[100005];
stack<int> s;
int ans, res, siz[200005], dp[200005], vis[200005];

void Tarjan(int now) {
	dfn[now] = low[now] = ++timer;
	s.push(now);
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (!dfn[g.to[i]]) {
			Tarjan(g.to[i]);
			low[now] = min(low[now], low[g.to[i]]);
			if (low[g.to[i]] == dfn[now]) {
				cnt++;
				for (int x = 0; x != g.to[i]; s.pop()) {
					x = s.top();
					tr.add(cnt, x);
					tr.add(x, cnt);
				}
				tr.add(cnt, now);
				tr.add(now, cnt);
			}
		} else low[now] = min(low[now], dfn[g.to[i]]);
	return ;
}
void getSize(int now, int fa) {
	siz[now] = (now <= n);
	for (int i = tr.hd[now]; i; i = tr.nxt[i])
		if (tr.to[i] != fa) getSize(tr.to[i], now), siz[now] += siz[tr.to[i]];
	return ;
}
void dfs1(int now, int fa, const int &B) {
	if (now > n) {
		dp[now] = 1;
		for (int i = tr.hd[now]; i; i = tr.nxt[i])
			if (tr.to[i] != fa) dfs1(tr.to[i], now, B), dp[now] = (long long)dp[now] * dp[tr.to[i]] % mod;
		return ;
	}
	dp[now] = 1;
	int sum = 1;
	for (int i = tr.hd[now]; i; i = tr.nxt[i])
		if (tr.to[i] != fa) {
			if (siz[tr.to[i]] < B) {sum += siz[tr.to[i]]; continue;}
			dfs1(tr.to[i], now, B);
			dp[now] = (long long)dp[now] * dp[tr.to[i]] % mod;
		}
	if (n - (siz[now] - sum) == B) res = (res + dp[now]) % mod;
	dp[now] *= (sum == B);
	return ;
}
void dfs2(int now, int fa, const int &B) {
	if (now > n) {
		dp[now] = 1;
		for (int i = tr.hd[now]; i; i = tr.nxt[i])
			if (tr.to[i] != fa) dfs2(tr.to[i], now, B), dp[now] = (long long)dp[now] * dp[tr.to[i]] % mod;
		return ;
	}
	dp[now] = 1;
	int sum = 1, num = 0;
	for (int i = tr.hd[now]; i; i = tr.nxt[i])
		if (tr.to[i] != fa) {
			if (siz[tr.to[i]] < B) {sum += siz[tr.to[i]]; continue;}
			dfs2(tr.to[i], now, B);
			num = (long long)num * dp[tr.to[i]] % mod;
			if (siz[tr.to[i]] == B) num = (num + dp[now]) % mod;
			dp[now] = (long long)dp[now] * dp[tr.to[i]] % mod;
		}
	if (n - (siz[now] - sum) == B || n - (siz[now] - sum) == B + 1) res = (res + dp[now]) % mod;
	if (now == 1 && sum == 1) res = (res + num) % mod;
	dp[now] *= (sum == B || sum == B + 1);
	dp[now] += num * (sum == 1);
	return ;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g.add(u, v);
		g.add(v, u);
	}
	cnt = n;
	Tarjan(1);
	getSize(1, 0);
	if (k == 0) {
		for (int i = 1; i < n; i++)
			if (n % i == 0) {
				res = 0;
				memset(dp, 0, sizeof(dp));
				dfs1(1, 0, i);
				ans = (ans + res) % mod;
			}
	} else {
		for (int i = 1; i <= n - 2; i++) {
			if (n % i > n / i) continue;
			res = 0;
			memset(dp, 0, sizeof(dp));
			dfs2(1, 0, i);
			ans = (ans + res) % mod;
			vis[i]++, vis[i + 1]++;
		}
		for (int i = 1; i <= n - 2; i++)
			if (vis[i] >= 2) {
				res = 0;
				memset(dp, 0, sizeof(dp));
				dfs1(1, 0, i);
				ans = (ans - res + mod) % mod;
			}
	}
	printf("%d\n", ans);
	return 0;
}

[Ynoi2010] Fusion Tree

Trick：对于关于树上与某节点相连的点的操作或询问，可以考虑先变成有根树然后把操作分成对父亲和对儿子。对父亲暴力修改，对儿子用数据结构维护。

考虑到求异或值，使用 01Trie 维护。

对于 $+1$ 操作，我们让 01Trie 从低位到高位维护，则 $+1$ 相当于交换左右儿子并递归处理交换后的左儿子。

AGC033D Complexity

考虑暴力：设 $dp_{u, d, l, r}$ 表示仅考虑 $(u, l)$ 到 $(d, r)$ 的矩形的答案。枚举最后一次操作转移。

容易发现答案最大为 $\left\lceil\log_2 n\right\rceil + \left\lceil\log_2 m\right\rceil$ ，于是考虑交换答案和状态。
即设 $dp_{o, u, d, l}$ 表示答案为 $o$ 时，以 $(u, l)$ 和 $(d, l)$ 为左上角和左下角的矩形的右边界最大是多少。

依然考虑枚举最后一次操作。

如果是输着切，则：

dp_{o, u, d, l} = dp_{o - 1, u, d, dp_{o - 1, u, d, l} + 1}

如果是横着切，则：

dp_{o, u, d, l} = \max\limits _ {k = u} ^ d \min\{dp_{o - 1, u, k, l}, dp_{o - 1, k + 1, d, l}\}

容易发现当 $o, u, l$ 不变时，随着 $d$ 的增加，最优决策点不降。于是可以将其优化到 $O(\log (n + m) n^2m)$ 。

洛谷 P9374 「DROI」Round 2 单图

6 月才更新五月做题记录，不亏是我（

容易发现单图中不能存在三个点按顺序连在一起的情况：

但是我们发现二元环是合法的：

于是我们可以得到：单图的每一个连通块都是一个单独的点或一个二元环或一个有向二分图（即一部分点向另一部分点连边，且每部分内部无连边）。

考虑分开来统计这些东西。

二元环是好统计的，我们设 $f_i$ 表示 $i$ 个点组成的二元环的方案数，显然有：

f _ i = \left\{ \begin{array}{ll} f _ {i - 2} \cdot (i - 1) & i \equiv 0 \pmod{2} \\ 0 & i \equiv 1 \pmod{2} \end{array} \right.

剩下的就是单独的点和二分图，我们把这两个放在一起统计。

首先有一个很显然的想法就是钦定一部分点在左侧，另一部分在右侧，然后连边。设 $g_i$ 表示 $i$ 个点的方案数，则有：

g _ i = \sum\limits _ {j = 0} ^ i \binom{i}{j} \cdot 2 ^ {j (i - j)}

但是这样显然不对，因为单独的点放在左侧和右侧的方案本质上是相同的。

于是我们考虑容斥，设 $h_i$ 为实际答案，则有：

h _ i = \sum\limits _ {j = 0} ^ i \binom{i}{j} \cdot g _ {i - j} \cdot (-1) ^ j

最后统计答案时，直接枚举二元环的点数即可。即， $n$ 的答案为：

\sum\limits _ {i = 0} ^ n \binom{n}{i} \cdot f _ i \cdot h _ {n - i}

总时间复杂度为 $O(n ^ 2 + Tn)$ 。

// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int T, mod, n, dp[1005], C[1005][1005], pw[1000005], sum[1005], res[1005];

int calc(int x) {return (pw[x] - 1 + mod) % mod;}

int main() {
	scanf("%d%d", &T, &mod);
	for (int i = 0; i <= 1000; i++)
		for (int j = 0; j <= 1000; j++)
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	pw[0] = 1;
	for (int i = 1; i <= 1000000; i++) pw[i] = pw[i - 1] * 2 % mod;
	dp[0] = 1;
	for (int i = 2; i <= 1000; i += 2)
		dp[i] = (long long)dp[i - 2] * (i - 1) % mod;
	for (int i = 0; i <= 1000; i++)
		for (int j = 0; j <= i; j++)
			sum[i] = (sum[i] + (long long)C[i][j] * pw[j * (i - j)] % mod) % mod;
	for (int i = 0; i <= 1000; i++)
		for (int j = 0; j <= i; j++)
			if (j % 2 == 0) res[i] = (res[i] + (long long)C[i][j] * sum[i - j] % mod) % mod;
			else res[i] = (res[i] - (long long)C[i][j] * sum[i - j] % mod + mod) % mod;
	while (T--) {
		scanf("%d", &n);
		int ans = 0;
		for (int i = 0; i <= n; i += 2)
			ans = (ans + (long long)C[n][i] * dp[i] % mod * res[n - i] % mod) % mod;
		printf("%d\n", ans);
	}
	return 0;
}

分类

文章目录

2023 年 5 月做题记录

联合省选 2023 Day1 T2 城市建造

[Ynoi2010] Fusion Tree

AGC033D Complexity

洛谷 P9374 「DROI」Round 2 单图