AtCoder Grand Contest 025 题解

AtCoder Grand Contest 025

Digits Sum

枚举。

inline int calc(int x) {
	int s = 0;
	while (x) s += x % 10, x /= 10;
	return s;
}

int main() {
	int n, ans = 1e9;
	rd(n);
	for (int i = 1; i < n; i++)
		ans = min(ans, calc(i) + calc(n - i));
	print(ans);
	return 0;
}

RGB Coloring

有 $f_aa + f_bb = k$ ，枚举 $f_a$ ，如果存在 $f_b$ ，有贡献 $\binom n{f_a}\binom b{f_b}$ 。

int main() {
	int n;
	ll a, b, k;
	rd(n), rd(a, b, k), init(n);
	modint ans;
	for (int i = 0; i <= n && i * a <= k; i++)
		if (!((k - i * a) % b) && (k - i * a) / b <= n) {
			int j = (k - i * a) / b;
			ans += binom(n, i) * binom(n, j);
		}
	print(ans);
	return 0;
}

Interval Game

每次贪心地走，那么一定是左右左右地走，枚举第一步向左还是向右取 $\max$ 即可。

const int N = 1e5 + 7;
int n, l[N], r[N];
bool v[N];

inline void work(int l, int r, int &t, ll &now) {
	if (l <= t && r >= t) return;
	if (t < l) now += l - t, t = l;
	else now += t - r, t = r;
}

inline ll solve(int o) {
	pq<pi> p, q;
	for (int i = 1; i <= n; i++)
		v[i] = 0, p.push(mp(l[i], i)), q.push(mp(-r[i], i));
	ll now = 0;
	int t = 0;
	for (int i = 1; i <= n; i++)
		if ((i & 1) == o) {
			while (v[p.top().se]) p.pop();
			int x = p.top().se;
			p.pop(), v[x] = 1;
			work(l[x], r[x], t, now);
		} else {
			while (v[q.top().se]) q.pop();
			int x = q.top().se;
			q.pop(), v[x] = 1;
			work(l[x], r[x], t, now);
		}
	work(0, 0, t, now);
	return now;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(l[i], r[i]);
	print(max(solve(0), solve(1)));
	return 0;
}

Choosing Points

题意

构造 $n^2$ 个点，满足每个点的坐标都是 $[0,2n)$ 中的整数，且任一对点的距离都既不是 $\sqrt {d_1}$ 也不是 $\sqrt {d_2}$ 。
$n \le 300$ ， $d_1,d_2 \le 2 \times 10^5$ 。

题解

考虑将距离为 $\sqrt d$ 的点连边，可以证明得到的是一个二分图。

设 $d = 4^kp$ ，其中 $p \bmod 4 \ne 0$ 。

若存在 $x^2+y^2 = d$ ，则 $(x,y)$ 一定可以写成 $(2^ku, 2^kv)$ 的形式，其中 $u^2+v^2=p$ ，反证很容易证明。

只考虑 $\bmod 2^k$ 的等价类。若 $p \bmod 4 = 1$ ，则 $u,v$ 奇偶性不同，按 $u+v$ 的奇偶性染色即可；若 $p \bmod 4 = 2$ ，则 $u,v$ 均为奇数，按 $u$ 的奇偶性染色即可；若 $p \bmod 4 = 3$ ，则不存在合法点。

于是问题变成我们得到了两张二分图，要求取出一个包含 $\frac 14$ 的点集，考虑被两张二分图分成的四类中包含点数最多的一类即可。

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

代码

const int N = 607;
int n;
struct G {
	int d, c[N][N];
	vector<pi> p;
	inline bool pd(int x, int y) {
		return x >= 0 && x < n * 2 && y >= 0 && y < n * 2 && !~c[x][y];
	}
	void dfs(int x, int y, int z) {
		c[x][y] = z;
		for (pi o : p) {
			int X = x + o.fi, Y = y + o.se;
			if (pd(X, Y)) dfs(X, Y, z ^ 1);
		}
	}
	inline void main() {
		rd(d);
		for (int i = 0; i < n * 2; i++)
			for (int j = 0; j < n * 2; j++)
				c[i][j] = -1;
		for (int i = 1 - n * 2; i < n * 2; i++)
			for (int j = 1 - n * 2; j < n * 2; j++)
				if (i * i + j * j == d) p.pb(mp(i, j));
		for (int i = 0; i < n * 2; i++)
			for (int j = 0; j < n * 2; j++)
				if (pd(i, j)) dfs(i, j, 0);
	}
} g[2];
vector<pi> p[4];

