AtCoder Grand Contest 035 题解
Visits: 375
XOR Circle
随便判一下。
const int N = 1e5 + 7;
int n, a[N];
int main() {
rd(n), rda(a, n);
map<int, int> c;
for (int i = 1; i <= n; i++) ++c[a[i]];
if (c[0] == n) return prints("Yes"), 0;
if (n % 3) return prints("No"), 0;
for (pi o : c)
if (o.se % (n / 3)) return prints("No"), 0;
int k = 0;
for (pi o : c) {
int t = o.se / (n / 3);
while (t--) k ^= o.fi;
}
if (k) return prints("No"), 0;
prints("Yes");
return 0;
}
Even Degrees
随便定向之后，若有偶数个奇点，则每次找到两个奇点之间的一条路径，对路径上的边取反即可消掉这两个奇点。
奇点个数的奇偶性等于 $m$ 的奇偶性，直接判。
考虑如何构造方案，找出图的一棵生成树，在树上让所有奇点与根之间的路径上的边取反即可。
const int N = 1e5 + 7;
int n, m, x[N], y[N];
bool d[N], v[N];
vector<pi> e[N];
bool dfs(int x) {
v[x] = 1;
bool s = d[x];
for (pi o : e[x]) {
int y = o.fi, i = o.se;
if (v[y]) continue;
bool k = dfs(y);
if (k) swap(::x[i], ::y[i]);
s ^= k;
}
return s;
}
int main() {
rd(n, m);
if (m & 1) return print(-1), 0;
for (int i = 1; i <= m; i++)
rd(x[i], y[i]), d[x[i]] ^= 1,
e[x[i]].pb(mp(y[i], i)), e[y[i]].pb(mp(x[i], i));
dfs(1);
for (int i = 1; i <= m; i++) print(x[i], y[i]);
return 0;
}
Skolem XOR Tree
题意
- 构造一棵 $2n$ 个点的树，满足：
- 对于 $i \in [1,n]$，将 $i$ 和 $i+n$ 的点权设为 $i$。
- $i$ 与 $i+n$ 在树上的路径上经过的所有点的点权异或和为 $i$。
- $n \le 10^5$。
题解
若 $n$ 为 $2^i$ 则无解。
否则，若 $n$ 为奇数，则对于 $i$ 为偶数，连边 $(i,i+1),(i+1,n+1),(n+1,i+n),(i+n,i+1+n)$，最后连边 $(1,2)$。
若 $n$ 为偶数，在上面的图的基础上挂上 $n$ 和 $2n$ 即可，随便构造。
代码
int main() {
int n;
rd(n);
if (n - (n & -n) == 0) return prints("No"), 0;
prints("Yes");
print(1, 2);
for (int i = 2; i < n - !(n & 1); i += 2)
print(i, i + 1), print(i + 1, n + 1), print(n + 1, i + n), print(i + n, i + 1 + n);
if (!(n & 1)) {
int x = n & -n, y = n - x;
print(n, x + 1), print(n * 2, y + n);
}
return 0;
}
Add and Remove
题意
- 给定 $n$ 个数 $a_{1\dots n}$。
- 你需要进行若干次下列操作，直到只剩下两个数：
- 选择三个连续的数 $a_{i-1},a_i,a_{i+1}$。
- 将 $a_{i-1},a_{i+1}$ 都加上 $a_i$，然后删掉 $a_i$。
- 要求最小化最终剩下的两个数的和。
- $n \le 18$。
题解
显然答案是对于每个 $a_i$ 乘上一个系数 $x_i$。
倒序考虑整个过程，一开始只有两个元素 $a_1,a_n$，这两个元素的系数 $x_1 = x_n$ 都为 $1$。若在 $a_i$ 和 $a_j$ 中插入了一个元素，其中 $a_i$ 的系数为 $x_i$，$a_j$ 的系数为 $x_j$，则可以发现插入的元素系数为 $x_i + x_j$。
考虑 DP，我们设 $f(i,j,l,r)$ 表示对于区间 $[i,j]$，$x_i = l$，$x_j = r$ 时 $(i,j)$ 对答案的最小贡献，转移时枚举断点 $d \in (i,j)$ 即可。
状态数的上界为 $\mathcal O(n^22^n)$。
代码
const int N = 19;
int n, a[N];
ll f(int i, int j, int l, int r) {
ll ans = 1e18;
if (j - i <= 1) return 0;
for (int d = i + 1; d < j; d++)
ans = min(ans, f(i, d, l, l + r) + f(d, j, l + r, r) + 1ll * a[d] * (l + r));
return ans;
}
int main() {
rd(n), rda(a, n);
print(f(1, n, 1, 1) + a[1] + a[n]);
return 0;
}
Develop
题意
- 给定 $n,k$。
- 设 $S$ 为整数的全集，求通过若干次下列操作可以得到多少个不同的集合：
- 选择 $x \in S \cap [1,n]$，将 $x$ 从 $S$ 中去掉。
- 对于 $x-2$ 和 $x+k$，若不在 $S$ 中，则加进 $S$。
- $1 \le k \le n \le 150$，答案对 $P$ 取模。
题解
考虑一个编号为 $1 \sim n$ 的有向图，连边 $(x,x-2)$ 和 $(x,x+k)$（如果存在）。
则每次操作相当于将一个点染黑，将其后继染白，其中初始时所有点都是白的，问最终形成的图有多少种方案。
显然黑点不能构成环，所以黑点一定是个 DAG，那么按照拓扑序选择黑点即可，于是问题等价于求给定图不存在黑环的方案数。
对 $k$ 分奇偶考虑然后简单 DP 一下即可。
代码
const int N = 157;
int n, K;
modint f[N][N], g[N][N][N], ans, ans0, ans1;
int main() {
rd(n, K, P);
if (K & 1) {
g[0][0][0] = 1;
int m = (K >> 1) + ((n + 1) >> 1);
for (int i = 0; i < m; i++)
for (int j = 0; j <= n >> 1; j++)
for (int k = 0; k <= K + 1; k++) {
g[i+1][0][0] += g[i][j][k];
if (i < n >> 1) g[i+1][j+1][0] += g[i][j][k];
if (i >= K >> 1) g[i+1][0][k?k+1:0] += g[i][j][k];
if (i >= (K >> 1) && i < (n >> 1)) g[i+1][j+1][max(j+2,k+1)] += g[i][j][k];
}
for (int j = 0; j <= n >> 1; j++)
for (int k = 0; k <= K + 1; k++)
ans += g[m][j][k];
print(ans);
} else {
f[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j <= min(i, K >> 1); j++)
f[i+1][j+1] += f[i][j], f[i+1][0] += f[i][j];
for (int j = 0; j <= K >> 1; j++)
ans0 += f[n>>1][j], ans1 += f[(n+1)>>1][j];
print(ans0 * ans1);
}
return 0;
}
Two Histograms
题意
- 对于一个 $n \times m$ 的矩阵，一开始每个位置上都是 $0$。
- 对于每一行，选择最左边的 $0 \sim m$ 个位置 $+1$；对于每一列，选择最上边的 $0 \sim n$ 个位置 $+1$。
- 求最后能形成的矩阵方案数。
- $n,m \le 5 \times 10^5$，答案对 $998244353$ 取模。
题解
注意到只有 $k_x = y$，$l_y = x – 1$ 和 $k_x = y – 1$，$l_y = x$ 才会形成一样的矩阵，那么枚举满足条件的 $(x,y)$ 对数容斥：
$$
ans = \sum_{i=0}^{\min(n,m)} (-1)^i \binom ni \binom mi i!(m+1)^{n-i}(n+1)^{m-i}
$$
时间复杂度 $\mathcal O(n)$。
代码
int main() {
int n, m;
rd(n, m), init(max(n, m) + 1);
modint a = (modint)(m + 1) ^ n, b = (modint)(n + 1) ^ m, w = 1, ans;
for (int i = 0; i <= min(n, m); i++, a *= v[m+1], b *= v[n+1], w = -w)
ans += w * binom(n, i) * binom(m, i) * p[i] * a * b;
print(ans);
return 0;
}
