AtCoder Grand Contest 032 题解

AtCoder Grand Contest 032

Limited Insertion

倒着考虑，每次找到最大的 $i$ 满足 $a_i = i$ 然后删掉，如果不存在则无解。

const int N = 107;
int n, a[N], ans[N];

int main() {
	rd(n), rda(a, n);
	for (int i = n; i; i--) {
		int p = 0;
		for (int j = i; j && !p; j--)
			if (a[j] == j) p = j;
		if (!p) return prints("-1"), 0;
		ans[i] = p;
		for (int j = p; j < i; j++) a[j] = a[j+1];
	}
	for (int i = 1; i <= n; i++) print(ans[i]);
	return 0;
}

Balanced Neighbors

构造方式见代码。

int main() {
	int n;
	rd(n);
	if (n == 3) {
		print(2);
		print(1, 3);
		print(2, 3);
		return 0;
	}
	if (n == 4) {
		print(4);
		print(1, 2);
		print(1, 3);
		print(4, 2);
		print(4, 3);
		return 0;
	}
	vector<pi> e;
	vi a, b;
	int m = n & 1;
	n -= m;
	for (int i = 1; i <= n >> 1; i++) a.pb(i);
	for (int i = n; i > n >> 1; i--) b.pb(i);
	for (int i = 1; i < n >> 1; i++)
		e.pb(mp(a[i-1], a[i])),
		e.pb(mp(b[i-1], b[i])),
		e.pb(mp(a[i-1], b[i])),
		e.pb(mp(b[i-1], a[i]));
	if (m) {
		e.pb(mp(n + 1, a[0])),
		e.pb(mp(n + 1, b[0])),
		e.pb(mp(n + 1, a.back())),
		e.pb(mp(n + 1, b.back()));
	} else {
		e.pb(mp(a.back(), a[0])),
		e.pb(mp(b.back(), b[0])),
		e.pb(mp(a.back(), b[0])),
		e.pb(mp(b.back(), a[0]));
	}
	print(e.size());
	for (pi o : e) print(o.fi, o.se);
	return 0;
}

Three Circuits

题意

给定一张 $n$ 个点 $m$ 条边的无向图，问能否将无向图拆成三个环，使得每条边恰好在一个环中。
$n,m \le 10^5$ 。

题解

首先要是欧拉回路。

若度数最大值 $\ge 6$ 则有解， $= 2$ 则无解，接下来考虑 $=4$ 的情况。

若度数为 $4$ 的点超过 $3$ 个则有解， $1$ 个则无解，接下来考虑 $2$ 个的情况。

只有两种形态，一种有解一种无解，讨论一下即可。

代码

const int N = 1e5 + 7;
int n, m, d[N], X, Y;
vi e[N];

void dfs(int x, int f) {
	if (x == Y) return;
	if (x == X) prints("Yes"), exit(0);
	for (int y : e[x])
		if (y != f) dfs(y, x);
}

int main() {
	rd(n, m);
	for (int i = 1, x, y; i <= m; i++)
		rd(x, y), ++d[x], ++d[y], e[x].pb(y), e[y].pb(x);
	for (int i = 1; i <= n; i++) if (d[i] & 1) return prints("No"), 0;
	int mx = *max_element(d + 1, d + n + 1);
	if (mx == 2) return prints("No"), 0;
	if (mx >= 6) return prints("Yes"), 0;
	int cnt = 0;
	for (int i = 1; i <= n; i++) cnt += d[i] == 4;
	if (cnt == 1) return prints("No"), 0;
	if (cnt >= 3) return prints("Yes"), 0;
	for (int i = 1; i <= n; i++)
		if (d[i] == 4) {
			if (X) Y = i;
			else X = i;
		}
	for (int z : e[X]) dfs(z, X);
	prints("No");
	return 0;
}

Rotation Sort

题意

给定一个 $1 \sim n$ 的排列 $p$ ，你要将其变成升序。
有两种操作：
- 选择一个 $l,r$ 满足 $1 \le l < r \le n$ ，将 $p_{l\dots r}$ 替换为 $p_{l+1\dots r},p_l$ ，代价为 $a$ 。
- 选择一个 $l,r$ 满足 $1 \le l < r \le n$ ，将 $p_{l\dots r}$ 替换为 $p_{r},p_{l\dots r-1}$ ，代价为 $b$ 。
求最小代价。
$n \le 5\times 10^3$ 。

