AtCoder Grand Contest 043 题解

AtCoder Grand Contest 043

Range Flip Find Route

注意到，最后走的路线一定是黑白交替的。

每一次翻转颜色都一定是在进入黑色的时候，将后面一段黑色的路变成白色。

这与最短路很类似，由于边权只有 $0/1$ ，因此本题用 deque bfs 即可，时间复杂度 $\mathcal O(nm)$ 。

const int N = 107, inf = 1e9;
int n, m, d[N][N], v[N][N];
char s[N][N];
deque<pi> q;

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rds(s[i], m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			d[i][j] = inf;
	q.pb(mp(1, 1)), d[1][1] = s[1][1] == '#';
	while (q.size()) {
		pi x = q.front();
		q.pop_front();
		if (v[x.fi][x.se]) continue;
		v[x.fi][x.se] = 1;
		if (x.fi < n) {
			if (s[x.fi][x.se] == '.' && s[x.fi+1][x.se] == '#') {
				if (d[x.fi+1][x.se] > d[x.fi][x.se] + 1)
					q.pb(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se] + 1;
			} else {
				if (d[x.fi+1][x.se] > d[x.fi][x.se])
					q.push_front(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se];
			}
		}
		if (x.se < m) {
			if (s[x.fi][x.se] == '.' && s[x.fi][x.se+1] == '#') {
				if (d[x.fi][x.se+1] > d[x.fi][x.se] + 1)
					q.pb(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se] + 1;
			} else {
				if (d[x.fi][x.se+1] > d[x.fi][x.se])
					q.push_front(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se];
			}
		}
	}
	print(d[n][m]);
	return 0;
}

123 Triangle

首先进行一次绝对值差分，让序列中的数都在 $0 \sim 2$ 中，显然无论什么情况后面的每个数只可能为 $0 \sim 2$ 。

如果此时的序列中存在 $1$ ，则意味着答案只可能是 $0$ 或 $1$ ；如果不存在 $1$ ，则答案只可能是 $0$ 或 $2$ 。

对于不存在 $1$ 的情况，我们可以将每个数都 $\div 2$ ，最后再将答案 $\times 2$ ，这显然是等价的。

于是现在的答案都只可能是 $0$ 或 $1$ 了，于是显然我们只用在模 $2$ 的情况下讨论。

考虑一次绝对值差分在模 $2$ 意义下的影响，可以发现等价于 $\operatorname{xor}$ 。

现在问题变为，给定一个 $0/1$ 序列，每次将相邻两个数 $\operatorname{xor}$ ，求最后剩下的数。

那么考虑每个数会被异或几次即可，设序列长度为 $n$ ，则位置 $i$ 上的数会被异或 $\binom {n-1}{i-1}$ 次。

这时候我们还要求出模 $2$ 意义下的组合数，一个简单的方法是计算每个阶乘的分解中 $2$ 的次数，将计算组合数时的除法改为做减法。则对于一个组合数，最后如果剩下的 $2$ 的次数为 $0$ ，则说明 $\bmod 2 = 1$ ，否则 $\bmod 2 = 0$ 。

对于阶乘的分解，可以先对每个数简单地求出分解中 $2$ 的次数，然后做前缀和即可。

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

const int N = 1e6 + 7;
int n, a[N], c[N];
char s[N];

int main() {
	rd(n), rds(s, n), --n;
	for (int i = 1; i <= n; i++) a[i] = abs(s[i] - s[i+1]);
	bool ok = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] == 1) ok = 1;
	if (!ok) for (int i = 1; i <= n; i++) a[i] >>= 1;
	for (int i = 1; i <= n; i++) {
		int x = i;
		while (!(x & 1)) ++c[i], x >>= 1;
		c[i] += c[i-1];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans ^= c[n-1] - c[i-1] - c[n-i] ? 0 : (a[i] & 1);
	if (!ok) ans <<= 1;
	print(ans);
	return 0;
}

Giant Graph

以下设 $n,m$ 同阶。

由于 $10^{18}$ 非常大，因此求最大独立集，相当于贪心地从权值大的往小的选，能选则选。

考虑 dp，设 $f_{x,y,z}$ 表示点 $(x,y,z)$ 是否要被选。

