AtCoder Grand Contest 035 题解

AtCoder Grand Contest 035

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;
}