[ARC116F] Deque Game

博弈。

考虑当 $k=1$ 且 $A$ 为先手时，手玩发现，最后剩下的都是中间两个或三个，即（记 $m=\frac{n+1}{2}$：
{ max ⁡ ( a n 2 , a n 2 + 1 ) n ≡ 0 ( m o d 2 ) max ⁡ ( min ⁡ ( a m − 1 , a m ) , min ⁡ ( a m , a m + 1 ) ) n ≡ 1 ( m o d 2 )

{max(a2n​​,a2n​+1​)max(min(am−1​,am​),min(am​,am+1​))​n≡0(mod2)n≡1(mod2)​
若 $B$ 先手，$\max$ 和 $\min$ 调换即可。

对于 $n$ 为偶数的情况，分类讨论：若 A 的目标在中间两数，则 $A$ 有策略使得最后剩下中间两数；反之，若 A 的目标不在中间两数，则 $B$ 有策略使得最后剩下中间两数。最后发现，A 只能取中间两数最大值。

$n$ 为奇数同理，最后只能剩下中间三数，讨论一下即可。

无奈考场上只能想到这步，还没有数据范围或性质启发，只能止步于此。

通过上面的式子不难得到，当序列长度为奇数时，$A$ 先手和 $A$ 后手的答案满足：
$$\max (\min (a_{m-1},a_m),\min (a_m,a_{m+1}))\le \min (\max (a_{m-1},a_m),\max (a_m,a_{m+1}))$$
$A$ 希望当序列长度为奇数时自己后手，当序列长度为偶数时自己先手。

$B$ 希望当序列长度为奇数时自己后手，当序列长度为偶数时自己先手。

所以最后策略为 $A$ 开始时操作偶数长度序列，$B$ 会选另一个偶数长度序列，直到选完。

再根据偶数长度序列个数奇偶性判断谁先选奇数长度序列即可。

对于偶数长度序列的选取，设 $x$ 表示 $[1,n-1]$ 先手的答案，$y$ 表示 $[2,n]$ 先手的答案，那么 $A$ 会选 $x,y$ 差值最大的 $\max (x,y)$，$B$ 会选 $x,y$ 差值最大的 $\min (x,y)$，优先队列维护即可。

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

#include
using namespace std;
#define int long long
typedef long long ll;
#define ha putchar(' ')
#define he putchar('\n')
inline int read() {
	int x = 0;
	char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}
inline void write(int x) {
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}
const int _ = 2e5 + 10;
int k, m, ans, l[_];
vector<int> d[_];
priority_queue<int> q;
int f(int t, int i) {
	if (l[i] == 2) return t == 0 ? d[i][1] : d[i][0];
	if (!m) return max(min(d[i][l[i] / 2 + t - 1], d[i][l[i] / 2 + t]), min(d[i][l[i] / 2 + t], d[i][l[i] / 2 + t + 1]));
	else return min(max(d[i][l[i] / 2 + t - 1], d[i][l[i] / 2 + t]), max(d[i][l[i] / 2 + t], d[i][l[i] / 2 + t + 1]));
}
signed main() {
	k = read();
	for (int i = 1; i <= k; ++i) {
		l[i] = read();
		for (int j = 1; j <= l[i]; ++j) d[i].emplace_back(read());
		if (!(l[i] & 1)) m ^= 1;
	}
	for (int i = 1; i <= k; ++i)
		if (l[i] & 1) {
			if (l[i] == 1) ans += d[i][0];
			else ans += f(0, i);
		} else {
			int x1 = f(-1, i), x2 = f(0, i);
			int t1 = max(x1, x2), t2 = min(x1, x2);
			q.push(t1 - t2), ans += t2;
		}
	while (!q.empty()) {
		ans += q.top();
		q.pop();
		if (!q.empty()) q.pop();
	}
	write(ans), he;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53