写作背景

蒟蒻第一篇题解，代码改了十几次，码风不是很好烦请各位谅解。如果有错误或者更优的写法，欢迎大佬们指出！！！蒟蒻在此感激不尽%%%orz

题意分析

阅读题目，找出以下关键点：

多测
共有 $n$ 个城市，要求给出 $m=1, 2, 3, ...,n-1$ 时小L是否在每轮操作均最优的条件下胜利
在每轮对战中，由小L先手行动，两人交替进行。
每轮对战操作方式有3种：转移、攻占、不操作。
对于每次操作，必须在相邻城市间进行
小L与小K的攻占成功的条件存在差异：
- 小L一边的边界城市兵力严格大于小K一方的边界城市
- 而对于小K来说，边界兵力只要大于等于小L一方即可攻占
任意一方攻占对方的城市后，可以将对方的兵力据为己有
两人“绝顶聪明”，也就是说他们的每一次操作一定是在当前条件下最优的，如果某一步操作会使形势扭转，就不会进行。~~（由于忽略了这个点，笔者在此被折磨了半个小时）~~
输出长度为 $n-1$ 的 01 字符串

设计策略

1. 假如你是小L/小K，为了尽可能地攻下对方的城市，你会怎么做呢？

结合题意不难发现交战发生在边界，于是我们想到不惜一切代价将兵力集中在边界。

尽管刚开始时对方兵力可能会占优势，但是在我方士兵人数完全充足 ~~（这里有说法的）~~ 的情况下，对方兵力会被快速消耗殆尽。

由此可以看出，如果初始状态下一方总兵力占绝对优势，他总能获胜。

于是我们可以用前缀和表示双方初始地盘内的总兵力。

CPP

for (int i=1;i<=n;i++) {
        cin >> city[i];
        sum[i]=sum[i-1]+city[i];
    }
int sum_l=sum[m],sum_r=sum[n]-sum[m];

2. 假如你是生性多疑的小L，你预先不知道小K的兵力比你大/小多少，，你该如何防患于未然？

贪心的你~~不择手段地~~扩充自己的兵力。你想到了在符合规则的条件下先手攻占小K的城市。一方面使自己的初始兵力增大，另一方面使小K的初始兵力减少，最大化自己的赢面。

3. 钓鱼执法

神机妙算的你猜透了小K的心思，担心小K来一手 “欲擒故纵”，再 “关门打狗”。而让你先手攻占他的一个城市只是障眼法，其实更强的兵力还在后头等着你。

一旦你中计，那么将陷入万劫不复之境。

于是你学会了走一步看十步，先攻下对方一城，如果后面会被对方兵力反噬，那么就撤回操作。

~~（落子无悔）~~

反之，如果对方没有设下圈套，那就享受饕餮盛宴吧（）

于是你设计出了代码如下：

CPP

if (l>r&&m<=n-2){
            sum_l=sum[m+1],sum_r=sum[n]-sum[m+1],l=city[m]+city[m+1],r=city[m+2];
            if (r>l) sum_l=sum[m],sum_r=sum[n]-sum[m];
        }

注意：

当 $m>2$ 时，你没必要进行吞并操作以扩大自己的初始兵力。一方面会越界，另一方面你不难证明此时你的兵力已经足够，无论是否吞并都不会对战局结果造成太大影响
绝顶聪明的你发现先手进行攻占后会被对方反噬，于是你带着大军以迅雷不及掩耳之势回到原位，~~假装什么也没发生~~。

错误示例：
CPP
if (r>l) sum_l=sum[m-1],sum_r=sum[n]-sum[m-1];

这行代码表示进行操作后被反噬。这样写只能得96pts，笔者为了最后这一个点调了半个小时（）

AC代码

说了这么多，给大家奉上AC代码。

改过许多次，其中有些表述可以简化，看着比较难受，烦请大家多多包涵

CPP

#include <bits/stdc++.h>
#define int long long
#define N 100015
using namespace std;
int t, n;
int city[N], sum[N];
void solve(){
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> city[i];
        sum[i]=sum[i-1]+city[i];
    }
    int m=1;
    while (m<n){
        int l=city[m], r=city[m+1];
        int sum_l=sum[m],sum_r=sum[n]-sum[m];
        if (l>r&&m<=n-2){//只有m<=n-2时才有必要判断是否先吞并，否则会越界
            sum_l=sum[m+1],sum_r=sum[n]-sum[m+1],l=city[m]+city[m+1],r=city[m+2];
            if (r>l) sum_l=sum[m],sum_r=sum[n]-sum[m];//依题意，两人的操作一定是最优的，所以这里判断出有被吃掉的风险就应该撤回操作，而不是傻乎乎地被对面吃掉
        }
        if (sum_l>sum_r) cout << 1;
        else cout << 0;
        m++;
    }
    cout << endl;
}
signed main(){
    cin >> t;
    while (t--) solve();
    return 0;
}

总结

初始兵力占 “绝对优势” 的一方一定能够胜利。
我们通过贪心 “尽可能地” 扩大自己的初始优势。
扩大初始优势的前提是这一步不会引起后面更大的反噬。
我们可以试着进行操作扩大初始优势，如果操作不优，需要直接撤回操作。

总而言之，这是一道非常优美的贪心题，它引导我们从模糊地如何决出胜负，一步一步深入思考 “怎么最大化赢面” 到 “什么情况下不能操作”，体现了贪心思想的极致运用。

最后，祝各位 NOIP2025 RP++ ，贪心一眼看出正解，代码一遍就过！！！

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

文章操作