Solution Set - CF787

Vive le R & M!

还被种草了 Hurt，真的颇有感触，但这是 Solution Set，就不写了。

A. The Monster

exgcd，但是发现 \(1 \leq a, b, c, d \leq 100\) 直接暴力枚举即可。我认为这是 \(O(1)\) 的，但题解认为是 \(O(n)\)，感觉不如原神。

B. Not Afraid

每一组里面只要有来自同一个宇宙的 Rick and Morty 就不可能都是坏的。等价于只要判断是否每一组都有 \(x\) 和 \(-x\) 同时存在即可。

C. Berzerk

难度骤升。显然是一个 bot 论。

被傻逼 bot 论整破防了。

Definition.

游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

这个有限步我们先忽略，是可以处理的。关键是这个与游戏者无关，看起来这里和游戏者有关，但是你可以把游戏者抽象成一个状态。。。这样就相当于是个公平组合游戏了（纯纯侠极霸说）。

然后这里不能硬上 dfs & SG 函数，因为 Loop 的存在会导致这个写法 \(O(n ^ 3)\)，得换用 bfs 的有向图游戏弄 \(O(n ^ 2)\)，然后就是很 trivial 的有一个状态能到达输状态就是赢状态，只能到达赢状态就是输状态，否则不能确定，就是 Loop。

我的写法还被卡空间（微笑），要写 short 才能过 /fn

namespace liuzimingc {
const int N = 7e3 + 5;
#define int short
#define endl '\n'

int n, out[N << 1], ans[N << 1];
set<int> s[2];
vector<int> e[N << 1];
queue<int> q;
bool vis[N << 1];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 0; i <= 1; i++) {
		int m, x;
		cin >> m;
		while (m--) {
			cin >> x;
			s[i].insert(x);
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= 1; j++) {
			for (const int &k : s[j]) {
				int pos = (i + k) % n;
				if (pos * 2 + !j == i * 2 + j) continue;
				e[pos * 2 + !j].push_back(i * 2 + j);
				out[i * 2 + j]++;
			}
		}
	for (int i = 0; i <= 2 * n + 1; i++) ans[i] = 2;
	ans[2] = ans[3] = 0;
	q.push(2);
	q.push(3);
	vis[2] = vis[3] = true;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (const int &v : e[u]) {
			if (ans[u] == 1) out[v]--;
			if (!out[v] && !vis[v]) ans[v] = 0, vis[v] = true, q.push(v);
			if (!ans[u] && !vis[v]) ans[v] = 1, vis[v] = true, q.push(v);
		}
	}
	for (int i = 0; i <= 1; i++)
		for (int j = 2; j <= n; j++) {
			if (ans[(j % n) * 2 + i] == 1) cout << "Win";
			else if (!ans[(j % n) * 2 + i]) cout << "Lose";
			else cout << "Loop";
			cout << " \n"[j == n];
		}
	return 0;
}
#undef int
} // namespace liuzimingc

D. Legacy

越做越感觉这是 educational round。C 博弈论，D 线段树优化建图，（SPOILER ALERT）E（根号）分治。

而且可喜可贺的是我们是学过线段树优化建图的，但是那天我请假了。

还是很 trivial，建完跑 Dijkstra 即可。

E. Till I Collapse

这道题是放在 vjudge 里的，标题是根号算法。但是这和根号算法有什么关系？

哦看标签可以知道是根号分治。

那么对于 \(k \leq \sqrt{n}\) 的情况直接暴力就是 \(O(n \sqrt{n})\) 的。

int calc(int i) {
	int tot = 0, lst = 1, ans = 1;
	for (int j = 1; j <= n; j++) {
		if (!vis[a[j]]) tot++, vis[a[j]] = true;
		if (tot > i) {
			ans++;
			tot = 1;
			for (int k = lst; k <= j; k++) vis[a[k]] = false;
			vis[a[j]] = true;
			lst = j;
		}
	}
	for (int k = lst; k <= n; k++) vis[a[k]] = false;
	return ans;
}

然后 \(k > \sqrt{n}\) 怎么做？我不会了。写了依托答辩，结果。。。

答案相同的一段一定连续，\(k > \sqrt{n}\) 时最多也只有 \(\sqrt{n}\) 段，二分相同的区间即可。时间复杂度应该是 \(O(n \sqrt{n} \log \sqrt{n})\) 的？然后显然不能直接对所有的 \(k\) 二分，不然会退化到 \(O(n ^ 2 \log n)\)。

但是其实有一个更加自然（？）的思路。首先答案序列单调不升是显然的，考虑分治。

void work(int l, int r, int x, int y) { // 计算区间 [l, r]，答案区间为 [x, y]
	if (l > r) return;
	int mid = l + r >> 1;
	ans[mid] = x == y ? x : calc(mid);
	work(l, mid - 1, ans[mid], y); // 左边答案不会更小
	work(mid + 1, r, x, ans[mid]); // 右边答案不会更大
}

这样写正确性是显然的，但是时间复杂度却很玄学。猜测是带了根号或者 \(\log\) 啥的。