AtCoder Grand Contest 027 题解

AtCoder Grand Contest 027

Candy Distribution Again

排序后从小到大贪心的选。

const int N = 107;
int n, x, a[N], s;

int main() {
	rd(n, x), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; s += a[i++])
		if (s + a[i] > x) return print(i - 1), 0;
	print(n - (s != x));
	return 0;
}

Garbage Collector

枚举次数 $k$ ，注意到从后往前的贡献为 $5,5,7,9,\cdots$ ，因此贪心地将最后 $k$ 个作为第一个，次后 $k$ 个作为第二个，以此类推。

复杂度是调和级数 $\mathcal O(n \log n)$ ，另外计算中会爆 long long 但答案不会爆，用 __int128 或者剪枝都可以。

const int N = 2e5 + 7;
int n;
__int128 x, p[N], s[N], d[N], ans = 1e36;

int main() {
	rd(n), rd(x), rda(p, n);
	for (int i = 1; i <= n; i++) s[i] = s[i-1] + p[i];
	d[1] = d[2] = 5;
	for (int i = 3; i <= n; i++) d[i] = d[i-1] + 2;
	for (int k = 1; k <= n; k++) {
		__int128 now = (k + n) * x;
		for (int i = n, t = 1; i > 0; i -= k, t++)
			now += d[t] * (s[i] - (i - k > 0 ? s[i-k] : 0));
		ans = min(ans, now);
	}
	print(ans);
	return 0;
}

ABland Yard

若一条边连接的两个点字符相同，则标为 0，否则标为 1。

那么合法当且仅当存在一个 01 环。

类似拓扑排序，每次删掉一个连边都是同一个字符的点。

如果最后剩下点没被删掉说明存在，否则不存在。

const int N = 2e5 + 7;
int n, m, d[N][2];
char s[N];
vi e[N];
queue<int> q;
bool v[N];

int main() {
	rd(n, m), rds(s, n);
	for (int i = 1, x, y; i <= m; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x), ++d[x][s[y]&1], ++d[y][s[x]&1];
	for (int i = 1; i <= n; i++)
		if (!d[i][0] || !d[i][1]) q.push(i), v[i] = 1;
	while (q.size()) {
		int x = q.front();
		q.pop();
		for (int y : e[x])
			if (!v[y] && !--d[y][s[x]&1]) q.push(y), v[y] = 1;
	}
	for (int i = 1; i <= n; i++)
		if (!v[i]) return prints("Yes"), 0;
	prints("No");
	return 0;
}

Modulo Matrix

题意

你要构造一个 $n \times n$ 的矩阵 $a$ ，满足：
- $a_{i,j} \in [1,10^{15}]$ 。
- 所有 $a_{i,j}$ 互不相同。
- 对于任意两个相邻的数 $x,y$ ， $\max(x,y) \bmod \min(x,y)$ 为定值。
$n \le 500$ 。

题解

如下图构造：

AtCoder Grand Contest 027 题解：原文插图

其中黄格子是两个质数的乘积，白格子为周围黄格子的 $\text{lcm} + 1$ 。

代码

namespace shai {
	const int n = 1e6 + 7;
	int p[n], v[n], phi[n], miu[n];

	inline void init(int n) {
		v[1] = phi[1] = miu[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
			for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
				v[i*p[j]] = p[j],
				phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
				miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
		}
	}
}
using shai::p;

const int N = 507;
int n, a[N], b[N];

int main() {
	shai::init(1e4);
	rd(n);
	for (int i = 1; i <= n; i++) a[i] = p[i&1?i/2+1:n*2-i/2+1];
	for (int i = 1; i <= n; i++) b[i] = p[(i&1?n-i/2:n+i/2)+(n&1)];
	a[0] = a[n+1] = b[0] = b[n+1] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			print((i ^ j) & 1 ? 1ll * a[(i+j)/2] * a[(i+j)/2+1] * b[(n+i-j+(n&1))/2] * b[(n+i-j+(n&1))/2+1] + 1 : 1ll * a[(i+j)/2] * b[(n+i-j+(n&1))/2], " \n"[j==n]);
	return 0;
}

ABBreviate

题意

给定一个仅包含 ab 的字符串 $s$ 。
你会进行若干次操作，每次操作可以将 $s$ 中的一个 aa 替换成 b，或将一个 bb 替换成 a。
求能够生成的字符串数量。
$|s| \le 10^5$ ，答案对 $10^9+7$ 取模。

题解

首先如果没有 aa 或 bb，答案为 $1$ 。

否则，令 a 为 $2$ ，b 为 $1$ ，可以发现每次操作都不影响和 $\bmod 3$ 的值。

考虑到如果一个 $t$ 能被 $s$ 生成，那么必然是 $t$ 中的每个字符对应 $s$ 中的某一段，且这两段的和 $\bmod 3$ 的值相同。

