Sun
Contest
Luogu月赛两题 / ARC两题
比较简单不做题解说明
智者的考验
【JSOI2012】
有一个 \(H\times W\) 的矩阵，初始全 \(0\)，共有 \(H+W\) 个开关，编号分别为 \(1\sim (H+W)\)，每一个开关对应一行或一列，操作该开关会将其对应的行/列的数字取反（\(0\to 1, 1\to 0\)）。
给出一个 \(H\times W\) 的 \(01\) 矩阵 \(M\)，我们认为操作后的矩阵与 \(M\) 相等则操作者是不好的。
有三种操作，共计 \(n\) 个人，\(m\) 个操作：单人修改操作开关，区间修改操作开关，询问区间中不好的操作者数量。
\(H\leq 2,W\leq 3,n\leq 10^6,m\leq 1.2\times 10^5\)。
格子多一点就要 Hash 了，但是这里最多 \(6\) 个格子，直接用二进制转数值，值域 \([0,64)\)。
暴力查找所有可能的开关状态发现只有 \(16\) 种，重新标号一下，不然就是【天台MLE OIer一位】。
一次操作，等价于一次异或，可以处理出每一个开关相当于异或了什么，询问相当于查询前缀异或值。
区间 Cover 包含单点 Cover 情况，故不考虑单点修改。
发现如果要将 \([l,r]\) 修改成异或 \(x\)，记前 \(i\) 个数的异或值为 \(S_i\)，则相当于把 \([l,r]\) 中下标与 \(l\) 同奇偶性的 \(S\) 改成 \(S_{l-1}\oplus x\)，不同奇偶性的改成 \(S_{l-1}\)，并把 \([r+1,n]\) 做一个区间异或。
所以用线段树维护奇数下标Cover、偶数下标Cover、区间异或Tag、各异或值的出现次数即可通过。
码长比较恐怖。
最大连通子块和
给定一棵 \(n\) 个节点的树，\(m\) 个操作，要么单点修改点权，要么查询某棵子树的最大连通块权值和。
\(n,m\leq 2\times 10^5\)。
考虑朴素 DP，记 \(f_{i,0}\) 表示以 \(i\) 为根的子树中包含 \(i\) 的最大连通块权值和，而 \(f_{i,1}\) 表示 \(i\) 的所有子节点的 \(f_{i,0}\) 中的最大值，故：
\[f_{i,0} = \max(\underset{j\in to_i}{\sum} f_{j,0},0) \]\[f_{i,1} = \underset{j\in to_i}{\max} \max(f_{j,0}, f_{j,1}) \]套路性地拿出所有轻儿子，令：
\[g_{i,0} = \underset{j\in lt_i}{\sum} f_{j,0} \]\[g_{i,1} = \underset{j\in lt_i}{\max} \max(f_{j,0}, f_{j,1}) \]则：
\[f_{i,0} = \max(g_{i,0} + f_{h_i,0} + a_i,0) \]\[f_{i,1} = \max(g_{i,1}, f_{h_i,0}, f_{h_i,1} ) \]那么有：
\[\begin{bmatrix} g_{i,0} + a_i & -\infty & 0\\ 0 & 0 & g_{i,1} \\ -\infty & -\infty & 0 \\ \end{bmatrix} * \begin{bmatrix} f_{h_i,0}\\ f_{h_i,1}\\ 0\\ \end{bmatrix} = \begin{bmatrix} f_{i,0}\\ f_{i,1}\\ 0\\ \end{bmatrix} \]然后，321上树剖，但是发现 \(f_{i,1}\) 的部分是取较大值，所以需要一个可以支持快速删除、查询最大值的数据结构（堆、多重集、平衡树……都可以）。
本题记得乘上初始转移矩阵，行向量/列向量均可，上述所写应乘列向量。
Mon
算法复杂度
【CTSC1998】
给定一个程序，包含循环（包括 break 与 continue 语句）以及做单位操作，以多项式形式输出其时间复杂度，计算常系数。
保证：程序不长，不超过 \(20\) 层循环嵌套，系数不超过 \(10^9\)。
本题是继【THUPC2019】鸭棋（码长：5.31KB）与【THUPC2021】群星连结（码长：10.39KB）后的又一道紫色大模拟，本题码长为 2.94KB。
考虑将循环抽象出来，我们可以看作是一棵树形结构，如果一个 loop 直接嵌套另一个 loop，则两个 loop 之间有边。
不妨称每一个点的复杂度是直接属于该 loop 的单位操作的复杂度，每一条边乘上下一个 loop 的循环次数。
然后就非常简单了，dfs 这棵树即可。
典型模拟部分：字符串转数字，多项式输出。
标签：2024.3,17,开关,max,leq,异或,3.22,bmatrix,loop From： https://www.cnblogs.com/ydzr00000/p/18079823