转移方程为 $f_{x,y,z} = \prod_{(x^\prime,y^\prime,z^\prime) \to (x,y,z)} [f_{x^\prime,y^\prime,z^\prime} = 0]$ ，其中 $(x^\prime,y^\prime,z^\prime) \to (x,y,z)$ 表示 $(x^\prime,y^\prime,z^\prime), (x,y,z)$ 之间有边且 $x^\prime + y^\prime + z^\prime \ge x + y + z$ 。

时间复杂度 $\mathcal O(n^3)$ ，显然过不了。

考虑如下这样一个博弈问题：

有三张 $n$ 个点的有向图，每张图在某个点上都有一个标记。

有两个人轮流进行移动，每次移动可以将一个标记从一条出边移动过去。

谁不能移动了谁就输了。

对于这样一个博弈问题，用 $\operatorname{SG}$ 函数可以解决。

然后可以发现，这个博弈问题的 $\operatorname{SG}$ 函数和上面那个 dp 的状态是一样的。

而这个博弈问题中，三张图之间相互独立。

这让我们想到了 $\operatorname{Nim}$ 游戏，即我们可以将三张图的 $\operatorname{SG}$ 函数分开算，最后 $\operatorname{xor}$ 起来得到原来的 $\operatorname{SG}$ 函数。 $\operatorname{SG}$ 函数为 $0$ 的点，即为原问题中要选择的点。

注意到，对于一个 DAG 博弈转移图， $\operatorname{SG}$ 函数值的上界是 $\mathcal O(\sqrt n)$ 的，因此我们可以 $\mathcal O(n)$ 求出答案。

const int N = 1e5 + 7;
const modint K = 1000000000000000000ll % P;
int n;
modint ans;
struct Graph {
	int n, m, sg[N], k;
	modint c[N];
	vi e[N];
	inline Graph() {}
	inline Graph(int n) : n(n) {}
	int SG(int x) {
		if (~sg[x]) return sg[x];
		map<int, bool> p;
		for (int y : e[x]) p[SG(y)] = 1;
		while (p[++sg[x]]);
		return sg[x];
	}
	inline void main() {
		rd(m);
		for (int i = 1; i <= n; i++) sg[i] = -1;
		for (int i = 1, x, y; i <= m; i++) {
			rd(x), rd(y);
			if (x > y) swap(x, y);
			e[x].pb(y);
		}
		for (int i = 1; i <= n; i++) if (!~sg[i]) SG(i);
		for (int i = 1; i <= n; i++) k = max(k, sg[i]), c[sg[i]] += K ^ i;
	}
} G[3];

int main() {
	rd(n);
	for (int i = 0; i < 3; i++) G[i] = Graph(n), G[i].main();
	for (int i = 0; i <= G[0].k; i++)
		for (int j = 0; j <= G[1].k; j++)
			ans += G[0].c[i] * G[1].c[j] * G[2].c[i^j];
	print(ans);
	return 0;
}

Merge Triplet

考虑已知每个序列，我们是如何构造排列的。

按照题意，每次选择最小的开头放入排列，然后扔掉。

这意味着，由于序列长度为 $3$ ，排列中一定不会出现连续四个（或以上）的数 $x_{1\dots 4}$ ，满足 $x_1 > x_{2\dots 4}$ 。

因此，最终的排列中，按照前缀 $\max$ 的位置划分，每一段的长度不超过 $3$ ，这是必要条件。

充分吗？不充分，比如 $2\ 1\ 4\ 3\ 6\ 5$ 就不可以。

我们发现，按照前缀 $\max$ 的位置划分，有三个长度为 $2$ 的段，而我们没办法讲其拼成两个长度为 $3$ 的序列。

于是另一个必要条件为，长度为 $2$ 的段个数不超过长度为 $1$ 的段个数。

充分吗？充分，因为一旦满足这个条件，我们就能构造出来序列。

那么考虑如何计数，设 $f_{i,j}$ 表示考虑前 $i$ 个数，长度为 $1$ 的段个数减去长度为 $2$ 的段个数为 $j$ 的方案数。

转移时枚举下一段的长度 $1/2/3$ 即可，如果长度不为 $1$ 还要额外乘上系数，具体见代码。

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

const int N = 2e3 + 7, M = N * 3;
int n;
modint f[M][M<<1], ans;

int main() {
	rd(n), rd(P), n *= 3;
	f[0][M] = 1;
	for (int i = 0; i < n; i++)
		for (int j = -i; j <= i; j++) {
			f[i+1][j+1+M] += f[i][j+M];
			f[i+2][j-1+M] += f[i][j+M] * (i + 1);
			f[i+3][j+M] += f[i][j+M] * (i + 1) * (i + 2);
		}
	for (int j = 0; j <= n; j++) ans += f[n][j+M];
	print(ans);
	return 0;
}

