AtCoder Grand Contest 034 题解

AtCoder Grand Contest 034

Kenken Race

分 $c < d$ 和 $c>d$ 讨论一下，后者合法多一个限制：存在 $i \in [b,d]$ 满足 $i-1,i,i+1$ 都是空的。

const int N = 2e5 + 7;
int n, a, b, c, d;
char s[N];

inline bool pd(int i, int j) {
	while (i != j) {
		if (s[i+1] == '#' && s[i+2] == '#') return 0;
		if (s[i+1] == '.') i += 1;
		else i += 2;
	}
	return 1;
}

int main() {
	rd(n), rd(a, b), rd(c, d), rds(s, n);
	if (c < d) return prints(pd(a, c) && pd(b, d) ? "Yes" : "No"), 0;
	bool ok = 0;
	for (int i = b; i <= d; i++)
		if (s[i] == '.' && s[i-1] == '.' && s[i+1] == '.') ok = 1;
	prints(ok && pd(a, c) && pd(b, d) ? "Yes" : "No");
	return 0;
}

ABC

每次操作相当于将 BC 移到 A 后面，从前往后做就行了。

const int N = 2e5 + 7;
int n;
char s[N];
ll ans;

int main() {
	rds(s, n);
	for (int i = 1, t = 0; i < n; i++)
		if (s[i] == 'B' && s[i+1] == 'C') ans += t, ++i;
		else if (s[i] == 'A') ++t;
		else t = 0;
	print(ans);
	return 0;
}

Tests

显然答案是若干个 $x$ ，一个 $[0,x]$ ，若干个 $0$ 。

二分答案，枚举 $[0,x]$ 的那个找到最大值，时间复杂度 $\mathcal O(n \log (nx))$ 。

const int N = 1e5 + 7;
int n, x, p[N];
ll b[N], l[N], r[N], s[N], sum;

inline ll calc(int x, ll t) {
	return t <= b[x] ? t * l[x] : b[x] * l[x] + (t - b[x]) * r[x];
}

inline ll pd(ll t) {
	int w = t % x ? t % x : x, c = (t - w) / x;
	ll sum = 0, ret = 0;
	for (int i = 1; i <= c; i++) sum += s[p[i]];
	for (int i = c + 1; i <= n; i++)
		ret = max(ret, sum + calc(p[i], w));
	sum += s[p[c+1]];
	for (int i = 1; i <= c; i++)
		ret = max(ret, sum - s[p[i]] + calc(p[i], w));
	return ret;
}

int main() {
	rd(n, x);
	for (int i = 1; i <= n; i++)
		rd(b[i], l[i], r[i]), p[i] = i,
		s[i] = b[i] * l[i] + (x - b[i]) * r[i], sum += b[i] * l[i];
	sort(p + 1, p + n + 1, [&](int i, int j) { return s[i] > s[j]; });
	if (!sum) return print(0), 0;
	ll l = 1, r = 1ll * n * x;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (pd(mid) >= sum) r = mid;
		else l = mid + 1;
	}
	print(l);
	return 0;
}

Manhattan Max Matching

题意

在平面上有 $n$ 个位置有红点， $n$ 个位置上有蓝点，其中 $(rx_i,ry_i)$ 上有 $rc_i$ 个红点， $(bx_i,by_i)$ 上有 $bc_i$ 个蓝点，红蓝点总个数相同。
现在要将红蓝点一一匹配，两点匹配的价值为其曼哈顿距离，要求最大价值和。
$n \le 10^3$ ， $rc_i,bc_i \le 10$ 。

题解

首先显然可以直接建图跑费用流，但边数为 $\mathcal O(n^2)$ 无法接受。

考虑曼哈顿距离有性质：

$\begin{aligned} |x_1-x_2|+|y_1-y_2| &=\max( x_1-x_2+y_1-y_2, x_1-x_2-y_1+y_2, -x_1+x_2+y_1-y_2, -x_1+x_2-y_1+y_2 )\\\\ &=\max( (x_1+y_1)+(-x_2-y_2), (x_1-y_1)+(-x_2+y_2), (-x_1+y_1)+(x_2-y_2), (-x_1-y_1)+(x_2+y_2) )\\\\ \end{aligned}$

于是只需要建四个点对应每种情况，边数 $\mathcal O(n)$ ，可以直接跑费用流。

