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

· · 题解

提示

::::success[提示]{open} :::success[Hint 1] 如果两个人初始时没有城市相邻（假设中间空了一个中立城市），那么二人的策略是什么？ ::: :::success[Hint 2] 原题和 Hint 1 中的问题区别在哪？ ::: ::::

解法

Hint 1

注意到两个城市交火并不是一换一或者别的之类的，而是哪边人多，另一边就全部投降。那么很自然的想到，如果它们俩不相邻，双方的策略一定都是将所有士兵全部聚集在一个格子上，再进行攻击。

Hint 2

正解。

发现原问题和弱化版（Hint 1）仅差一个相不相邻。根据我们在 Hint 1 中发现的性质：

双方的策略一定都是将所有士兵全部聚集在一个格子上，再进行攻击。

可知，我们只需要比较小 L 和小 K 的总兵力即可。因为我们需要判断的是小 L 能否必胜，所以我们考虑算出小 L 可以获得的最大兵力。

而小 L 先手和有国家相邻这两条性质非常有用，可以想到，如果 a_m>a_{m+1}，那么小 L 就可以在第一回合中将第 m+1 个城市攻陷，获得更多的兵力。在这之后，由于双方都绝顶聪明，所以一定尽量不会接触对方，也就没有兵力的增加或减少。

但是有一种情况：若 a_{m+2}\ge a_m+a_{m+1}，那么根据题设，攻陷第 m+1 个城市之后这些兵都要移动到这个城市来，此时小 K 可以趁机用第 m+2 个城市的兵力将小 L 的 a_m 个兵抢过来，这样小 L 不仅没有赚，反而亏了。

整理一下，当 a_m>a_{m+1} 且 a_{m+2}<a_m+a_{m+1} 时，小 L 可以额外获得 a_{m+1} 的兵力；否则就只能获得初始的 a_1+a_2+\dots+a_m 的兵力了。用总兵力减去小 L 兵力可以得到小 K 的，比较大小即可。可以用前缀和加速计算。

时间复杂度 O(n)。

:::info[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005], s[100005];
int main() {
    int T; cin >> T; while(T--) {
        int n; cin >> n;
        for(int i = 1;i <= n;i++)
            cin >> a[i],
            s[i] = s[i-1] + a[i];
        for(int i = 1;i < n;i++) {
            ll s1 = s[i], s2 = s[n] - s[i];
            if(a[i] > a[i+1] && ((i + 2) > n || a[i+2] < (a[i] + a[i+1]))) 
                s1 += a[i+1], s2 -= a[i+1];
            cout << (s1 > s2);
        }
        cout << endl;
    }
    return 0;
}

:::