可以证明从前往后贪心匹配 $t$ 中的每个字符，如果最后 $s$ 剩下的部分之和 $\bmod 3 = 0$ ，则 $t$ 合法。

于是可以简单的 $\mathcal O(n)$ DP 求出答案了。

代码

const int N = 1e5 + 7;
int n, a[N], p[N][3];
char s[N];
modint f[N], ans;

inline bool pd() {
	for (int i = 1; i < n; i++)
		if (s[i] == s[i+1]) return 0;
	return 1;
}

int main() {
	rds(s, n);
	if (pd()) return print(1), 0;
	for (int i = 1; i <= n; i++) a[i] = (a[i-1] + (s[i] & 1) + 1) % 3;
	for (int i = 0; i < 3; i++) p[n+1][i] = n + 1;
	for (int i = n; i; i--) {
		for (int j = 0; j < 3; j++) p[i][j] = p[i+1][j];
		p[i][a[i]] = i;
	}
	f[0] = 1;
	for (int i = 0; i <= n; i++) {
		if (i && a[i] == a[n]) ans += f[i];
		for (int j = 1; j < 3; j++)
			f[p[i+1][(a[i]+j)%3]] += f[i];
	}
	print(ans);
	return 0;
}

Grafting

题意

给定两棵 $n$ 个点的树 $A,B$ 。
一开始 $A$ 的所有点都是白色，你可以对 $A$ 进行若干次下列操作使得 $A$ 与 $B$ 相同：
- 选择一个白色的叶子节点 $x$ 。
- 删掉与 $x$ 相连的边。
- 加上一条连接 $x$ 与另一个节点 $y$ 的边。
- 将 $x$ 染成黑色。
判断是否可行，如果可行，请最小化操作步数。
$n \le 50$ ，多组数据组数 $T \le 20$ 。

题解

首先判一下 $A,B$ 是否本身就相同，如果是就直接输出 $0$ 。

否则枚举第一次操作的 $x,y$ ，然后以 $x$ 为根把两棵树拎起来（其中 $A$ 是操作后的树）。

那么某个节点会被修改当且仅当这个点在两棵树上的父亲不同。

另外可以得到一些约束条件：

若某个点不需要被修改，这意味着它在 $A$ 上的父亲不可能成为叶子，因此若它在 $A$ 上的父亲需要被修改，那么无解。
在 $A$ 中，一个点一定比它的父亲先被修改（如果都要被修改的话）。
在 $B$ 中，一个点一定比它的父亲后被修改（如果都要被修改的话）。

根据后两个条件我们可以得到一个有向图，如果这个有向图无环则说明有解，否则无解。

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

代码

const int N = 57, inf = 1e9;
int n, f[2][N], d[N];
vi e[2][N], g[N];
bool v[N];
queue<int> q;

inline bool pd0() {
	for (int i = 1; i <= n; i++)
		if (e[0][i] != e[1][i]) return 0;
	return 1;
}

inline void change(int x, int y, int z) {
	e[0][x][0] = z;
	for (int &o : e[0][y])
		if (o == x) {
			swap(o, e[0][y].back());
			break;
		}
	e[0][y].pop_back(), e[0][z].pb(x);
}

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

inline void add(int x, int y) {
	g[x].pb(y), ++d[y];
}

inline int calc(int x, int y) {
	int z = e[0][x][0], now = y != z;
	change(x, z, y);
	dfs(0, x, 0), dfs(1, x, 0);
	change(x, y, z);
	for (int i = 1; i <= n; i++)
		now += v[i] = f[0][i] != f[1][i], g[i].clear(), d[i] = 0;
	for (int i = 1; i <= n; i++)
		if (!v[i] && v[f[0][i]]) return inf;
	for (int o = 0; o < 2; o++)
		for (int i = 1; i <= n; i++)
			if (v[i] && v[f[o][i]])
				add(o ? f[o][i] : i, o ? i : f[o][i]);
	for (int i = 1; i <= n; i++)
		if (v[i] && !d[i]) q.push(i);
	while (q.size()) {
		int x = q.front();
		q.pop(), v[x] = 0;
		for (int y : g[x])
			if (!--d[y]) q.push(y);
	}
	for (int i = 1; i <= n; i++)
		if (v[i]) return inf;
	return now;
}

inline void solve() {
	rd(n);
	for (int o = 0; o < 2; o++) {
		for (int i = 1; i <= n; i++) e[o][i].clear();
		for (int i = 1, x, y; i < n; i++)
			rd(x, y), e[o][x].pb(y), e[o][y].pb(x);
		for (int i = 1; i <= n; i++)
			sort(e[o][i].begin(), e[o][i].end());
	}
	if (pd0()) return print(0);
	int ans = inf;
	for (int x = 1; x <= n; x++)
		if (e[0][x].size() == 1u)
			for (int y = 1; y <= n; y++)
				ans = min(ans, calc(x, y));
	print(ans == inf ? -1 : ans);
}

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