代码

namespace Dinic {
	const int N = 1e5 + 7, M = 2e6 + 7;
	const ll inf = 1e18;
	int n, S, T;
	int h[N], hi[N], e[M], t[M], tot;
	ll d[N], f[M], c[M], mxf, ans;
	bool v[N];

	inline void add(int x, int y, ll z, ll w, bool o = 1) {
		e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0, -w, 0);
	}

	inline bool bfs() {
		for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
		queue<int> q;
		q.push(S), d[S] = 0, v[S] = 1;
		while (q.size()) {
			int x = q.front();
			q.pop(), v[x] = 0;
			for (int i = h[x]; i; i = t[i]) {
				int y = e[i];
				ll z = f[i], w = c[i];
				if (d[y] <= d[x] + w || !z) continue;
				d[y] = d[x] + w;
				if (!v[y]) q.push(y), v[y] = 1;
			}
		}
		return d[T] != inf;
	}

	ll dfs(int x, ll now = inf) {
		if (x == T) return now;
		v[x] = 1;
		ll rst = now;
		for (int &i = hi[x]; i; i = t[i]) {
			int y = e[i];
			ll z = f[i], w = c[i];
			if (v[y] || d[y] != d[x] + w || !z) continue;
			ll k = dfs(y, min(z, rst));
			if (!k) d[y] = inf;
			else ans += k * w, f[i] -= k, f[i^1] += k, rst -= k;
			if (!rst) break;
		}
		v[x] = 0;
		return now - rst;
	}

	inline void main() {
		while (bfs()) {
			for (int i = 1; i <= n; i++) hi[i] = h[i];
			ll now;
			while ((now = dfs(S))) mxf += now;
		}
	}

	inline void init(int _n, int _S, int _T) {
		n = _n, S = _S, T = _T, tot = 1, mxf = 0, ans = 0;
		for (int i = 1; i <= n; i++) h[i] = 0; 
	}
}
using Dinic::add;
using Dinic::inf;

int main() {
	int n;
	rd(n);
	int p1 = n << 1 | 1, p2 = p1 + 1, p3 = p2 + 1, p4 = p3 + 1;
	int S = p4 + 1, T = S + 1;
	Dinic::init(T, S, T);
	for (int i = 1, x, y, c; i <= n; i++)
		rd(x, y, c),
		add(S, i, c, 0),
		add(i, p1, inf, x + y),
		add(i, p2, inf, x - y),
		add(i, p3, inf, -x + y),
		add(i, p4, inf, -x - y);
	for (int i = 1, x, y, c; i <= n; i++)
		rd(x, y, c),
		add(i + n, T, c, 0),
		add(p1, i + n, inf, -x - y),
		add(p2, i + n, inf, -x + y),
		add(p3, i + n, inf, x - y),
		add(p4, i + n, inf, x + y);
	Dinic::main();
	print(-Dinic::ans);
	return 0;
}

Complete Compress

题意

给定一棵 $n$ 个点的树，树上的某些节点上有一个人。
每次可以选择两个距离 $\ge 2$ 的人，它们将向对方移动一个点。
问能否使得所有人都在一个点上。
$n \le 2 \times 10^3$ 。

题解

枚举最终的点 $rt$ ，以 $rt$ 为根建树。

则每一步必然是找到两个非祖先关系的人，向着它们的 $\text{lca}$ 移动一格。

若将点 $x$ 上的人视为 $\text{dist}(rt,x)$ 个，则问题等价于每次消掉两个非祖先关系的人，问是否能消完。

考虑 DP，设 $f_u$ 表示 $u$ 子树的答案，设 $d_u$ 表示 $u$ 子树内的人数，则：

若 $u$ 存在某个儿子 $v$ ，满足 $d_u < 2d_v$ ，则有转移 $f_u = d_u - d_v + \min(f_v, \lfloor\frac{2d_v - d_u}{2} \rfloor)$ 。
否则， $f_u = \lfloor\frac{d_u}{2} \rfloor$ 。

最终要求 $d_{rt}$ 为偶数，且 $2f_{rt} \ge d_{rt}$ 才能更新答案。

代码

const int N = 2e3 + 7, inf = 1e9;
int n, m, d[N], s[N], f[N], ans = inf;
char a[N];
vi e[N];