题解

显然操作等价于将某个数左移或者右移。

考虑 DP，设 $f_{i,j}$ 表示考虑前 $i$ 个数，其中最后一个没有被移动的数为 $j$ 的最小代价，分 $a_i > j$ 和 $a_i < j$ 转移即可，时间复杂度 $\mathcal O(n^2)$ 。

代码

const int N = 5e3 + 7;
const ll inf = 1e18;
int n, a, b, p[N];
ll f[N][N], ans = inf;

int main() {
	rd(n, a, b), rda(p, n);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			f[i][j] = inf;
	f[0][0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= n; j++)
			if (p[i] > j)
				f[i][j] = min(f[i][j], f[i-1][j] + a),
				f[i][p[i]] = min(f[i][p[i]], f[i-1][j]);
			else f[i][j] = min(f[i][j], f[i-1][j] + b);
	for (int i = 0; i <= n; i++) ans = min(ans, f[n][i]);
	print(ans);
	return 0;
}

Modulo Pairing

题意

给定模数 $m$ 和 $2n$ 个整数，你要将这些整数分成 $n$ 对。
对于每一对 $(x,y)$ ，其权值为 $(x+y) \bmod m$ 。
你要最小化这 $n$ 对权值的最大值。
$n \le 10^5$ ， $m \le 10^9$ 。

题解

有结论：按从小到大排序后，一定存在一个最优解，是以某个位置为界，两边分别首位匹配，满足左边每一对的和都 $< m$ ，右边每一对的和都 $\ge m$ 。

二分这个位置，时间复杂度 $\mathcal O(n \log n)$ 。

代码

const int N = 2e5 + 7;
int n, m, a[N], ans;

inline bool pd(int o) {
	for (int i = o << 1 | 1; i <= n << 1; i++)
		if (a[i] + a[((n+o)<<1|1)-i] < m) return 0;
	return 1;
}

int main() {
	rd(n, m), rda(a, n << 1);
	sort(a + 1, a + (n << 1 | 1));
	int l = 0, r = n;
	while (l < r) {
		int d = (l + r) >> 1;
		if (pd(d)) r = d;
		else l = d + 1;
	}
	int p = l << 1;
	for (int i = 1; i <= p; i++)
		ans = max(ans, a[i] + a[p+1-i]);
	for (int i = p + 1; i <= n << 1; i++)
		ans = max(ans, a[i] + a[(n<<1|1)+p-i] - m);
	print(ans);
	return 0;
}

One Third

题意

有一个披萨，将它在 $n$ 条随机的半径切一刀。
你会选择若干块相邻的披萨饼，使其总和最接近 $\frac 13$ 。
求选择的披萨饼大小与 $\frac 13$ 之差的绝对值的期望值。
$n \le 10^6$ ，答案对 $10^9+7$ 取模。

题解

先转化，对于每一刀，先将其染成红色，再在 $+ \frac 13$ 和 $-\frac 13$ 各切一刀，分别染蓝色和绿色。

将每一刀 $\bmod \frac 13$ ，于是问题等价于有一条长 $\frac 13$ 的线段， $0$ 处为红， $\frac 13$ 处为蓝，中间还有 $n-1$ 个位置和颜色随机的点，将整个线段分成了 $n$ 段，求最短的两端颜色不同的线段长度的期望。

把所有线段拿出来排序，考虑答案为第 $k$ 短的线段，经过积分可以得到为 $\sum_{i=1}^{k} \frac{1}{3n(n+1-i)}$ 。

考虑最短的，答案为 $\frac{1}{3n^2}$ ，如果同色考虑次短的，要加上 $\frac{1}{3n(n-1)}$ 乘上同色的概率 $\frac 13$ ，以此类推，答案为 $\sum_{k=1}^{n} \frac{1}{3^kn(n+1-k)}$ 。

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

代码

int n;
modint ans, a = 1;

int main() {
	rd(n), init(max(n, 3));
	for (int k = 1; k <= n; k++) ans += (a *= v[3]) * v[n+1-k];
	print(ans * v[n]);
	return 0;
}