CSP2019 题解 · 徐皓天

CSP2019-S2 自测

格雷码

依照题意模拟即可，注意开 unsigned long long。

inline void dfs(int n, ul k) {
	if (!n--) return;
	putchar('0' + ((k >> n) & 1));
	if ((k >> n) & 1) k ^= (1llu << n) - 1;
	dfs(n, k);
}

int main() {
	int n;
	ul k;
	rd(n), rd(k);
	dfs(n, k);
	return 0;
}

括号树

考虑以每个节点为结尾的合法括号子串有多少个。

以 ( 为 $1$ ) 为 $-1$ 做一个树上前缀和，设点 $x$ 的前缀和为 $s_x$ 。

则以 $x$ 结尾的合法括号子串的开头 $v$ 需要满足：

$s_u = s_v$ 。
$v \to u$ 的路径上所有点的 $s \ge s_u$ 。

遍历一遍树，用一个 $c$ 数组记录从根节点到当前节点的所有 $s$ 出现的个数，同时用一个 $p$ 数组记录每一个 $s$ 上一次出现的位置。

那么对于一个点 $u$ ，以 $u$ 结尾的合法括号子串的个数应该为，在点 $u$ 的时候 $c[s_u]$ 的值（去掉 $s_u$ 本身）减去在点 $p[s_u-1]$ 的时候 $c[s_u]$ 的值。

前者可以直接加到 $ans_u$ 中，后者则需要等到回溯到 $p[s_u-1]$ 再从 $ans_u$ 减掉，用一个 vector 记录即可。

其中，更新 $p$ 数组时，需要用一个额外的变量记录更新前的值。

总时间复杂度 $\mathcal O(n)$ 。

const int N = 5e5 + 7;
int n, c[N<<1], p[N<<1];
char s[N];
vi e[N], g[N];
ll ans[N], Ans;

void dfs(int x, int o) {
	o += s[x] == '(' ? 1 : -1;
	ans[x] = c[o];
	++c[o];
	int w = p[o];
	p[o] = x;
	g[p[o-1]].pb(x);
	for (ui i = 0; i < e[x].size(); i++) dfs(e[x][i], o);
	for (ui i = 0; i < g[x].size(); i++) ans[g[x][i]] -= c[o+1];
	--c[o];
	p[o] = w;
}

void dfs(int x) {
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		ans[y] += ans[x];
		dfs(y);
	}
}

int main() {
	rd(n), rds(s, n);
	for (int i = 2, x; i <= n; i++) rd(x), e[x].pb(i);
	c[n+1] = 1;
	dfs(1, n + 1);
	dfs(1);
	for (int i = 1; i <= n; i++) Ans ^= i * ans[i];
	print(Ans);
	return 0;
}

树上的数

题目太神仙了，先咕咕咕着。

Emiya 家今天的饭

首先容斥，显然答案为总方案数，减掉有一个 $\ge \lfloor \frac n2 \rfloor$ 的方案数，减掉有两个 $\ge \lfloor \frac n2 \rfloor$ 的方案数。

然后就发现不可能出现多于一个 $\ge \lfloor \frac n2 \rfloor$ 。

那么可以枚举多于 $\ge \lfloor \frac n2 \rfloor$ 的那个，然后 dp。

设 $f[i][j][k]$ 为考虑到第 $i$ 种，要求多于的那个选了 $j$ 个，其他的选了 $k$ 个的方案数。

时间复杂度 $\mathcal O(n^3m)$ 。

考虑优化，我们并不关心 $j$ 和 $k$ 的具体值，而是只需要知道它们的差即可。

那么设 $f[i][j]$ 为考虑到第 $i$ 种，要求多于的那个比其他的多选了 $j$ 个的方案数。

时间复杂度 $\mathcal O(n^2m)$ 。

const int N = 107, M = 2e3 + 7;
int n, m;
modint a[N][M], s[N], f[N][N<<1], ans = 1;

inline modint calc(int x) {
	f[0][n+3] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = -i; j <= i; j++) {
			int k = j + n + 3;
			f[i][k] = 0;
			f[i][k] += f[i-1][k-1] * a[i][x];
			f[i][k] += f[i-1][k];
			f[i][k] += f[i-1][k+1] * (s[i] - a[i][x]);
		}
	modint ret = 0;
	for (int i = 1; i <= n; i++) ret += f[n][i+n+3];
	return ret;
}

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			rd(a[i][j]), s[i] += a[i][j];
		ans *= s[i] + 1;
	}
	ans -= 1;
	for (int i = 1; i <= m; i++) ans -= calc(i);
	print(ans);
	return 0;
}

划分

首先可以发现，某个点的最优决策一定是从上一个合法的最优决策转移过来的。

然后这个过程显然可以单调队列优化，时间复杂度 $\mathcal O(n)$ 。

const int N = 4e7 + 7;
int n, o, a[N], p[N], q[N], l, r;
ll s[N];
__int128 ans;

namespace GET {
	const int M = 1e5 + 7, P = (1 << 30) - 1;
	int x, y, z, b[N], m, p[M], l[M], r[M];
	inline void get() {
		rd(x), rd(y), rd(z), rd(b[1]), rd(b[2]), rd(m);
		for (int i = 3; i <= n; i++) b[i] = (1ll * x * b[i-1] + 1ll * y * b[i-2] + z) & P;
		for (int j = 1; j <= m; j++) {
			rd(p[j]), rd(l[j]), rd(r[j]);
			for (int i = p[j-1] + 1; i <= p[j]; i++)
				a[i] = b[i] % (r[j] - l[j] + 1) + l[j];
		}
	}
}

