2024.8.5

现在是 \(20:45\)，场上只有三个小学生改出来 \(\text{T4}\) 了，你校小学生太可怕。不想写 \(\text{T4}\) 了，还有一个小时写写总结吧。

今天大爆炸，无论是思维上还是码力上还是读题上。
\(0+10+40+0\)，真的要挂到地板上了（我发现一个规律，每次比赛 \(\text{T3}\) 的分都是最高的。

T1 逆流而上

今天的 \(\text{T1}\)，还是像往常一样的 shi。

题意：给一个 \(01\) 串，\(A,B\) 两人先后轮流操作，都以最优方式，谁不能操作为输。问谁赢。操作方式为将以下四种之一的串反转：\(\text{"10","100","110","1010"}\)。

一上来又是猜结论。哎我们观察发现能反转的里面都带 \(10\)，那么考虑从左往右找 \(10\)，统计个数，诶我们发现两个 \(10\) 并在一起可以一次操作搞掉，于是我们手模发现当扫到一个地方发现这个位置之后的 \(10\) 个数为奇数，那么它就会赢。因为：\(“ABABA”\)，这是个奇数次操作，最后一次刚好停在 \(A\) 手上，且第一次是 \(A\)，于是就有了上述结论。然后又想到一个 \(1010\) 是一个关键操作，因为他可以转变奇偶性，然后对于奇偶情况分类讨论……

然后一个小时过去了，测一下第一个样例过了。后面的样例没一个对的，然后发现思路假了，就陷进去了，再也想不出什么新思路，甚至暴力也不会打，就死了。

来看看正解是怎么想的。首先最终状态一定是左边一坨 \(0\)，右边一坨 \(1\)，\(10\) 不能穿插着放，因为只要能放了，必然能反转。所以相当于就是要把所有的 \(1\) 往右边换，所有的 \(0\) 往左边换。呃呃然后你看看操作类型：把 \(10\) 反转成 \(01\)，相当于把逆序对减少了 \(1\)，\(100\) 反转是把逆序对减少了 \(2\)，\(110\) 也是把逆序对减少了 \(2\)，\(1010\) 还是把逆序对减少了 \(2\)。所以我们发现当只有一个逆序对时，肯定是类似于 \(00000010111111\) 这种情况，即中间只有一个 \(10\)，两边都是好的；那其余情况的逆序对肯定都至少是 \(2\)。那么肯定就至少会包含 \(100,110,1010\) 中的一个。我们再仔细看看反转这些串发生了什么本质上的变化：\(100\) 反转成 \(001\) 其实就是把 \(1\) 移动到最右边；\(110\) 反转其实就是把 \(0\) 移动到最左边；\(1010\) 其实就是把最左边的 \(1\) 移动到最右边。那么这每一个逆序对 \(-2\) 的操作其实都在向最终序列靠近。又可以看到这些逆序对 \(-2\) 的操作其实是可以拆出来逆序对 \(-1\) 的操作的。因为他们里面都包含 \(10\)，你可以单独拆出来 \(10\) 进行逆序对 \(-1\) 的操作。

综上得到如下结论：

• 当总逆序对为 \(3\) 的倍数时，后手可以使它始终维持为 \(3\) 的倍数（因为先手给一个 \(-2\) 后手就能还上一个 \(-1\)）。
• 当总逆序对不为 \(3\) 的倍数时，先手总可以使它成为 \(3\) 的倍数（同上）。

所以： \(n \mod 3 = 0\) 时，后手胜；否则先手胜。

这其实是一个比较经典的博弈论问题了，或者说你观察题目名称“逆流而上”是不是也能看出来逆序对？然后观察观察样例输出和逆序对的关系也许就能发现结论。呃呃，以后 \(\text{T1}\) 就当结论题做。

T2 致命冲击

什么鬼，这不就是纵使日薄西山。

对于一个长度为 \(n\) 的整数序列 \(a_n\)，它的权值定义如下： 找到序列中最大的数 \(a_x\) ,将 \(a_{x-1},a_{x},a_{x+1}\) 均减 1. 如果有多个最大的数则取标号最小的那一个。

重复进行以上操作直到序列中不存在正数，操作的次数就是这个序列的权值。

现在给出 \(a_n\) 并有 \(q\) 次修改，每次将某个数修改。在每次修改后 \(a_n\) 的权值。

拿到这个题就想，你得查区间最大，还要找序号最小的那个，然后区间修改，怎么打暴力？直接上线段树啊。

然后打了一棵线段树，拿了 \(10\) 分。发现我的暴力比别人的暴力复杂度还多一个 \(n\)，少 \(40\) 分。因为是真的纯暴力没有发现本质。

可以想到，每一个 \(a_{i-1},a_{i},a_{i+1}\) 大小关系一定是不变的。为啥，因为能操作肯定保证 \(a_i\) 是三个里面最大的，不可能改着改着 \(a_{i-1}\) 还比 \(a_i\) 大了吧。那你肯定偷偷把 \(a_i\) 用 \(a_{i+1}\) 修改了，而 \(a_{i+1}\) 又没 \(a_i\) 大，所以不可能。那么最终要使所有数到 \(0\)，\(a_i\) 还没别人能改，只能是自己把自己一点点减成 \(0\) 的，所以肯定不用暴力减，每次找到一个 \(a_i\) 直接给总答案加上 \(a_i\) 然后给他们仨打标记就行了。这样复杂度应该可能是 \(O(q\log^2n)\) 的吧，好像差不多，但是常数是相当大啊。多了一个 \(\log\)。然后这个复杂度肯定是要比纯暴力优秀的，纯暴力是 \(O(nq)\)，但是没多放部分分的档。

最重要也是本题最惨的挂分点加粗了。

T3 帝国飘摇

倍增写。砍一个 \(n\) 变成 \(\log\)。
想到平衡树维护区间，复杂度 \(O(Tnm\log n)\)，有 \(80\) 分，但是这里的前驱后继是假的前驱后继，写的时候脑抽没想到，但是大样例四个过了三个，还以为是精度问题。。因为这里的前后是牵扯到相同元素的，所以你直接开个 vector 暴力跑都行，何必要用平衡树？……

T4 通天之塔

读错题可还行，它是每一个线路的平方和不是每一条边的平方和，所以你从起点开始往线路的每个点都连条边，长度可以前缀和求，跑最短路这样的话复杂度应该是 \(O(n^2)\) 的。