本文没有正确格式，请移步标题链接。

看过题解区思路，感觉和我的想法殊途同归，尤其是题解区第一篇，那句“如果吃了之后变成最弱的蛇了，到底选择吃不吃呢？这个问题就变成了一个递归的问题了，直到某条蛇吃了之后不是最弱的蛇或者只能下两条蛇为止。”

现在介绍我的思路，当然有极大可能是错的，所以这不应该算作在讨论区发题解：

首先我们发现，整个状态空间是由一条链（在所有蛇不考虑自己存亡下一个确定的“食物链”）和一个超级汇点（结束状态点）组成，所以我们可以通过比较成熟的方法得到整个状态空间，不再赘述。

然后我考虑从后往前，假设某一个局面在前面所有蛇都是先知的情况下可达，同时之后的局面都已经检查完毕，维护得到一个（从后往前检查）到目前为止合法的最靠后的最后一步（边界），那么我们可以得到当前这条强大蛇是否会在后面被吃，如果被吃，那么他会选择前移边界到（从前往后的）上一步，直接结束，因为如果确实如我们所愿，这一步可达，而且这条蛇吃了，那么这条蛇一定会在在我们目前维护的边界之前的某次操作中被吃，同时保证在这条蛇被吃之前不会有其他曾经强大过的蛇被吃（否则考虑这一步我们不更新边界，（从后往前的）之后某一次更新时，再像这一步一样，边界会前移到更靠前的位置，显然越晚更新，从答案的角度讲，越劣）；否则他肯定会吃，因为目前来看他没有危险。这个思路也可以被成熟的做法实现，不再展开。

目前看来，好像我与题解区大部分题解思路没有大区别。

那么我的问题是什么呢？经过我的检查，所有我错的数据的 n 都是偶数，我的错误输出都是奇数，答案都是偶数，而且相差 1。同时我检查了部分数据（其实应该相当有代表性，或者如果其他数据结构并非如此，也不妨碍我们先思考这个比较典型的结构），发现它们的“食物链”具有相同的结构：首先一堆正常的吃，然后从答案附近的某一个位置开始，这一轮的强者下一轮就会成为食物（这也是本文开始我引用的那句话的情况），直到最后（第 n−1 轮）。

那么请让我按照我的思路分析：

第 n−1 轮的强者肯定要吃，因为显然他没有任何危险；
第 n−2 轮的强者不敢吃，因为一旦他吃了，下一轮就会被吃掉；
第 n−3 轮的强者“知道”就算他吃了，下一轮也不会被吃掉，所以大胆吃；
…
食物链不再具有这种结构。

我们发现，因为 n 是偶数，所以始终是奇吃偶不吃。

现在，假如从第 i 轮开始，食物链具有这种结构，并且第 i 轮的强者下一轮被吃，那么：

如果 i 为偶数，那么答案就是 i−1，因为本轮的强者肯定不敢吃，否则立刻就被吃掉；
否则，答案是 i，因为就算下一轮可能被吃，下一轮的强者也不会吃；

考虑到蛇都是“先知”，所以他们也会推演之后其他强大蛇的最优做法，所以按照我的思路，答案确实应该是偶数。

我到现在没有发现我和常规做法思路的最本质区别，也不清楚孰对孰错。

如果有高手发现我是错的，或是觉得有必要确认一下食物链的结构是否真的如此，可以 @ 我，我会补发几组我的样例模拟，同时也欢迎高手自行模拟，因为我的实现可能从头到尾都是错的。

现在附上我的代码，可能会有些丑陋：

#include #include #include using namespace std; const int N=1e6+10,P=1e9+10; struct node{ int pla,nu; }dl[N]; int t,n,k; int id,a[N],tot; int bc[N]; int b[N]; deque q1,q2; int main(){ scanf("%d",&t); for(int tt=1;tt<=t;tt++){ if(tt1){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); } else{ scanf("%d",&k); while(k--){ scanf("%d",&id); scanf("%d",&a[id]); } } q1.clear(),q2.clear(); tot=0; for(int i=1;i<=n;i++) bc[i]=0; for(int i=n;i;i--) q1.push_back(node{i,a[i]}); while(q1.size()+q2.size()>1){ node s1,s2,g,h; if(q1.size()) s1=q1.front(); else s1=node{-1,-1}; if(q2.size()) s2=q2.front(); else s2=node{-1,-1}; if(s1.nus2.nu) g=s2,q2.pop_front(); else{ if(s1.nu<s2.nu) swap(s1,s2),q2.pop_front(); else q1.pop_front(); g=s1; } if(q1.size()) s1=q1.back(); else s1=node{-1,P}; if(q2.size()) s2=q2.back(); else s2=node{-1,P}; if(s1.nus2.nu) h=s1,q1.pop_back(); else{ if(s1.nu>s2.nu) swap(s1,s2),q2.pop_back(); else q1.pop_back(); h=s1; } if(g.nu<h.nu||(g.nuh.nu&&g.pla<h.pla)) break; dl[++tot]=node{g.pla,h.pla}; g.nu-=h.nu; q2.push_back(g); } for(int i=tot;i;i--){ bc[dl[i].nu]++; if(bc[dl[i].pla]){ for(;tot>=i;tot--){ bc[dl[tot].nu]--; } } } printf("%d\n",n-tot); } return 0; }

多谢！