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

提示

Hint 1

如果两个人初始时没有城市相邻（假设中间空了一个中立城市），那么二人的策略是什么？

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)

。

code

CPP

#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;
}

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

文章操作

提示

解法

Hint 1

Hint 2

相关推荐

评论

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