void dfs(int x, int fa = 0) {
	s[x] = a[x] == '1', d[x] = 0;
	int o = 0;
	for (int y : e[x])
		if (y != fa) {
			dfs(y, x), s[x] += s[y], d[x] += d[y] += s[y];
			if (d[y] > d[o]) o = y;
		}
	if (d[x] >= 2 * d[o]) f[x] = d[x] >> 1;
	else f[x] = d[x] - d[o] + min(f[o], (d[o] * 2 - d[x]) >> 1);
}

int main() {
	rd(n), rds(a, n);
	for (int i = 1; i <= n; i++) m += a[i] == '1';
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	for (int x = 1; x <= n; x++) {
		dfs(x);
		if (d[x] & 1) continue;
		if (f[x] * 2 >= d[x]) ans = min(ans, d[x]);
	}
	print(ans == inf ? -1 : ans >> 1);
	return 0;
}

RNG and XOR

题意

给定 $n$ 和 $a_{0\dots 2^n-1}$ 。
有一个初始为 $0$ 的变量 $x$ 。
每次操作会将 $x$ 以 $\frac {a_i}{\sum_{j=0}^{2^n-1}a_j}$ 的概率异或上 $i$ 。
求对于 $i \in [0,2^n-1]$ ， $x$ 第一次变成 $i$ 的期望操作次数。
$n \le 18$ ， $a_i \le 10^3$ ，答案对 $998244353$ 取模。

题解

为了方便，将 $a_i$ 视为 $\frac {a_i}{\sum_{j=0}^{2^n-1}a_j}$ 。

设 $x_i$ 为 $i$ 第一次变成 $0$ 的期望操作次数，显然 $x_i$ 也是 $0$ 第一次变成 $i$ 的期望操作次数。

有转移： $x_i = \begin{cases} 0 & i = 0 \\\\ \sum_{j=0}^{2^n-1} a_jx_{i\operatorname{xor}j} + 1 & i \ne 0 \end{cases}$ 即异或卷积： $(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0,p_1,\cdots,p_{2^n-1}) = (c,x_1-1,x_2-1,\cdots,x_{2^n-1}-1)$ 其中 $c$ 为一个常数。

注意到显然异或卷积 $(p_0,p_1,\cdots,p_{2^n-1})$ 后总和不变，因此 $c = x_0+2^n-1$ ，即： $(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0,p_1,\cdots,p_{2^n-1}) = (x_0+2^n-1,x_1-1,x_2-1,\cdots,x_{2^n-1}-1)$ 注意到如果将 $p_0$ 减 $1$ ，那么右边第 $i$ 项会减去 $x_i$ ，正好把右边的未知项删掉了，即： $(x_0,x_1,\cdots,x_{2^n-1})\operatorname{xor}(p_0-1,p_1,\cdots,p_{2^n-1}) = (2^n-1,-1,-1,\cdots,-1)$ 这时异或卷积中的三项有两项都已知了，那么剩下的一项可以直接 FWT 求出。

然而会发现求出的答案不对，问题出在这样的异或卷积是有不只一组解的，对每个 $x_i$ 都加上 $k$ 之后式子依然成立。

又注意到 $x_0 = 0$ ，因此我们把求出来的每一项都减去 $x_0$ 就是我们要的答案。

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

代码

const int N = 1 << 18 | 1;
int n;
modint a[N], b[N], s;

inline void XOR(modint *f, modint x) {
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; j++) {
				modint p = f[i+j] * x, q = f[i+j+k] * x;
				f[i+j] = p + q, f[i+j+k] = p - q;
			}
}

int main() {
	rd(n), n = 1 << n;
	for (int i = 0; i < n; i++) rd(a[i]), b[i] = P - 1, s += a[i];
	modint vs = 1 / s;
	for (int i = 0; i < n; i++) a[i] *= vs;
	a[0] -= 1, b[0] = n - 1;
	XOR(a, 1), XOR(b, 1);
	for (int i = 0; i < n; i++) b[i] /= a[i];
	XOR(b, (modint)1 / 2);
	for (int i = 0; i < n; i++) print(b[i] - b[0]);
	return 0;
}

Kenken Race

ABC

Tests

Manhattan Max Matching

题意

题解

代码

Complete Compress

题意

题解

代码

RNG and XOR

题意

题解

代码

评论