游戏

题面

Alice 和 Bob 又在一起在玩游戏，这次游戏的规则是：

1. Alice 先手，Bob 后手，轮流进行操作，共有 $m$ 轮操作，有一个集合初始为 $S=\{a_1,a_2,\cdots,a_n\}$ 。
2. 第 $i$ 轮操作有一个参数 $b_i$ ，当前轮的操作者有以下两个选择：保留 $S$ 中所有是 $b_i$ 倍数的数字，或者保留 $S$ 中所有不是 $b_i$ 倍数的数字。
3. 进行了 $m$ 轮操作后两人获得的权值是 $S$ 中的数字之和， $S$ 可以为空。

Alice 希望权值最小，Bob 希望权值最大，假设他们都足够聪明，那么游戏最终的权值是多少。

题解

也是比较技巧的题。对决策建树，树的每一层就是每一轮操作，若 $a_i$ 整除把他丢到左子树，反之亦然。然后就好统计答案了。

每次进行决策，如果他选择集合大小更小的那一侧，那么每次操作集合大小至少减半，只需要 $\log n$ 次操作就必定可以使答案为 $0$ ，考虑上“两人是轮流操作”的这个因素，当 $m>2\log n$ 的时候，答案不可能大于 $0$ 。同理答案也不可能小于 $0$ （因为后手可以采取同样的策略），因此答案一定是 $0$ 。复杂度 $\mathcal{O}(n\log n)$ 。

代码

const int N = 2e4 + 5, M = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	ll a[N], b[M], root;

	struct Tree {
		struct node {
			ll sum, l, r;
		} t[N * 30];
		int tot;

		void Insert (ll &p, ll dep, ll val) {
			if (!p) p = ++tot;
			if (dep > m) { t[p].sum += val; return; }
			Insert (val % b[dep]? t[p].l: t[p].r, dep + 1, val);
		}
		
		ll Query (ll p,	ll dep) {
			if (!p) return 0;
			if (dep > m) return t[p].sum;
			ll l = Query (t[p].l, dep + 1), r = Query (t[p].r, dep + 1);
			return (dep & 1)? min(l, r): max(l, r);
		}
	} tr;

	int main () {
		n = Read(), m = Read();
		if (m > 28) {puts("0"); return 0;}
		for (int i = 1; i <= n; i++) a[i] = Read();
		for (int i = 1; i <= m; i++) b[i] = Read();
		for (int i = 1; i <= n; i++) tr.Insert (root, 1ll, a[i]);
		printf ("%lld\n", tr.Query(root, 1ll));
		return 0;
	}
}

int main () {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	Main::main();
	return 0;
}