int main() {
	rd(n), g[0].main(), g[1].main();
	for (int i = 0; i < n * 2; i++)
		for (int j = 0; j < n * 2; j++)
			p[g[1].c[i][j]*2+g[0].c[i][j]].pb(mp(i, j));
	int o = 0;
	for (int i = 1; i < 4; i++)
		if (p[i].size() > p[o].size()) o = i;
	while ((int)p[o].size() > n * n) p[o].pop_back();
	for (pi x : p[o]) print(x.fi, x.se);
	return 0;
}

Walking on a Tree

题意

给定一棵 $n$ 个点的树和 $m$ 条未定向的路径。
请你给这 $m$ 条路径定向，使得最大化有向覆盖的边数。
- 有向覆盖，即一条边从不同方向走算作两条有向边被覆盖。
$n,m \le 2 \times 10^3$ 。

题解

猜测答案是上界 $\sum_{i=1}^{n-1} \min(2, c_i)$ ，考虑如何构造。

考虑每次缩掉一个叶子 $u$ ，设其父亲为 $f_u$ ，与其相连的边为 $i$ 。

若 $c_i = 0$ 则可以直接缩。

若 $c_i = 1$ 则怎么定向没有区别，把所有端点为 $u$ 的路径改成端点为 $f_u$ ，然后也可以直接缩。

若 $c_i \ge 2$ ，则取出两条端点为 $u$ 的路径，剩下的路径按 $c_i = 1$ 来。对于取出的两条路径，设为 $(u,x),(u,y)$ ，则我们可以将它替换为 $(x,y)$ 。若 $(x,y)$ 为 $x \to y$ ，则还原为 $x \to u$ 和 $u \to y$ ，反之亦然。

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

代码

const int N = 4e3 + 5;
int n, m, de[N], fa[N], ans;
vi e[N];
int u[N], v[N], fu[N], fv[N], f[N], g[N], tot;
bool w[N], o[N], r[N];

void dfs(int x) {
	for (int y : e[x])
		if (y != fa[x]) fa[y] = x, de[y] = de[x] + 1, dfs(y);
}

void mark(int a, int b, int c, int d) {
	static int t[N];
	memset(t, 0, sizeof(t));
	while (a != b) {
		if (de[a] < de[b]) swap(a, b);
		++t[a], a = fa[a];
	}
	while (c != d) {
		if (de[c] < de[d]) swap(c, d);
		++t[c], c = fa[c];
	}
	for (int i = 1; i <= n; i++) o[i] |= t[i] >= 2;
}

void work(int x) {
	for (int y : e[x])
		if (y != fa[x]) work(y);
	if (x == 1) return;
	int t = 0;
	for (int i = 1; i <= tot; i++)
		if (!w[i]) t += (fu[i] == x) ^ (fv[i] == x);
	ans += min(max(t, o[x] * 2), 2);
	if (t <= 1 || o[x]) {
		for (int i = 1; i <= tot; i++)
			if (!w[i]) {
				if (fu[i] == x) fu[i] = fa[x];
				if (fv[i] == x) fv[i] = fa[x];
			}
		return;
	}
	vi p;
	for (int i = 1; i <= tot; i++)
		if (!w[i] && ((fu[i] == x) ^ (fv[i] == x))) p.pb(i);
	int a = p[0], b = p[1];
	mark(fu[a], fv[a], fu[b], fv[b]);
	w[a] = w[b] = 1, f[++tot] = a, g[tot] = b;
	if (fu[a] == x) u[tot] = v[a], fu[tot] = fv[a];
	else u[tot] = u[a], fu[tot] = fu[a];
	if (fu[b] == x) v[tot] = v[b], fv[tot] = fv[b];
	else v[tot] = u[b], fv[tot] = fu[b];
	for (int i = 1; i <= tot; i++)
		if (!w[i]) {
			if (fu[i] == x) fu[i] = fa[x];
			if (fv[i] == x) fv[i] = fa[x];
		}
}

int main() {
	rd(n, m), tot = m;
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	de[1] = 1, dfs(1);
	for (int i = 1; i <= m; i++)
		rd(u[i], v[i]), fu[i] = u[i], fv[i] = v[i];
	work(1), print(ans);
	for (int i = tot; i; i--) {
		if (!w[i]) r[i] = 1;
		if (i > m) {
			int a = f[i], b = g[i];
			r[a] = r[i] ^ (u[i] != u[a]);
			r[b] = r[i] ^ (v[i] != v[b]);
		}
	}
	for (int i = 1; i <= m; i++)
		if (r[i]) print(u[i], v[i]);
		else print(v[i], u[i]);
	return 0;
}

Addition and Andition

题意

给定两个二进制数，分别为长度为 $n$ 的 $x$ 和长度为 $m$ 的 $y$ 。
你要进行下列操作 $k$ 次：
- 设 $z = x \operatorname{and} y$ ，将 $x,y$ 都加上 $z$ 。
求最终 $x,y$ 的值。
$n,m,k \le 10^6$ 。