inline ll calc(int x) {
	return s[x] * 2 - s[p[x]];
}

int main() {
	rd(n), rd(o);
	if (o) GET::get();
	else for (int i = 1; i <= n; i++) rd(a[i]);
	for (int i = 1; i <= n; i++) {
		s[i] = s[i-1] + a[i];
		while (l < r && calc(q[l+1]) <= s[i]) ++l;
		p[i] = q[l];
		while (l <= r && calc(q[r]) >= calc(i)) --r;
		q[++r] = i;
	}
	while (n) ans += (__int128)(s[n] - s[p[n]]) * (s[n] - s[p[n]]), n = p[n];
	print(ans);
	return 0;
}

树的重心

考虑每个点作为重心的次数。

首先拿出一个重心来当作根 $rt$ 。

对于点 $x \ne rt$ ，如果 $x$ 为割掉某条边后的重心，那么这条边一定不在 $x$ 的子树内。

设割掉一条边后，另外一棵树的大小为 $S$ 。

设 $g_x = \max_{y \in \text{son}(x)} \\{s_y\\}$ 。

由于 $x$ 为重心，所以要满足： $2 \times (n - S - s_x) \le n - S$

$2 \times g_x \le n - S$

即： $n - 2s_x \le S \le n - 2g_x$ 即我们要找到对于一个 $x$ ，有多少条可以割掉的边满足：

$n - 2s_x \le S \le n - 2g_x$ 。
边不在 $x$ 的子树内。

如果只有第一个条件，那么我们可以进行一次 dfs，同时拿一个树状数组动态维护割掉当前点和其父亲之间的边后每一个 $S$ 的值有多少个，那么对于每一个点的询问实质上就是一个区间求和。

然后我们要去掉不满足第二个条件，即在 $x$ 的子树内的边，可以再拿一个树状数组按照 dfs 序动态维护经过的所有点的每一个 $s$ 的值有多少个，那么对于一个点，在其子树内可以割掉的边就是回溯与进入时区间求和后的差。

最后还有一个问题是，当 $x = rt$ ，我们如何统计 $x$ 为重心的次数？

设 $x$ 的儿子中子树最大的节点为 $u$ ，次大的节点为 $v$ 。

若割掉的边在 $u$ 的子树中，则需要满足： $2 \times s_v \le n - S$ 即： $S \le n - 2s_v$ 否则，需要满足： $2 \times s_u \le n - S$ 即： $S \le n - 2s_u$

可以在 dfs 的时候直接维护。

那么总时间复杂度为 $\mathcal O(n \log n)$ 。

const int N = 3e5 + 7;
int n, rt, s[N], g[N], u, v, z[N];
vi e[N];
ll ans, c1[N], c2[N];

inline void add(ll *c, int x, int k) {
	++x;
	while (x <= n + 1) c[x] += k, x += x & -x;
}

inline ll ask(ll *c, int x) {
	++x;
	ll k = 0;
	while (x) k += c[x], x -= x & -x;
	return k;
}

void dfs1(int x, int f) {
	s[x] = 1, g[x] = 0;
	bool fg = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == f) continue;
		dfs1(y, x);
		s[x] += s[y];
		g[x] = max(g[x], s[y]);
		if (s[y] > (n >> 1)) fg = 0;
	}
	if (n - s[x] > (n >> 1)) fg = 0;
	if (fg) rt = x;
}

void dfs2(int x, int f) {
	add(c1, s[f], -1);
	add(c1, n - s[x], 1);
	if (x ^ rt) {
		ans += x * ask(c1, n - 2 * g[x]);
		ans -= x * ask(c1, n - 2 * s[x] - 1);
		ans += x * ask(c2, n - 2 * g[x]);
		ans -= x * ask(c2, n - 2 * s[x] - 1);
		if (!z[x] && z[f]) z[x] = 1;
		ans += rt * (s[x] <= n - 2 * s[z[x]?v:u]);
	}
	add(c2, s[x], 1);
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == f) continue;
		dfs2(y, x);
	}
	add(c1, s[f], 1);
	add(c1, n - s[x], -1);
	if (x ^ rt) {
		ans -= x * ask(c2, n - 2 * g[x]);
		ans += x * ask(c2, n - 2 * s[x] - 1);
	}
}

inline void solve() {
	rd(n);
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	ans = 0;
	dfs1(1, 0);
	dfs1(rt, 0);
	u = v = 0;
	for (ui i = 0; i < e[rt].size(); i++) {
		int x = e[rt][i];
		if (s[x] > s[v]) v = x;
		if (s[v] > s[u]) swap(u, v);
	}
	for (int i = 1; i <= n + 1; i++) c1[i] = c2[i] = 0;
	for (int i = 0; i <= n; i++) add(c1, s[i], 1), z[i] = 0;
	z[u] = 1;
	dfs2(rt, 0);
	print(ans);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

格雷码

括号树

树上的数

Emiya 家今天的饭

划分

树的重心

评论