很有意思的一道题，感觉csp2020的T3和T4都比较有质量，属于考思维的题目。
题目链接：
https://www.luogu.com.cn/problem/P7078
题目大意：
有n条蛇，每条蛇都有一个体力值a[i]还有一个编号（1~n的编号）。这些蛇需要决斗，每轮决斗都是最强蛇考虑要不要吃掉最弱蛇。蛇的强弱我们以他们剩余的体力值作为判断，体力越多越强。假设有两条蛇体力相同，则编号大的更强。
那么对于每轮决斗，最强蛇有两种决策：
1.如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
2.如果选择不吃，决斗立刻结束。
每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。
现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。
n<=10^6
注意数据有T组，T<=10
思路：
人不如蛇系列。
看到题目，感觉是博弈啊。
我们从2条蛇开始考虑。假设n=2，必吃
假设n=3，我们有a1,a2,a3.那么若a3-a1<a2则不吃，否则吃。
那么n>3的时候呢？似乎不好判断。
但是对于n来说，如果n-1不吃，那么当前肯定吃了。否则就得考虑是否要冒险吃。
我这里一开始直接写了个递归，先考虑每次都吃，然后到只剩2条蛇的时候，往上返回结果。
那么假设dfs(n)表示还剩n条蛇的时候吃不吃,true表示吃，false表示不吃。
若dfs(n-1)为true，那么如果吃完变最弱的则返回false并且记录max（因为递归中已经知道下一次会吃了，所以如果此时冒险吃变成最弱，那就选择不吃），否则返回true（冒险吃）
若dfs(n-1)为false,那么dfs(n)返回true
那么我只要得到最大的不吃（即过程中记录的max）就是答案。
这样做可以拿40分。
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,idx;
}p[1000030],q[1000030];
int ans=0;
bool dfs(int n){
if(n==2)return true;
node w[20030];
for(int i=1;i<=n;i++)w[i].a=q[i].a,w[i].idx=q[i].idx;
node tmp;
tmp.a=q[n].a-q[1].a;tmp.idx=q[n].idx;
for(int i=n-1;i>1;i--){ //利用插入排序的方法插入元素
if(tmp.a<q[i].a)q[i+1].a=q[i].a,q[i+1].idx=q[i].idx;
else {
q[i+1].a=tmp.a;
q[i+1].idx=tmp.idx;
break;
}
}
for(int i=1;i<n;i++){
q[i].a=q[i+1].a;
q[i].idx=q[i+1].idx;
}
if(dfs(n-1)){
if(w[n].a-w[1].a<w[2].a||(w[n].a-w[1].a==w[2].a&&w[n].idx<w[2].idx)){ans=max(ans,n);return false;}
else return true;
}
else return true;
}
int main()
{
int T,n;
cin>>T;
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].a,p[i].idx=i;
for(int i=1;i<=n;i++)q[i].a=p[i].a,q[i].idx=p[i].idx;
while(T--){
for(int i=1;i<=n;i++)q[i].a=p[i].a,q[i].idx=p[i].idx;
ans=1;
dfs(n);
cout<<ans<<endl;
int k;
cin>>k;
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
p[x].a=y;
}
}
return 0;
}其实上面的算法，其中一个不放心的地方是冒险吃的时候。在上面的递归中，我们的做法是如果可以冒险，每次都选择冒险吃，由于是递归，所以返回来的时候就可以得到结果然后再次判断是否要吃或不吃。这么看来，感觉是没什么问题的。
看了正解，有一个比较重要的点需要证明的：
如果当前吃完以后不是最弱的，放心吃！
证明：若有a1<a2<...a(n-1)<an，那么an-a1>a(n-1)-a2
这意味着an吃完一次以后还是比a(n-1)吃完一次强。
即如果an吃掉a1以后不是最弱，a(n-1)不管选择吃不吃，an都可以不死。假设a(n-1)选择吃，那么an比a(n-1)还是强。假设a(n-1)选择不吃，本轮决斗结束，an不死。
也就是，我们一开始的时候可以直接模拟，如果当前吃了不是最弱的，可以一直模拟吃下去。
接下来考虑当前ai吃了变成最弱的时候
我们再分情况讨论一下,假设下一条蛇是a(i-1)：
①下一条蛇不吃，当前吃。
②下一条蛇吃，当前不吃
那么下一条蛇a(i-1)吃不吃呢？他考虑的问题其实和a(i)一样的，取决于下下条蛇。问题又变成了一个递归，那么什么时候结束呢？
（1）只剩2条蛇的时候（2）某一条蛇直接放心吃的时候
所以存在一个奇偶性的情况了。
我们把问题分成3个阶段：
阶段1：所有蛇放心吃阶段，吃了不是最弱。
阶段2：所有蛇冒险吃阶段，吃了是最弱。此时每条蛇吃不吃仅仅取决于他的下面那条蛇，因此一定是吃-不吃交替的。
阶段3：某一条蛇可以放心吃（只剩2条或者吃了不是最弱）
那么从阶段3到阶段2，中间的蛇的数量的奇偶性影响了阶段2的第一条冒险的蛇会不会多吃一次。
对于上述过程，我们可以利用set进行模拟。每次取出最大最小来进行情况的判断，这样由于set的存在，复杂度为O（nlogn）。可以得到70分。
#include<bits/stdc++.h>
using namespace std;
int n;
pair<int,int>p[1000030];
set<pair<int,int> >st;
int main()
{
int T;
cin>>T;
cin>>n;
for(int cas=1;cas<=T;cas++){
if(cas==1){
for(int i=1;i<=n;i++){
int x;
cin>>x;
p[i]=make_pair(x,i);
st.insert(p[i]);
}
}
else {
int k;
cin>>k;
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
p[x]=make_pair(y,x);
}
st.clear();
for(int i=1;i<=n;i++)st.insert(p[i]);
}
int flag=0;
int ans;
while(1){
if(st.size()==2){ //只剩两条，此时必吃。
st.erase(st.begin());
if(flag){
ans=ans-(ans-st.size())%2; //看阶段2的奇偶性
}
else ans=1;
break;
}
set<pair<int,int> >::iterator it;
it=st.end();it--;
st.erase(it);
pair<int,int>p1,pn;
pn=*it;
it=st.begin();p1=*it;
st.erase(it++);
st.insert(make_pair(pn.first-p1.first,pn.second));
if(st.begin()->second==pn.second){ //进入阶段2冒险吃
if(!flag)ans=st.size()+1,flag=1;
}
else { //放心吃阶段1和3
if(flag){ //阶段3
ans=ans-(ans-st.size())%2;
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}正解是使用2个双端队列模拟，由于我不会双端队列，先贴个代码：
#include<bits/stdc++.h>
using namespace std;
int n;
pair<int,int>p[1000030];
set<pair<int,int> >st;
int main()
{
int T;
cin>>T;
cin>>n;
for(int cas=1;cas<=T;cas++){
deque<pair<int,int > >dq1,dq2;
if(cas==1){
for(int i=1;i<=n;i++){
int x;
cin>>x;
p[i]=make_pair(x,i);
dq1.push_back(p[i]);
}
}
else {
int k;
cin>>k;
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
p[x]=make_pair(y,x);
}
for(int i=1;i<=n;i++)dq1.push_back(p[i]);
}
int ans;
while(1){
if(dq1.size()+dq2.size()==2){
ans=1;
break;
}
int p1,pn,id;
p1=dq1.front().first;dq1.pop_front();
if(dq2.empty()||!dq1.empty()&&dq1.back()>dq2.back()){
pn=dq1.back().first;
id=dq1.back().second;
dq1.pop_back();
}
else {
pn=dq2.back().first;
id=dq2.back().second;
dq2.pop_back();
}
pair<int,int>pp=make_pair(pn-p1,id);
if(dq1.empty()||dq1.front()>pp){
//进入第二阶段
ans=dq1.size()+dq2.size()+2;
int cnt=0;
while(1){
cnt++;
if(dq1.size()+dq2.size()+1==2){
ans-=(cnt+1)%2;
break;
}
int x,id;
if(dq2.empty()||!dq1.empty()&&dq1.back()>dq2.back()){
x=dq1.back().first;
id=dq1.back().second;
dq1.pop_back();
}
else{
x=dq2.back().first;
id=dq2.back().second;
dq2.pop_back();
}
pp=make_pair(x-pp.first,id);
if((dq1.empty()||pp < dq1.front())&&(dq2.empty()||pp < dq2.front()));
else {
ans-=(cnt+1)%2;
break;
}
}
break;
}
else {
dq2.push_front(pp); //放心吃的第一阶段
}
}
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号