题解：P14520 【MX-S11-T1】战争游戏

· · 题解

前言

为了方便描述，进行一些口语化的定义 QwQ

本文中的后撤 前移 指题目中的转移操作

本文中的吃掉 指题目中的攻占操作

本文中的前 后指小 L 和小 K 相对的方向。具体地，小 L 的 前 指 数组下标增大的方向，后指数组下标减少的方向。相对地，小 K 的方向定义则刚好相反。

题目分析

注意到获胜条件为攻占全部城市。

所以双方的最优策略一定是尽可能地集中更多兵力，尝试在最后使己方的总兵力大于对方的总兵力。

小 L 先手，对于每个不同的 m，他接下来的操作有两种选择：

首先是前一种情况。执行这种策略必须同时满足两个条件：

  1. 对于当前的 m，满足 a[m]>a[m+1]。这是题目攻占操作的必要要求。

  2. 对于当前的 m，满足 a[m]+a[m+1]>a[m+2]。若不满足此条件，如果小 L 向前一步吃掉小 K 的兵力，在接下来小 K 的回合中处于这个位置的兵力会被小 K 吃掉，得不偿失。这里不能取等，因为题目中小 K 吃掉小 L 的条件是大于等于而不是大于。

在这里，向前吃掉这个操作仅能进行最多一步，因为若满足条件，小 K 的最优策略当然是一直往后撤，防止继续被小 L 吃兵力。由于有回合差，小 L 一直往前是追不到的。

那么在这种情况下，小 L 最后可得到的总兵力为：

\sum_{i=1}^{m+1} a[i]

同理，小 K 最后可得到的总兵力为：

\sum_{i=m+2}^{n} a[i]

再然后是第二种情况，显然与第一种情况相比仅有\text a[\text m] 这一项的变化。

第二种情况小 L 最终可得到的总兵力：

\sum_{i=1}^{m} a[i]

同理，小 K 最终可得到的总兵力：

\sum_{i=m+1}^{n} a[i]

现在，我们得到了双方最终的总兵力，只需要进行比较即可。需要注意的是，题目要求是小 L 获胜才输出 1。所以此步判断同样不能取等。

对于每个测试点我们进行一个前缀和操作，以快速求出不同的 m 所对应的双方总兵力。前缀和的时间复杂度是 O(n) ,遍历 m 的时间复杂度是 O(n)，总时间复杂度为 O(nT)，足以通过本题。

代码

#include<bits/stdc++.h>
#define us unsigned
#define ll long long
#define ci const int
#define cd const double
#define pb push_back
#define ppb pop_back
#define gc getchar
#define ppct __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
int t;
int n;
ll a[100010],s[100010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;++i)
            cin>>a[i],s[i]=a[i]+s[i-1];
        for(int m=1;m<n;++m){
            ll L,K;
            if(a[m]>a[m+1]&&a[m+2]<a[m]+a[m+1]){
                L=s[m+1]-s[0];
                K=s[n]-s[m+1];
            }
            else{
                L=s[m]-s[0];
                K=s[n]-s[m];
            }
            if(L>K)
                cout<<1;
            else
                cout<<0;
        }
        cout<<'\n';
    }
    return 0;
}