ABC261Ex
显然有一个倒序DP
\[\begin{cases} f_{i,0}=\min_{i\to j}f_{j,1}+w(i,j)\\ f_{i,1}=\max_{i\to j}f_{j,0}+w(i,j)\\ \end{cases} \]目标 \(f_{S,0}\)
可以看作用 dijkstra 跑最短路。
当 \(f_{i,1}\) 的所有 \(f_{j,1}\) 确定时才确定 \(f_{i,1}\)，再将其扔到最短路里面跑。
如果无法确定一个f，就说明它后续会一直更新？
首先边界是可以确定的
那么min如果钦定只能由已经OK的1来转，一定是正确的，后续的1不可能更新它
而更新完了的1也是可以如此操作的
agc048D
可以发现的是，当某一堆无穷多的时候，先拿到这一堆的人获胜，因为它可以磨到另一个人操作完
打个爆搜看看
啊
我们发现若固定局面不变，单独增加第一堆的个数，其胜负呈现00000000000001111111111111，单独增加最后一堆其胜负呈现111111111111110000
说明这玩意单调。。。。。。。。。。。
那考虑维护分界点，设f[l,r],g[l,r]分别表示当前先手，若先手赢得[l,r]，则当前第一堆最少需要 \(f[l,r]\) 个，当前后手，若后手赢得 \([l,r]\)，则当前最后一堆至少需要 \(g[l,r]\) 个
但是有什么转移的规律吗
显然有单调性随着端点移动
打一个 \(f[l,r]\) 和 \(g[l,r]\) 的表看看
发现
\(f[l,r]=a[r]-g[l+1,r]+1+f[l,r-1]\)，当 \(g[l+1,r]>a[r],f[l,r]=1\)
arc116F
显然ICG
显然的一个贪心策略是删除两端对于自己而言不优的那个元素。
显然我要大的肯定是删小的，反之同理
显然每个独立，不然可以交换操作顺序，会抢
而且一定有办法让答案取到中间的数字，且这样做应当是最优的
那么当n是偶数的时候，显然是留下 \(mid,mid+1\) 里对先手有利的一个，因为最后一步是先手
否则n是奇数的时候，mid显然是可以保留的，但是后面后手可以想办法让你取小的，所以应该是\(a[mid],(a[mid+1].a[mid-1]\) 里较先手优的)中较先手劣的
所以长度为奇数的显然独立操作不影响先后手，而长度为偶数的显然也是轮流操作
然后长度为偶数的会交替先后手，所以应该按照贡献贪心取？
考虑枚举第一步进行的操作之后能够得到的答案
先手肯定取较大者，后手肯定取较小者，设弄出这玩意是 \((a,b)\)
考虑邻项交换，\((a[i],b[i])\)
如果交换前更优，且先是先手操作就有 \(a[i]+b[i+1]>a[i+1]+b[i]\implies a[i]-b[i]>a[i+1]-b[i+1]\)
排序取即可。
做完了？
做完了。
「省选联考 2023 day2」过河卒
智障模拟题，直接不讲
「HAOI2015」数组游戏
根据翻硬币游戏的结论，我们只关心最开始的白棋位置，变为求解若干 100000000 局面的 \(sg\) 值。
长度应当是某个 \(\lfloor\frac{n}{x}\rfloor\) ，所以共有 \(O(\sqrt n)\) 种不同 SG值。
对于每种值，我们考虑其后继局面，例如 10000，其后继是 00000,01000,01100,01110,01111，相当于是这些局面的 \(mex\)
发现每个局面的 \(sg\) 值是一个前缀异或和，从当前白棋位置开始，最初是 \(0\)。利用数论分块再优化即可。
复杂度应当是 \(O(n^{\frac{3}{4}})\) 级别的，也不太会证明。
标签：局面,一堆,博弈论,mid,显然,先手,专练,操作 From： https://www.cnblogs.com/spdarkle/p/18447302