D. Dot Product Game
首先将对两个数组的操作转变为对一个数组的操作：可以发现，对 \(a\) 的某个子数组循环左移 \(r\) 位 与 对 \(b\) 的某个子数组循环右移 \(r\) 位是等价的，因此修改某个情形，只需要对其中一个序列的子数组循环左移或右移即可。
我们可以猜到，最终答案一定由序列的奇偶性决定（感觉这个猜还是比较容易想的）。证明也比较容易：一个经典结论是，交换任意排列的任意两个不同的数，逆序对数的奇偶性一定发生改变，而由于交换的两个位置 \(i, j\) 必须满足：\(a_{i} * b_{i} + a_{j} * b_{j} < a_{i} * b_{j} + a_{j} * b_{i}\)，化简得：\((a_{i}-a_{j})(b_{i}-b_{j}) < 0\)，可以等价于：\((i-j)((ba^{-1})_{i} - (ba^{-1})_{j}) < 0\)（\(ba^{-1}\) 是 \(a,b\) 作为置换复合后形成的环）。和 \(21\) 年 \(ccpc\) 桂林 \(D\) 一样，可以看出我们只能交换原序列中的逆序对，进一步可得知每次操作后，逆序对数必然减少，最终一定会减为 \(0\)。而由于每次操作必然会导致逆序对数奇偶性的改变，因此可推导：操作次数的奇偶性等于逆序对数的奇偶性。
因此问题缩小为 带修动态维护序列逆序对数的奇偶性。
如果修改和查询操作没有什么特殊性，那这个问题应该没有什么解法。但由于修改一定是将某个子数组循环左移或右移，并且只是查询逆序对数的奇偶性，我们可以发现，每循环左移（或右移）子数组 \(a[l,r]\) 一步，逆序对的奇偶性是否改变与 \(r-l\) 的奇偶性有关，因为一次循环左移操作等价于将第一个元素移动到其他元素之后，而它们的数量是 \(r-l\)。因此得出结论：对于子数组 \(a[l,r]\), 循环左移/右移 \(d\) 步，逆序对奇偶性是否改变取决于 \(d(r-l)\) 的奇偶性。 修改操作不需要真正模拟一遍，每次只需要 \(O(1)\) 查询即可，总复杂度 \(O(n)\)。
code
E. Light Up the Grid
这道题的状态转移有点把蒟蒻弄糊涂了，补了很长时间才补出来。
开始时想到了逆向着求单源最短路，但状态表示远远没有蒟蒻想得那么简单，因为并没有要求所有初始状态在同一操作过程中 同时到达 全1状态，而是只要经历过就可以。因此状态表示就需要特殊考虑。由于整张图只是一个 \(2 \times 2\) 大小，总共只有 \(16\) 种状态，因此可以考虑对图的所有情形进行状压。可以设状态 \(dp_{state}:\)，目前仍存在二进制状态 \(state\) 表示的所有图还没有到达过全 \(1\) 状态（每一个二进制位代表一个 \(2 \times 2\) 矩阵，填充恰好与当前二进制位数相同），要使得它们均到达全 \(1\)，最小总代价。
在状态转移时，只需要注意当某个状态转移到全 \(1\) 时，就可以消除掉这个状态，其他未到达的状态直接转移即可。最后问题就等价于给定所有初始图对应的二进制状态到达 \(0\) 的最短路，直接从 \(0\) 开始求一遍单源最短路即可。复杂度 \(O(2^{16})\)。
code
B. Magical Palette
一道比较考验数学的构造题，思路和官解一模一样。
code
M. Gitignore
大致思路是没问题的，但忘记了当环的总边权和为 \(0\) 时也不可行。本题的关键是在于判断某个强连通分量内是否存在一个非 \(0\) 环；而强连通分量的总边权和为 \(0\) 并不代表不存在非 \(0\) 环，这一点需要特别注意。
判断一个强连通分量内部是否存在一个非 \(0\) 环：由于强连通分量内部的点两两可达，因此可以考虑指定一个起点出发，遍历所有点和边，看是否可以找到非 \(0\) 环。在指定起点后，可以直接用 \(dfs\) 或 \(bfs\) 记录每个点到起始点的距离 \(dist\)；在遍历点 \(u\) 的出边时，若一个点 \(v\) 再次被搜索到，就代表找到了 \(v\) 所在的其中一个环，其中 \(dist[u] - dist[v]\) 代表环内除了边 \(w(u,v)\) 外的所有边权和；那么该环是非 \(0\) 环当前仅当 \(dist[u] - dist[v] + w = 0\)。按上述方法搜索，每个点和每条边均只会遍历一次，复杂度 \(O(n + m)\)。
每个询问 \(O(1)\) 查询即可，总复杂度 \(O(n + m + q)\)。
code