题解

令 $s_i,t_i$ 表示两个数的第 $i$ 位。

定义对 $i$ 的进位操作为：

条件为 $s_i = t_i = 1$ 。
将 $s_i,t_i$ 设为 $2$ 。
重复下列操作：
- 若 $s_i = 2$ 或 $t_i = 2$ ，将其设为 $0$ 并对下一位 $+1$ ，将 $i$ 也 $+1$ 。
- 否则结束进位操作。

定义一次加法操作为：

从大到小对于每个 $s_i = t_i = 1$ 的 $i$ 进行进位操作。

题目要求我们进行 $k$ 次加法操作，我们可以将其等价的转化为：

从大到小对于每个 $s_i = t_i = 1$ 的 $i$ 进行 $k$ 次下列操作：
- 找到最小的满足 $s_j = t_j = 1$ 的 $j$ ，对 $j$ 进行进位操作。
- 若不存在这样的 $j$ ，则结束操作。

可以这样转化是因为，在一次加法操作中，先进行的进位操作造成的增量将会大于之后进行的所有进位操作造成的增量之和，并且对 $i$ 进行进位操作后有 $s_i = t_i = 0$ 。

考虑转化后对于每个 $s_i = t_i = 1$ 的 $i$ 我们具体要做什么。

设 $x = 00,01,10,11$ 为当前的进位情况， $c$ 表示剩余操作次数。

初始时让 $s_i = t_i = 0$ ， $x = 11$ ， $c = k$ ，然后对于 $j = i,i+1,\cdots$ 进行如下操作：

若 $(s_j,t_j) = (0,0)$ ：
- 若 $x = 10$ ，让 $(s_j,t_j) = (1,0)$ ，结束操作。
- 若 $x = 01$ ，让 $(s_j,t_j) = (0,1)$ ，结束操作。
- 若 $x = 11$ ，让 $(s_j,t_j) = (1,1)$ ， $x$ 不变， $c$ 减去 $1$ ，若 $c < 0$ 结束操作。
若 $(s_j,t_j) = (1,0)$ ：
- 若 $x = 10$ ，让 $(s_j,t_j) = (0,0)$ ， $x$ 不变。
- 若 $x = 01$ ，让 $(s_j,t_j) = (1,1)$ ， $x = 11$ ， $c$ 减去 $1$ ，若 $c < 0$ 结束操作。
- 若 $x = 11$ ，让 $(s_j,t_j) = (0,1)$ ， $x = 10$ 。
若 $(s_j,t_j) = (0,1)$ ，同理 $(1,0)$ 的情况。
不可能出现 $(s_j,t_j) = (1,1)$ 的情况。

注意到 $(s_j,t_j) = (0,0)$ 的情况可以快速处理，因此把 $(0,0)$ 段全部缩起来，用一个栈维护 $(s_j,t_j) \ne (0,0)$ 的位置，由于其它操作都将减少 $1$ 的个数，所以总时间复杂度是 $\mathcal O(n)$ 的。

代码

const int N = 2e6 + 7;
int n, m, k, a[N], b[N], s[N], t[N];
stack<pi> st;

inline void in(int *a, int n) {
	static char s[N];
	rds(s, n);
	for (int i = 1; i <= n; i++) a[n+1-i] = s[i] - '0';
}

inline void out(int *a) {
	int l = max(n, m) + k;
	while (!a[l]) --l;
	for (int i = l; i; i--) printc(a[i] + '0');
	printc('\n');
}

int main() {
	rd(n, m, k), in(a, n), in(b, m);
	for (int i = max(n, m); i; i--) {
		if (a[i] + b[i] == 1) st.push(mp(i, a[i] * 2 + b[i]));
		if (a[i] + b[i] <= 1) continue;
		int c = k, p = i, x = 3;
		stack<pi> sa;
		while (st.size()) {
			pi o = st.top();
			if (p == o.fi) {
				st.pop();
				if ((x ^ o.se) == 3) {
					x = 3;
					if (c) c--;
					else break;
				} else if (x == 3) x &= o.se, sa.push(mp(o.fi, o.se ^ 3));
				p++;
			} else if (x == 3 && o.fi - p <= c) c -= o.fi - p, p = o.fi;
			else break;
		}
		if (x == 3) s[p+c] = t[p+c] = 1;
		else sa.push(mp(p, x));
		while (sa.size()) st.push(sa.top()), sa.pop();
	}
	while (st.size()) {
		pi o = st.top();
		s[o.fi] += o.se >> 1 & 1, t[o.fi] += o.se & 1, st.pop();
	}
	out(s), out(t);
	return 0;
}