[??记录]ARC116F Deque Game
command_block
2021-10-28 10:18:55
**题意** ： 给出 $k$ 个序列，第 $i$ 个序列 $S_i$ 的长度为 $n_i$ 。
A 和 B 用这些序列玩游戏，两人轮流进行下列操作，直到所有序列的长度都变为 $1$。
- 删除某个（长度至少为 $2$ 的）序列的开头或结尾。
A 先手。A 想要最大化最终剩下的 $k$ 个元素的和，而 B 想要最小化，求最终这 $k$ 个元素的和。
$k,\sum_i n_i\leq 2\times1 0^5$ ，时限$\texttt{2s}$。
------------
先观察只有一个序列的情况。
记 $f(S)$ 为 $S$ 的答案。
- $n=1$，B 先手：$f(S)=S_1$ 。
- $n=2$，A 先手：$f(S)=\max(S_1,S_2)$ 。
- $n=3$，B 先手：$f(S)=\min\Big(\max(S_1,S_2),\max(S_2,S_3)\Big)=\max(S_2,\min(S_1,S_3))$ 。
- $n=4$，A 先手， ：$f(S)=\max\Big(\max(S_2,\min(S_1,S_3)),\max(S_3,\min(S_2,S_4))\Big)=\max(S_2,S_3)$ 。
如此不难归纳证明：
- $n$ 为偶数，A 先手时， $f(S)=\max\big(A_{n/2-1},A_{n/2}\big)$ 。
- $n$ 为奇数，B 先手时， $f(S)=\max\big(A_{(n+1)/2},\min\big(A_{(n+1)/2-1},A_{(n+1)/2+1}\big)\big)$ 。
由于 $\min$ 和 $\max$ 对称，先后手反过来也类似：
- $n$ 为偶数，B 先手时， $f(S)=\min\big(A_{n/2-1},A_{n/2}\big)$ 。
- $n$ 为奇数，A 先手时， $f(S)=\min\big(A_{(n+1)/2},\max\big(A_{(n+1)/2-1},A_{(n+1)/2+1}\big)\big)$ 。
------------
准备工作：比较对于一个序列，先手赚还是后手赚。
- $n$ 为偶数：双方都是先手更赚。
$\max\big(A_{n/2-1},A_{n/2}\big)\geq \min\big(A_{n/2-1},A_{n/2}\big)$
- $n$ 为奇数：双方都是后手更赚。
$\min\big(A_{(n+1)/2},\max\big(A_{(n+1)/2-1},A_{(n+1)/2+1}\big)\big)\leq \max\big(A_{(n+1)/2},\min\big(A_{(n+1)/2-1},A_{(n+1)/2+1}\big)\big)$
因为前者至多是 $A_{(n+1)/2}$ ，后者至少是 $A_{(n+1)/2}$。
接着我们来研究多个序列的情况，可以归纳证明：
- 若所有 $n_i$ 均为奇数，先手操作一次后，会形成一个偶序列，则后手必定接着操作这个偶序列。
答案即为各个序列的答案的和。
- 若存在偶序列，则先手必选一个偶序列操作。
这可以说明两人必定先瓜分完偶序列，然后变为奇数序列的情况。
注意瓜分完之后先后手可能会变化。
对于第 $i$ 个序列，记操作一次后的 $f$ 的较大值（要考虑先后手）为 $a_i$ ，较小值为 $b_i$ 。
若让 A 操作，则会选 $a_i$ ，B 选 $b_i$ 。按照 $a_i-b_i$ 从大到小排序，按这个顺序瓜分。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 200500
using namespace std;
int c1,m,a[MaxN],fA[MaxN],fB[MaxN],gA[MaxN][2],gB[MaxN][2],s[MaxN],tn;
bool e[MaxN];
int main()
{
scanf("%d",&m);
for (int k=1,n;k<=m;k++){
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
if (n==1)fA[k]=fB[k]=a[1];
else if (n&1){
int mid=(n+1)/2;
fA[k]=min(a[mid],max(a[mid-1],a[mid+1]));
fB[k]=max(a[mid],min(a[mid-1],a[mid+1]));
}else {
c1++;e[k]=1;
int mid=n/2;
fA[k]=max(a[mid],a[mid+1]);
fB[k]=min(a[mid],a[mid+1]);
if (n==2){
gB[k][0]=gA[k][0]=a[1];
gB[k][1]=gA[k][1]=a[2];
}else {
gA[k][0]=min(a[mid],max(a[mid-1],a[mid+1]));
gB[k][0]=max(a[mid],min(a[mid-1],a[mid+1]));
mid++;
gA[k][1]=min(a[mid],max(a[mid-1],a[mid+1]));
gB[k][1]=max(a[mid],min(a[mid-1],a[mid+1]));
}
}
}
ll ans=0;
for (int i=1;i<=m;i++)if (e[i]){
int a,b;
if (c1&1){a=gB[i][0];b=gB[i][1];}
else {a=gA[i][0];b=gA[i][1];}
if (a<b)swap(a,b);
ans+=b;s[++tn]=a-b;
}else {if (c1&1)ans+=fB[i];else ans+=fA[i];}
sort(s+1,s+tn+1);
for (int i=tn;i>=1;i-=2)ans+=s[i];
printf("%lld",ans);
return 0;
}
```