Topology

首先判合法性，显然一个合法点集的所有子集都应该合法，一个非法点集的所有超集都应该非法，特别地，空集必须合法。

判完之后考虑如何构造，考虑一个极小非法点集 $S$ 。我们如果构造出来一个从 $(0,0)$ 开始的环，使得它在 $S$ 非法，在 $S$ 的真子集合法，那么对于所有的极小非法点集如此构造后，将这些环在 $(0,0)$ 处接起来即可。

考虑对于一个点集 $S$ ，如何判断一个环合法：

从环的最左端开始，沿一个方向走一圈，穿过第 $i(\in S)$ 条线上方时记录一个 $u_i$ ，穿过下方时记录一个 $d_i$ ，这样得到一个字符串。
不断地在字符串中选择两个相邻且相同的字符删掉，如果能清空，则该点集合法，否则非法。

稍微画一下就能证明。

显然如果我们已知这个字符串，是可以还原出这个环的，因此问题转化为构造这个字符串。

考虑如下递归构造，一开始在 $(0,0)$ ：

若此时右边只剩下了一个点，则绕一个圈，即返回 $u_1d_1$ 。
否则穿过第一个点的上方，然后递归，得到字符串 $t$ ，然后从第一个点上方穿回来。
再从第一个点的下方穿过去，按照 $t^r$ 的方式走，然后再从第一个点下方穿回来。
返回字符串 $u_1tu_1d_1t^r d_1$ 。

稍微画一下同样能证明这个构造的正确性。

#define Fail prints("Impossible"), exit(0)
#define vp vector<pi>
int n, f[1<<8|1];
string s;
vp p[1<<8|1], ans(1, mp(0, 0));

inline bool pd(int i) {
	for (int j = (i - 1) & i; j; j = (j - 1) & i)
		if (s[j] == '0') return 0;
	return 1;
}

inline void merge(vp &a, vp b) {
	for (pi o : b) a.pb(o);
}

inline vp work(int i) {
	if (p[i].size()) return p[i];
	int j = i & -i, k = f[j];
	p[i].pb(mp(k, 1));
	p[i].pb(mp(k + 1, 1));
	vp t = work(i - j);
	merge(p[i], t);
	p[i].pb(mp(k + 1, 1));
	p[i].pb(mp(k, 1));
	p[i].pb(mp(k, 0));
	p[i].pb(mp(k + 1, 0));
	p[i].pb(mp(k + 1, 1));
	reverse(t.begin(), t.end());
	merge(p[i], t);
	p[i].pb(mp(k + 1, 1));
	p[i].pb(mp(k + 1, 0));
	p[i].pb(mp(k, 0));
	p[i].pb(mp(k, 1));
	return p[i];
}

inline vp get(pi a, pi b) {
	vp ret(1, a);
	if (a.se != b.se) return ret.pb(b), ret;
	while (a != b)
		a.fi += a.fi < b.fi ? 1 : -1, ret.pb(a);
	return ret;
}

inline vp update(vp a) {
	if (a.size() == 1u) return a;
	vp b;
	for (ui i = 1; i < a.size(); i++) merge(b, get(a[i-1], a[i]));
	return b;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> s;
	if (s[0] == '0') Fail;
	for (int i = 0; i < (1 << n); i++)
		if (s[i] == '1')
			for (int j = i; j; j = (j - 1) & i)
				if (s[j] == '0') Fail;
	for (int i = 0; i < n; i++) {
		f[1<<i] = i;
		p[1<<i].pb(mp(i, 1));
		p[1<<i].pb(mp(i + 1, 1));
		p[1<<i].pb(mp(i + 1, 0));
		p[1<<i].pb(mp(i, 0));
		p[1<<i].pb(mp(i, 1));
	}
	for (int i = 0; i < (1 << n); i++)
		if (s[i] == '0' && pd(i))
			ans.pb(mp(0, 1)), merge(ans, work(i)),
			ans.pb(mp(0, 1)), ans.pb(mp(0, 0));
	ans = update(ans);
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	prints("Possible");
	print(ans.size() - 1);
	for (pi o : ans) print(o.fi, o.se);
	return 0;
}

Jewelry Box

题目太神仙了，先咕咕咕着。