AtCoder Grand Contest 032 题解
Visits: 422
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;
}
