题解：P14520 【MX-S11-T1】战争游戏
写作背景
蒟蒻第一篇题解，代码改了十几次，码风不是很好烦请各位谅解。如果有错误或者更优的写法，欢迎大佬们指出！！！ 蒟蒻在此感激不尽%%%orz
题意分析
阅读题目，找出以下关键点：
- 多测
- 共有
n 个城市，要求给出m=1, 2, 3, ...,n-1 时小L是否在每轮操作均最优的条件下胜利 - 在每轮对战中，由小L先手行动，两人交替进行。
- 每轮对战操作方式有3种：转移、攻占、不操作。
- 对于每次操作，必须在相邻城市间进行
- 小L与小K的攻占成功的条件存在差异：
- 小L一边的边界城市兵力严格大于小K一方的边界城市
- 而对于小K来说，边界兵力只要大于等于小L一方即可攻占
- 任意一方攻占对方的城市后，可以将对方的兵力据为己有
- 两人“绝顶聪明”，也就是说他们的每一次操作一定是在当前条件下最优的，如果某一步操作会使形势扭转，就不会进行。
（由于忽略了这个点，笔者在此被折磨了半个小时） - 输出长度为
n-1 的 01 字符串设计策略
1. 假如你是小L/小K，为了尽可能地攻下对方的城市，你会怎么做呢？
结合题意不难发现交战发生在边界，于是我们想到不惜一切代价将兵力集中在边界。
尽管刚开始时对方兵力可能会占优势，但是在我方士兵人数完全充足 （这里有说法的） 的情况下，对方兵力会被快速消耗殆尽。
由此可以看出，如果初始状态下一方总兵力占绝对优势，他总能获胜。
于是我们可以用前缀和表示双方初始地盘内的总兵力。
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来一手 “欲擒故纵”，再 “关门打狗”。而让你先手攻占他的一个城市只是障眼法，其实更强的兵力还在后头等着你。
一旦你中计，那么将陷入万劫不复之境。
于是你学会了走一步看十步，先攻下对方一城，如果后面会被对方兵力反噬，那么就撤回操作。
（落子无悔）
反之，如果对方没有设下圈套，那就享受饕餮盛宴吧（）
于是你设计出了代码如下：
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 时，你没必要进行吞并操作以扩大自己的初始兵力。一方面会越界，另一方面你不难证明此时你的兵力已经足够，无论是否吞并都不会对战局结果造成太大影响 - 绝顶聪明的你发现先手进行攻占后会被对方反噬，于是你带着大军以迅雷不及掩耳之势回到原位，
假装什么也没发生。错误示例：
if (r>l) sum_l=sum[m-1],sum_r=sum[n]-sum[m-1];这行代码表示进行操作后被反噬。这样写只能得96pts，笔者为了最后这一个点调了半个小时（）
AC代码
说了这么多，给大家奉上AC代码。
改过许多次，其中有些表述可以简化，看着比较难受，烦请大家多多包涵
#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++ ，贪心一眼看出正解，代码一遍就过！！！