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

· · 题解

感觉应该是黄题吧。

题目概述

一个数轴，前 k 个地给小 A，后面的地给小 B，小 A 先手，可以选择集结兵力或者进攻，进攻到其他领土需要满足大于对方的兵力，而小 B 可以等于对方的兵力，进攻之后兵力归进攻方。

问两个人都采取最优策略，谁会赢。

分析

一开始我还想如果是一张无向图那就有一点麻烦，但没想到这里只有一块相邻的地啊，那就好办了。

一个很显然的策略就是我把兵全部集结到我最后一个格子最后跟你决一死战就行了。但是这只考虑到了集结兵力，而且小 A 具有先手优势，所以可以采取先扩张再集结的办法。

扩张时应当先满足首要条件，但是你还需要判断扩张之后会不会遭到反噬——也就是扩张后小 B 反扩张你。那你这个操作就是无意义的，甚至是更劣的。

那我们的思路就出来了，从前到后扫一遍，搞一下前缀和，顺便判断一下能不能扩张即可。

代码

时间复杂度 \mathcal{O}(Tn)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
#define N 100005
using namespace std;
int n,a[N];
signed main(){
    int T;
    cin >> T;
    for (;T--;) {
        scanf("%lld",&n);
        int tot = 0;
        for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),tot += a[i];
        int sum = 0;
        for (int i = 1;i < n;i ++) {
            sum += a[i];
            int yc = (a[i + 1] < a[i] && a[i + 2] < a[i + 1] + a[i] ? a[i + 1] : 0);
            if (sum + yc > tot - sum - yc) putchar('1');
            else putchar('0');
        }
        putchar('\n');
    }
    return 0;
}
/*
1
4
1 2 1 3

*/