前言
笔者将使用该博客写下他所有网赛的总结和自己的思考。
如有错误，欢迎指出。
对于没有价值的题，我会自动忽略掉。
\[\large \text{Round 1 : Educational Codeforces Round 120 (VP)} \]
一言:
孤独的人不会伤害别人，只会不断地伤害自己罢了。
——我的青春恋爱物语果然有问题
\(\text{C: Set or Decrease }\)
后四题唯一场切题，（别问我为什么只有这一道）。
读完题之后，理一下思路，可以很容易的想到一种贪心思想，就是我们找到这个序列中最小的数，对他执行 \(x\) 次操作 \(1\)，然后找到 \(m\) 个最大的数，将他们与最小的数执行一次操作 \(2\)，这样必然是最优的。（$ 0 \le x, 0 \le m \le n - 1$）。
首先对于符合题意的序列，输出 \(0\) 直接跳过。
接着我们求出要使得总和小于给定总和总共需要减去的数，即 \(sum - k\)，设为 \(need\) 。然后定义 \(b\) 数组表示 \(b_i=a_i-a_1\)，以及 \(sum_i\) 表示 \(b\) 数组的后缀和。
所以我们显然有 \(b_{n-m+1}+x \times (m+1) \ge need\)。
由于 \(x\) 可能很大，所以我们可以直接考虑枚举 \(m\)，求得最小的 \(x\)，然后将 \(m+x\) 取最小值即可。
\(\text{D: Shuffle}\)
对于这道题，我们可以非常容易的通过 \(n^2\) 的复杂度找到可以修改的所有区间，并对其进行修改。
但是很显然，这样是有重复的，这也是本道题的难点。
但是实际上，我们并不关心具体是那个区间修改了，我们可以直接枚举发生变化过的所有区间 \([l,r]\)，如果两个端点保证改变了，那他就必然可以保证会与其他区间的变化不一样，所以接下来的目标就是要求对于区间 \([l,r]\)，保证端点修改的方案数。（可以发现，只有 \([l,r]\) 之间 \(1\) 的个数小于等于 \(k\)，且全局 \(1\) 的个数大于等于 \(k\)，它才会被修改。）
对于 \(a_l,a_r\)，必须填上与其原来不同的 \(0,1\)，（如果填不上就特判无解），定义还可以填的 \(0,1\) 的个数分别为 \(num0,num1\)，则方案就是 \(C(num0+num1,num0)\)。
最后累加起来就可以了。
\(\text{E: Math Test}\)
看见这个绝对值就很不爽，我们可以考虑对于每个人定义一个数组 \(c_i \in \{ -1,1 \}\)，并暴力搜索得到每个人的 \(c_i\) 是 \(-1\) 还是 \(1\)。
那么，我们就可以把答案重新定义为 \(\sum ^n _{i=1} c_i \times (r_i - x_i)\)，假设第 \(i\) 道题目的得分为 \(e_i\)，\(a_{i,j}\) 表示第 \(i\) 个人的是否答对了第 \(j\) 道题。
接着我们对这个式子进行一系列的恒等变形：
\[\begin{aligned} ans&=\sum ^n _{i=1} c_i \times (r_i - x_i) \\ &=\sum ^n _{i=1} c_i \times r_i - \sum ^n _{i=1} c_i \times x_i\\ &=\sum ^n _{i=1} c_i \times r_i - \sum ^n _{i=1} c_i \times \sum _{j=1} ^ m a_{i,j} \times e_j\\ &=\sum ^n _{i=1} c_i \times r_i - \sum ^m _{i=1} \left( \sum _{j=1} ^ n a_{j,i} \times c_i\right) \times e_j \end{aligned} \]可以发现，减号之前部分是定值，右边括号内也是定值，要使右边减的越小，则根据排序不等式，则括号内值越小，\(e\) 的值就越大。
虽然但是，这样并没有结束，你会发现有一些不合法的方案，就是你求出来 \(e\) 之后，还原回去，会发现他绝对值取正负并不与 \(c\) 数组匹配，也就是有可能存在一个人他的 \(c_i \times (r_i-x_i)\) 可能是个负数。但显然，如果他是个负数，那么将 \(c\) 数组取反就必然会得到正确的答案，也就是说，必然会有其他情况比该情况更优，所以这个不合法情况永远成不了最优解。
所以最终复杂度 \(2^nmn+2^nm\log m\) 在 CF 神机下乱过。
\(\text{F: Quadratic Set}\)
题目给到了两个关键信息，阶乘的连乘，完全平方数。那我们就希望能不能将阶乘的连乘简化为一个完全平方数再乘一些数。
实际上还真就可以简化。有以下恒等式：
\(\prod _{i=1} ^ {2k} i! = \left (\prod_{i=1}^k (2k-1)! \right)^2 \times 2^k \times k!\)
因为 \(\left(\prod_{i=1}^k (2k-1)! \right)^2= \prod_{i=1}^k (2k-1)! \times (2k)! \times \dfrac{1}{2k}\) ，还是比较好推的，就是确实不太好想到。
然后我们在通过一系列的样例观察，发现好像至少可以选出 \(n-3\) 个数，那我们根据上面的恒等式来证明一下。
首先对于 \(4 \mid n\)，那我们令 \(k=\dfrac{n}{2}\)，则只需要删去 \(\dfrac{n}{2}\) 即可符合条件。
接着对于剩余的 \(2\mid n\)，我们仍然令 \(k=\dfrac{n}{2}\)，则只需要删去 \(2,\dfrac{n}{2}\)，即可符合条件。
对于剩余情况，显然 \(n\) 是奇数，我们令 \(k = \dfrac{n-1}{2}\)，则只需要删去 \(2,\dfrac{n-1}{2},n\) 即可符合条件。
所以得证，但是并不一定是最优解。
我们定义 \(A=\prod _{i=1} ^ {n} i!\)
如果 \(A\) 是平方数，则输出所有的 \(n\) 个数。
接着枚举 \(1 \le i \le n\)，如果 \(\dfrac{A}{i!}\) 是平方数，则输出 \(n-1\) 个除了 \(i\) 的数。
接着枚举 \(1 \le i \le n\)，如果能够找到 \(j\) 满足 \(\dfrac{A}{i! \times j!}\) 平方数，则输出 \(n-2\) 个除了 \(i,j\) 的数。
否则输出 \(n-3\) 个不是 \(\dfrac{n-1}{2},2,n\) 的数。
但是你总不可以暴力求阶乘吧？ 实际上，每个阶乘是不是平方数只与其的质因数分解后，每个质因数的个数是不是偶数有关，想到偶数，你是否有想到异或？
我们可以考虑给每个质因子赋一个哈希值，定义一个阶乘的 \(a_i\) 表示 \(i\) 的阶乘中质因数分解后所有质数哈希值的异或和。（如果每个质数有多个，那就都异或起来）显然可以递推处理。
显然，如果 \(B=a_1 \oplus a_2 ... \oplus a_n=0\)，则就满足最初的 \(A\) 是平方数。如果 \(B \oplus a_i = 0\)，也就找到了\(\dfrac{A}{i!}\) 是平方数。对于最后一种情况，可以用 \(map\) 处理，即每次将 \(a_i \oplus B\)，放入 \(map\) 中，每次查 \(map\) 中是否存在 \(a_i\)，一旦存在就满足\(\dfrac{A}{i! \times j!}\) 平方数。
时间复杂度 \(n\log n\)。
\(\text{What I learned:}\)
-
如果你发现当你求方案加和时存在重复方案，则可以考虑将每次将要求解的子问题多限定一些条件达到去重目的。
-
你要求最值，但是通过你的办法求出时可能存在不满足题目条件的，那你可以想想这些解有没有可能是最优的。
-
多观察样例找规律。
-
\(\prod _{i=1} ^ {2k} i! = \left (\prod_{i=1}^k (2k-1)! \right)^2 \times 2^k \times k!\) 。
-
排序不等式。
-
如果要看一个数出现了奇数次还是偶数次，请别忘记异或。
-
如果判断一个数出现次数的奇偶性仅仅通过异或的话，可能会出现另外的数把当前数给异或掉了，所以此时可以考虑哈希来尽量避免这种重复。
\[\large \text{Round 2 : AtCoder Beginner Contest 313 (VP)} \]
一言：
当我拔出第二把剑时，就是为了我所爱之人
——刀剑神域
这场比赛真的是大败而归，只 A 了 \(A,B,C,E\)。。。
虽然但是，\(F,G\) 确实不可做，但是 \(D\) 题还是有点可惜了。
\(\text{D: Odd or Even}\)
感觉考场上最有价值的就是这道题了。
首先对于 \(k=1\)，我们直接特判，每次询问 \(1 \le i \le n\) 即可。
注意，以下定义均基于前 \(k+1\) 个数。
我们定义 \(a_i\) 表示第 \(i\) 个位置上最终的答案，\(b_i\) 表示除开第 \(i\) 个位置的异或和，即 \(b_i = a_1 \oplus a_2 \oplus a_3.... \oplus a_{i-1} \oplus a_{i+1} ... \oplus a_{k+1}\)。
接着我们可以考虑一种特殊情况，即 \(n=k+1\)。
显然，我们可以每次查询 \(b_i\)，因为 \(k\) 是奇数，所以 \(A=a_1 \oplus a_2 \oplus a_3.... \oplus a_{k+1}=b_1 \oplus b_2 \oplus ..... \oplus b_{k+1}\)。接着根据异或的性质，有 \(a_i=A \oplus b_i\)，也就求出了前 \(k+1\) 个数。
那么对于一般情况，我们就需要求出剩余的数，可以每次在查询时从输出 \([3,k+2]\) 开始，每次往后面挪一位，然后就可以根据以前的答案，异或后得到答案。
\(\text{What I learned:}\)
-
当题目与奇偶性相关时，一定要想到异或哦。
-
求一个序列时，可以先求出前 \(k\) 个，然后再慢慢递推下去。
\[\large \text{Round 3 : Codeforces Round 893 (Div. 2)(VP)} \]
一言:
从你站在桥上看我的那一刻起你就是我的世界
——火影忍者
不是很满意，还是没有突破 \(\text{D}\) 题，确实是没有想到这题竟然如此毒瘤。。
\(\text{D: Trees and Segments}\)
首先不难想到一种思路，就是枚举 \(l0\)，然后预处理出在得到 \(l0\) 时，能够得到最大的 \(l1\) 是多少，假设这个值为 \(d_{l0}\)。
显而易见的，\(0\) 的连续段不是在 \(1\) 连续段的右边就是在他的左边，所以考虑维护四个数组来辅助得到 \(d_{l0}\)：
定义 \(l1_{i,j}\) 表示以 \(i\) 结尾，得到长度为 \(j\) 的最大 \(0\) 串需要的最少操作数。
\(l2_{i,j}\) 表示以 \(i\) 开头，得到长度为 \(j\) 的最大 \(0\) 串需要的最少操作数。
显然，对于 \(1\) 串，为了方便求出 \(d\) 数组，我们就需要换一种定义方式：
定义 \(r1_{i,j}\) 表示使用 \(j\) 次操作，得到的以 \(i\) 结尾的最大连续 \(1\) 串的长度。
\(r2_{i,j}\) 表示使用 \(j\) 次操作，得到的以 \(i\) 开头的最大连续 \(1\) 串的长度。
显然对于上述数组，我们可以通过枚举任意一个子区间 \([l,r]\)，获取其变为 \(0\) 串，或者 \(1\) 串的代价，然后带回上述的几个数组中来求解。
所以有 \(d_j = \max{\ r1_{i - 1,k-l2_{i,j}},r2_{i+1,k-l1_{i,j}}}\)。
但是还有一个问题，这样求出的 \(d_i\) 两个连续 \(01\) 串根据定义是必须靠在一起的，实际上却可以是不连续的，所有我们要对 \(r1\) 求一个前缀 \(\max\)，\(r2\) 求一个后缀 \(max\) 再套入刚刚 \(d_j\) 的公式。
另外，也要处理好一些边界值的细节。以及不能 \(\text{memset}\) 真的好烦啊！
\(\text{F: Rollbacks (Hard Version)}\)
看完题解之后，感觉这个题是真的妙啊。
由于这道题是 \(\text{E}\) 的加强版，所以就直接忽略这道 \(\text{E}\) 了。
首先，为了让题目更加简单，我们可以直接不考虑这个删除操作。
那么显然由于是要求不同的数字，所以实际上只有每个数出现的第一个位置是有意义的，那么我们可以考虑维护一个 \(\text{set}\) 来储存每个数出现的位置。然后还有单点修改，所以可以维护一个树状数组，来把有意义的点储存进去。
具体来说，对于插入操作，将这个数放入 \(\text{set}\)，然后并根据 \(\text{set}\) 来单点修改树状数组。对于查询操作，假设当前有 \(\text{len}\) 个数，那么直接在树状数组中查询 \([l,\text{len}]\) 的有效值总和。
重点是这个删除操作，实际上我们可以直接令 \(len = len - k\)，仔细想可以发现，如果我们想要撤销到这个删除，那么必然在撤销这个删除的上一个状态就是这个 \(len = len - k\) 这个状态，所以到时候直接在撤销的时候把 \(len\) 加回来即可。
至于插入操作的撤销，这个还是很简单的，就不细说了。
实际上在代码实现的时候，是还可以更简单的。
\(\text{What I learned:}\)
-
当求两个独立的区间的贡献时，可以考虑枚举两个区间的相对方位，然后通过一些预处理进行维护。
-
如果既有删除操作，有些时侯又要撤销这个删除操作，那么可以考虑在删除的时候只将数组的最后一位向前挪，并不改变实际的值。
-
维护一个序列有多少个不同的数时，可以只将每个数第一次出现的位置设为贡献 \(1\)，其余位置都不存在贡献。
\[\large \text{Round 4 : cqbz Weekly Round 10} \]
一言:
无论你在哪里，就算我看不见你，我也会一直注视着你。
——妖精的尾巴
\(\text{D: cloud}\)
如果把买入和卖出分开处理显然会有一些繁琐，所以我们考虑把他们合在一起，那么买入的利润就是价格的相反数，而卖出就会失去核心。
我们可以很显然的想到将核心当作容量，利润当作价值，定义 \(dp_i\) 表示还剩下核心数量为 \(i\) 的最大利润，那么显然就可以想到一个 \(01\) 背包 \(\text{DP}\)。
但是只是单纯这样的话，我们会发现，对于一些卖出，他可能时钟频率不合法。
所以我们考虑将时钟频率从小到大排序，然后根据最开始的分析来一遍背包 \(DP\)，最后枚举还剩下多少个核心，取一个最大值即可。（特别的，对于时钟频率相同的，将买入的放前面，卖出的放后面。）
\(\text{E: matrix}\)
解法一：
考虑 \(\text{dp}\)。
我们定义 \(dp_{i,j}\) 表示前 \(i\) 行，在保证每一行的最小值为 \(1\) 的前提下，有 \(j\) 列的最小值是 \(1\)。另外，为了方便叙述，我们定义 \(m\) 为原题中的 \(k\)。
对于初始值，显然有 \(dp_{0,0} = 1\)。
接着我们考虑转移。首先顺着枚举状态中的 \(i,j\) ，然后枚举 \(k\) 表示这一行会新产生 \(k\) 列的最小值是 \(1\)。
-
对于 \(k = 0\)，由于第 \(i\) 行必须有 \(1\)，并且不能再新产生一列的最小值是 \(1\)，所以只能在这最小值已经为 \(1\) 的 \(j\) 列中，使得其中必须存在一个 \(1\)。计算的话，就是用乱选减去一个 \(1\) 都不选，及 \(dp_{i,j}=(m^j - (m-1)^j) \times dp_{i-1,j}\)。
-
对于剩余情况，显然这一行已经有 \(1\) 了，所以我们只需要考虑列的情况。显然，我们需要从 \(n - （j - k）\) （就是在上一行还没有产生这 \(k\) 列的状态） 选出 \(k\) 列来填补 \(1\)，对于上一状态就已经最小值为 \(1\) 的列，显然是可以乱选的，也就是 \(m^{(j-k)}\)，那么对于剩余的 \(n-j\) 列，只要不取 \(1\) 就可以了，也就是 \((m-1)^{n-j}\) 。总的来说，就是 \(dp_{i,j} = \sum _{k=1} ^ j dp_{i-1,j-k} \times C(n - j + k,k) \times m^{(j-k)} \times (m-1)^{n-j}\)。
将两个部分的解加起来即可。
最后，直接输出 \(dp_{n,n}\) 即可。
总复杂度为 \(O(n^3 \log n)\)。
解法二：
考虑容斥，枚举有 \(i\) 行，\(j\) 列的最小值不是 \(1\)。
乱推一波式子，显然有 \(\sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} \times C(n,i) \times C(n,j) \times (k-1)^{(i+j)\times n-i\times j} \times (k-1)^{(n-i)\times (n-j)}\)。
\(\text{F: virus}\)
这题应该是最有价值的了。
题意就是求逆序对个数的期望，不难发现，对于树上的一对点对 \((i,j),i>j\)，那么显然最终的答案就是求 \(i\) 比 \(j\) 先到的概率之和。
首先可以枚举根是谁
仔细思考可以发现，对于是 \(i\) 先还是 \(j\) 先到，他的概率只会与走到 \(\text{lca(i,j)}\) 之后的操作相关，也就是说，就是要求 \(i\) 有 \(x\) 步到 \(lca(i,j)\)，\(j\) 有 \(y\) 步到 \(lca(i,j)\)，要求 \(i\) 先到的概率。（显然，这个概率实际上只与 \(x,y\) 有关）
所以接下来考虑一个简单的递推。定义 \(f_{i,j}\) 表示 \(x\) 有 \(i\) 步要走，\(y\) 有 \(j\) 步要走，\(x\) 比 \(y\) 先到的概率。（这个值已经说明过与 \(x,y\) 无关）
对于初始值，显然有 \(dp_{0,i}=1\)。
如果你走的下一步并不能靠近 \(x\) 或者 \(y\)，那么这一步显然对答案没有任何影响，我们就只需要考虑是靠近了 \(x\) 还是靠近了 \(y\)，所以有 \(f_{i,j}=\dfrac{f_{i-1,j}+f_{i,j-1}}{2}\)。
最后，对于每一个根，枚举 \((i,j)\)，其产生的贡献就是 \(f_{{dep_i-dep_{lca(i,j)},{dep_j-dep_{lca(i,j)}}}}\) 之和。
时间复杂度 \(n^3\log n\)（因为 \(lca\) 需要复杂度，但是也可以优化）。
\(\text{What I learned:}\)
-
对于一堆 \(i\) 对应一个 \(j\)，如果有一些限制条件，使得其他的 \(i\) 不合法，且为了方便求解，我们需要把 \(i,j\) 合并在一起算，那么我们可以考虑排一个合适的顺序，使得 \(j\) 前面的 \(i\) 对他全部合法，这样更能方便求解。
-
对于组合数学，一个很好的方式就是背包 \(DP\)。
-
对于树上 \(i,j\) 两个点的一些对比，是否只需要从他的 \(lca(i,j)\) 开始呢。
-
考场上第五题文件名为 \(\text{martix}\) 但我拼的 \(\text{matrix}\) ，所以100分没了，出题人你真的英语就这么好吗。。下次复制吧。
\[\large \text{Round 5 : AtCoder Beginner Contest 298 (VP)} \]
一言:
成一事者，是失之不渝的愚者；毁一事者，是停滞不前的贤者。
——不正经的魔法讲师
\(\text{Ex: Sum of Min of Length}\)
这次比赛总体难度不是很大，可能也是我第一次自己独立做出 \(\text{Ex}\)。（虽然不是场切，也调了很久，没看题解，所以纪念一下。）
这题维护的东西比较多，下面我们一个一个列出来。（默认以 \(1\) 为根。）
-
\(dep_i\) 表示 \(i\) 节点的深度。
-
\(siz_i\) 表示 \(i\) 子树的大小。
-
\(dis_i\) 表示 \(i\) 到 \(i\) 子树中每个点的距离之和。
-
\(eds_i\) 表示 \(i\) 到每个点的距离之和。
-
\(f_{i,j}\) 表示 \(i\) 的 \(2^j\) 个祖先是谁。
显然，\(dis_i\) 正常当作树形 \(\text{DP}\) 求，\(eds_i\) 就换根求，\(f_{i,j}\) 就是一个倍增，用来求 \(\text{lca}\) 。
接着，对于每一组询问 \((x,y)\)，设 \(z=lca(x,y)\)。假设 \(x\) 的深度比 \(y\) 的深度大，否则交换。定义 \(dist\) 为 \(x\) 和 \(y\) 到 \(lca\) 的总和。
首先对于不属于 \(z\) 子树的那一些点，答案显然就是 \(z\) 到哪些点的距离之和 \(eds_z - dis_z\) 在加上 \(z\) 到 \(y\) 的距离（肯定比到 \(x\) 的距离小） 乘上 \(n-size_z\)。（第二部分是因为那些距离还要走到 \(z\)）
显然，对于 \(x\) 的 \(\dfrac{dist}{2}\) 级祖先的子树，显然这些点的距离都是到 \(x\) 最小（设这个祖先为 \(k\)）。所以这部分答案就是 \(x\) 到所有点的距离，减去 \(x\) 到这个祖先子树以外的距离，也就是 \(eds_x - (eds_z-dis_z)-(n-siz_k) \times \dfrac{dist}{2}\)。
最后对于 \(y\) 的那一部分，也就是 \(y\) 到在 \(z\) 子树中不包含 \(k\) 的子树的点的距离之和。也就是将 \(y\) 到所有点的距离减去 \(y\) 到 \(z\) 子树以外点的距离，再减去 \(k\) 子树中点到 \(y\) 的距离，就是 \(eds_y-dis_k-siz_k\times (dist-\dfrac{dist}{2}) - (eds_z-dis_z)-(n-size_z)\times (dep_y-dep_z)\)。
最后将三部分加起来就是答案。
下面是一些需要特殊处理的情况，每种都需要特殊处理。（至于怎么处理，就举一反三吧。）
-
\(x=y\)
-
\(k=z\)
-
\(z=y\)
\(\text{What I learned:}\)
- 这场比赛在思想上并没有学到什么特殊的，但是独立做出 \(\text{Ex}\) 还是让我很开心的，增强了一点自信心吧，总之还是要大胆的去实践自己推出来的东西。
\[\large \text{Round 6 : AtCoder Beginner Contest 315} \]
一言:
愿悲 、爱恋、你和宇宙以及那颗星辰，能够永远拥抱我们。
——THE BEYOND-機動戦士ガンダム40周年纪念曲
这场打的一般，主要还是一开始网卡爆了把心态弄得很不好，一定程度上影响了发挥。
\(\text{G: Ai + Bj + Ck = X (1 <= i, j, k <= N)}\)
这题其实还是很好想的，主要问题出现在实现上面。
我们可以考虑枚举 \(i\)，那么接下来就会得到一个式子 \(\text{Bj + Ck = x - Ai}\)。显然，我们可以通过扩展欧几里德得到一组通解 \(y,z\)。
那么对于每一个整数 \(p\)，就会有 \(B\times y+C\times z=B\times (y-p \times \dfrac{C}{\gcd(B,C)})+c\times (z+p\times \dfrac{B}{\gcd(B,C)})=x-Ai\)
实际上就是要你求出有多少个 \(p\) 满足 \(1 \le y-p \times \dfrac{C}{\gcd(B,C)} ,z+p\times \dfrac{B}{\gcd(B,C)}\le n\)。其实可以把它转化为当 \(p<0\) 以及 \(p \ge0\) 两种情况分别讨论，这样做会方便不少。
\(\text{What I learned:}\)
-
以后 AT 网卡的时候，尝试重启电脑吧，亲测有效。
-
对于给定三个数 \(i,j,k\) 合在一起的限制，要求方案，可以考虑枚举 \(i\)，算出 \(j,k\) 的一些限制，然后将可能的情况加在一起。
-
\(\text{From Problem E}\)，我们发现，如果我们可以采取一些代价减少操作数，那么当你枚举代价时，请明白这个代价最多只需要枚举到总操作数之和，这样可以减少复杂度。
\[\large \text{Round 7 : Codeforces Round 892 (Div. 2) (VP)} \]
一言:
所谓人，无论是谁到了最后，都会形单影只。
——悠久之翼2
最令人无语的是最后三分钟交代码的时候把 \(\text{D}\) 题交到了 \(\text{E}\) 题，结果能过的代码直接没有过。。
\(\text{D: Andrey and Escape from Capygrad}\)
这题乍一看每一个东西有四个要输入的，好像还挺复杂的，但仔细想想你就会发现，实际上只有 \(l_i,b_i\) 是有用的。（后面会讲为什么）
仔细想想，我们可以把 \([l_i,b_i]\) 当作一个区间，然后将所有有交集的区间合并在一起，最后输出的时候直接看 \(x\) 在那个区间里面，然后直接输出这个区间的右端点。
接下来我们仔细想想为什么。
首先可以发现，如果有一次传送是在向前面传送，那一定不是最优的（至少除去这些传送必然还会留下最优解）。可能你到了前面可以到达更大的 \(b_i\)，但是这样的 \([l_i,r_i]\) 肯定是包含当前操作的这个点的，所以我们可以直接在这一次传送时向后面传送，不需要向前。
然后对于 \(b_i\) 右边那一部分，可以发现，它即使有可能处于 \([l_i,r_i]\) 这个区间里面，但他此时如果跳到 \(b_i\) 实际上是在往后面退的，可以保证这个一定不是最优解，对于 \([l_i,a_i]\) 这一部分，可以发现，他最多也只能到 \(b_i\)，所以刚刚那个贪心策略就是对的了。
\(\text{E: Maximum Monogonosity}\)
首先我们可以想到一个 \(\text{DP}\)，即 \(dp_{i,j}\) 表示前 \(i\) 个数，已经选了长度和为 \(j\) 的不相交的区间可以得到的价值总和的最大值。（假设 \(f_{l,r}\) 表示一个区间 \([l,r]\) 的价值，感觉这个状态也不是很好想啊）
可以考虑枚举一个 \(k\) 表示选了区间 \([i-k+1,i]\)（当然可以不选），那么显然有 \(\text{DP}\) 转移：\(dp_{i,j}=\max \{ dp_{i-k-1,j-k} + f_{i-k+1,i}\}\)。
但是这样的时间复杂度是 \(O(n \times k ^2)\)，显然不符合我们的要求。
可以发现，最难处理的是 \(f_{l,r}\) 的那两个绝对值。由于绝对值满足性质 \(|x| \in \{ x,-x\},|x| \ge \max\{x,-x\}\)，所以我们可以把两个绝对值每个差一个正负号，合在一起就是 \(4\) 个，且可以发现只有合法的那个才有可能成为最大值。那么我们就可以重新写一次 \(\text{DP}\)：
\[\begin{aligned} dp_{i,j}=\max \{ dp_{i-k,j-k} + a_i-b_{i-k+1}+b_i-a_{i-k+1}\} \\ dp_{i,j}=\max \{ dp_{i-k,j-k} - a_i+b_{i-k+1}+b_i-a_{i-k+1}\} \\ dp_{i,j}=\max \{ dp_{i-k,j-k} + a_i-b_{i-k+1}-b_i+a_{i-k+1}\}\\ dp_{i,j}=\max \{ dp_{i-k,j-k} - a_i+b_{i-k+1}-b_i+a_{i-k+1}\}\\ \end{aligned} \]由于 \(a_i,b_i\) 是定值，整理一下就可以得到：
\[\begin{aligned} dp_{i,j}=\max \{ dp_{i-k,j-k} -b_{i-k+1}-a_{i-k+1}\}+a_i+b_i \\ dp_{i,j}=\max \{ dp_{i-k,j-k} +b_{i-k+1}-a_{i-k+1}\}-a_i+b_i \\ dp_{i,j}=\max \{ dp_{i-k,j-k} -b_{i-k+1}+a_{i-k+1}\}+a_i-b_i\\ dp_{i,j}=\max \{ dp_{i-k,j-k} +b_{i-k+1}+a_{i-k+1}\}-a_i-b_i\\ \end{aligned} \]可以发现，对于中间那一坨最大值，他好像可以在求出 \(dp_{i-k,j-k}\) 的时候进行更新，可以发现 \(dp_{i-k,j-k},dp_{i,j}\) 的一个共同点就是他们的第一维坐标减去第二维坐标的差是一定的，所以我们可以定义一个 \(f_{x,0-3}\) 表示当前枚举到的所有的 \(i-j=x\) 的 \(\max\) 里面那一坨的最大值。所以每次求 \(dp_{i,j}\) 时，就是 \(f_{i-j,0-3}\) 在加上 \(a_i,b_i\) 对应的贡献再求个最大值，且每次求完 \(dp_{i,j}\) 之后，要记得对对应的 \(f_{i-j,0-3}\) 进行更新。
\(\text{What I learned:}\)
-
当你发现每个东西里面的一些相关条件有些是无关紧要的时候，可以考虑把他删去来降低题目的复杂程度。
-
当出现绝对值的运算并且要求最值时，一定要想一想如果不考虑绝对值是否有可能让一些错误的值成为最值。如果否，那么你就可以直接把绝对值这东西删去了，这样更能方便推式子。
-
当你优化 \(\text{DP}\) 的时间复杂度时，一定要思考一下当前状态与他之前的所有状态是否都有共同点（比如 \(dp_{i,j}\) 与 \(dp_{i-k,j-k}\) 的共同点就是两维之差都是 \(i-j\)），且把转移式中只跟当前这个数相关的部分去掉，如果是，那么可以通过这个共同点维护一个东西（比如维护一个 \(f_x\) 维护此前所有 \(i-j=x\) 的所有状态最值），使得你能够快速找到是从哪个状态转移来是最优的，并且在求出一个 \(\text{DP}\) 式后，更新这个共同点维护的东西，从而优化复杂度。
\[\large \text{Round 8 : AtCoder Beginner Contest 310 (VP)} \]
一言:
虚伪的眼泪，会伤害别人，虚伪的笑容，会伤害自己。
——反叛的鲁鲁修
\(\text{F}\) 竟然没有第一时间想到状压，还是太蒟了。。
\(\text{F: Make 10 Again}\)
这题看到一个子集，再加上子集和的范围只需要考虑小于 \(10\) 的情况，其实就应该直接想到状压的，不知道当时我是范什么抽了，竟然没想到。。。
我们定义 \(dp_{i,j}\) 表示前 \(i\) 个数中，每个骰子选出的数所能构造出的小于等于 \(10\) 的子集和只能是 \(j\) 状态上二进制为 \(1\) 的数。
显然，我们可以考虑枚举一个 \(k,l\) 分别表示第 \(i\) 个骰子会投出那个数。和从 \(i-1\) 的那个状态转移过来。那么下面就是考你位运算的时候。
首先已经至少出现 \(k\) 这个状态了，接着，由于投出了 \(l\)，所以当前状态就变成了 \(2^l | k\)。但是由于是子集和，所以以前的子集和可以全部加上 \(l\) 构成新的子集和，也就是 \(k<<l\)，但是由于这样可能会超出 \(10\)，所以有 \((k<<l) \& (2^{10}-1)\)，所以用人话说就是 \(dp[i][2^l|k|((k<<l) \& (2^{10}-1))]+=\dfrac{dp[i-1][k]}{a[i]}\)。
另外，对于 \(a_i \ge 10\) 的情况可能会导致左移的太多炸精度，所以直接特殊处理就可以了。
\(\text{G: Takahashi And Pass-The-Ball Game}\)
题目里面那个期望其实没什么大用的，就是用来唬人的。
仔细读题之后，就会发现题意实际上就是对于一个点 \(i\) 他的权值是 \(a_i\)，他的父亲是 \(b_i\)，他会对所有他 \(k\) 步以内的祖先的答案全部加上 \(a_i\)，最后输出每个点的答案除以 \(k\) 对一个质数取模。
由于是向上跳 \(k\) 步，我们考虑是否可以倍增。（鬼知道是怎么想到这个倍增的。）我们可以一步一步来理解这个过程：
如果是向上跳 \(2^j\) 步，且当前每个数组中已经存好了 \(2^{j-1}\) 步的情况。（具体储存什么后面会讲）注意，由于是倍增处理，我们要把 \(a\) 和 \(b\) 数组也处理到倍增以后的情况，也就是 \(a_i\) 就表示当前跳完 \(2^{j-1}\) 步后，他的 \(2^j\) 步会跳到哪里，所以跳完 \(2^{j-1}\)，都有 \(a_i=a_{a_i}\)。（仔细思考可以发现，这个和树上倍增的思想类似。）对于 \(b_i\)，我们储存已经跳完 \(2^{j-1}\) 步每个点的答案。仔细想可以发现，我们对于 \(b_i\) 只需要统计从 \((2^{j-1}+1)-2^j\) 这些步数跳来的，在加上 \(b_i\)，就可以得到答案。仔细思考一下，这不就是 \(b_{a_i}=b_{a_i}+b_i\)。
最后统计答案的时候，我们将所有 \(k\) 的二进制位是 \(1\) 的 \(b\) 加到答案上就可以了。（并记得在此时重新初始一下 \(b\) 数组）
还是要配合代码才能方便理解啊。。。。
\(\text{What I learned:}\)
-
当答案是关于选出的数的一些子集的限制时，且这些限制并不是很多，可以通过二进制表示出来。那么请考虑状态压缩。
-
当你在题目中看到期望的时候，不要紧张，大概率都需要将问题的模型转化一下。
-
如果要求 \(n\) 个东西经过 \(k\) 步的贡献之和，可以考虑把 \(k\) 拆成 \(2^{i_1}+2{i_2}+...2^{i_l}\) 这样一个一个的二进制位。然后从 \(2^0\) 开始，每次让次数加一次，也就是通过一些手段求出经过 \(2^0,2^1,2^n...2^{il}\) 这些步数的贡献，然后每次将 \(2^{i_1},2^{i_2}...2^{i_l}\) 这些步数的贡献加在一起，就可以得到 \(k\) 步的贡献之和。相当于将时间复杂度从 \(O(nk)\) 优化到 \(O(n \log k)\)。
-
不只是树可以倍增，仔细想想，基环树或者只有一个父亲的图是不是都可以倍增？
\[\large \text{Round 9 : Cqbz Weekly Round 12} \]
一言:
雨滴降落的速度是每秒十米，我该用怎么样的速度，才能将你挽留？
——言叶之庭
感觉这场比赛挺有意思的，除了T3的大模拟被某巨佬拉开了差距，其他的题目感觉完成情况都比较正常吧。
\(\text{F : middle}\)
这是一道可持久化的好题。
首先由于要求这个范围内最大的中位数，再看看这个询问数才 \(5\times 10^4\)，不想到二分这个中位数。
那么接下来考虑一个 \(\text{check}_x\)。
为了方便描述，我们假设序列中所有小于等于 \(x\) 的值为 \(-1\), 大于 \(x\) 为 \(1\)。实际上，要让一个中位数合法，就是看他在这个区间内的和是不是 \(0\)。
由于你无论如何怎么选中位数都需要考虑 \([b,c]\)，所以先直接查询 \([b,c]\) 里面的数的和是多少，假设为 \(x_1\)。
然后我们在 \([a,b-1]\) 中找到一个最大的 \(x\)，满足 \([x,b-1]\) 的和最大，为 \(x_2\)。
同理，我们再在 \([c+1,d]\) 里面找到一个最小的 \(x\)，满足 \([c+1,x]\) 的和最大，为 \(x_3\)。
若 \(x_1+x_2+x_3 < 0\)，就可以说明无论你怎么选区间，你小于等于 \(x\) 的数永远都会比大于 \(x\) 的数多，故 \(x\) 显然不合法，应该将 \(l=x-1\)。
否则，就说明就算 \(x\) 不合法，也会有大于等于 \(x\) 的其他中位数合法，也就是 \(r=mid\)。
这样就可以找到答案了。
秩序怎么维护的话，考虑以权值为时间戳，数组下标为线段树维护的东西，剩下的还是比较好想了。
\(\text{What I learned:}\)
-
关于 T5 的一些 \(\text{trick}\)，如果相同的数之间有不同，考虑通过他们在数组下的下标区分它们。
-
二分的时候，有可能这个数不合法，但是如果你能够找到一个大于这个数（或者小于这个数）合法，那仍然可以二分。
-
要通过贡献的大小来求区间，可以考虑找到所有可能成为答案区间的共性，然后只考虑他们之间不同的地方，来判断他们的大小。
-
将小于 \(x\) 的变成 \(-1\)，大于 \(x\) 的变成 \(1\)，是一个很常用的技巧。
\[\large \text{Round 10 : AtCoder Beginner Contest 320} \]
一言:
当毫无寄托的两颗心紧挨之时，真正的悲伤开始展翅翱翔。
——空之境界
终于在 ABC 搞过了揭老汉啦！
\(\text{F : Fuel Round Trip}\)
首先不难想到一个二维的 \(dp_{i,j}\)，表示走到了第 \(i\) 个点，剩余油量为 \(j\) 需要花费的最少的钱。
但是由于每个加油站只能用一次，所以这样的话就有后效性。
发现 \(n,k\le 200\)，考虑再来一个状态。
既然过去和回来加起来只能选一次，那就考虑把两者都统计，定义 \(dp_{i,j,k}\) 表示，正着走到 \(i\) 的剩余油量为 \(j\)，到 \(i\) 点时的剩余油量为 \(k\)，从 \(i\) 走到 \(n\) 的最小价钱之和。
显然，我们只需要枚举第 \(i\) 个点的油是不用，还是加给 \(j\)，或者是加给 \(k\)。想到这里应该就比较直观了，为了方便，可以考虑顺推。
\(\text{G : Slot Strategy 2 (Hard)}\)
非常容易想到去枚举最终的那个数字，但是我却没有想到可以二分答案。
然后我们考虑去判断。
可以考虑建立一个二分图，左边节点为每一行，（右边节点为时间），连向满足条件的时间（即这个时间转到的是最终数字）。最后看他的最大匹配是否是 \(n\) 即可。
但是这个 \(t\) 可能会比较大，导致右边节点与左部节点连的边的数目太多了。仔细思考可以发现，如果左部节点连的边超过了 \(n\)，那他显然是可行的，所以就不用去连更多的边了。故最终最多只有 \(n^2\) 条边。
所以最终复杂度 \(n^3\log{nm} \times 10\)。
\(\text{What I learned:}\)
-
当每个数有可能正着倒着被预选，但他又只能被选一次，且你只能动态规划时，考虑 \(1-n,i-n\) 的选数同时进行，定义 \(dp_{i,j,k}\) 同时维护进行到的 \(i\)，以及正着和倒着的信息 \(j,k\)，转移的时候看 \(i\) 是给了正着，倒着，还是都没给分别转移即可。
-
有单调性的题目一定不要忘了二分啊！
-
当一个点需要连很多边来实现自己的算法，但是你发现当一个点建立了一定量的边之后他的答案已经已知了，那么对于他之后的边就不要建了，不然容易让算法的时空复杂度假掉。
-
如果对于每一个东西他需要选一个时刻保证其合法，而每个东西选的时刻必须不一样，要看最多有多少个东西合法（或者能不能够让所有东西合法）时，考虑二分图，或者在其他扩展情况下，可以考虑网络流。
\[\large \text{Round 11 : Cqbz Weekly Round 13} \]
一言:
男人从小的时候就是无药可救的。
——秋之回忆
炸裂的一场，主将中的最低分，组长中的倒二。
忏悔啊！
\(\text{D : card}\)
写这道题没什么别的意义所在，只是为了记录一下回退背包的知识点。
这个题目可以非常容易的转化为在所有除去 \(a_i\) 的数所构成的集合中，与 \([k-a_i,k-1]\) 没有交集。
显然，我们可以暴力枚举 \(i\)，然后打一个 \(nk\) 的 0/1 背包。
但是这样的复杂度是 \(n^2k\) 的，所以考虑优化。
我们发现，如果我们求出了 \(1-n\) 所有 \(a_i\) 的 0/1 背包，我们对于枚举到的每一个 \(a_i\)，实际上就是将 \(a_i\) 从这个背包中删除。
由于在 0/1 背包中，你的 \(a_i\) 的枚举顺序是无关大雅的，所以想成可以把 \(a_i\) 放在最后一个转移，那么就有 \(dp[j]+=dp[j-a[i]]\)，并且 \(j\) 是倒叙枚举。
那么要把 \(a_i\) 删掉，那就考虑正序枚举，然后 \(dp[j]-=dp[j-a[i]]\)。
那么这道题实际上就解决了。
（考场上打的 \(nk\log n\) 的神奇二分做法，被卡到90分。）
\(\text{F : open}\)
算是这几次周考代码最少的 T6，但感觉是思维难度最高的。
首先你需要想到一个非常重要的转化。即我们可以求出任意两个传送门之间互相到达的最短距离，然后题目就转化为了求传送门之间的最小生成树。
于是，你得到了重要的前 \(60pts\)。
那么如何优化呢？
我们考虑一个构造生成树的过程，回顾一下 \(\text{kruskal}\) 算法。
对于每次操作，实际上我们都是找到两个还没有联通的传送门中，距离最小的连在一起。
那么考虑将任意一条边拆解为图中最原始的边。
然后对于途中的任意一条边 \((x,y)\)，求出 \(x,y\) 分别到距离最近他们的传送门的距离 \(dis_x,dis_y\)，那么这条边实际的贡献就是 \(w(x,y)+dis_x+dis_y\)。这一步可以考虑多源最短路。然后根据 \(\text{kruskal}\) 的思想，考虑将任意边按照他们的贡献排序，每次连一条边，就是将他们对应的两个传送门连接在一起，最后输出连的边的贡献和。
至于为什么这样是对的，额俺也不会证，俺也不知道。可以理解为，如果没有选择这条边，那么就必然可以将新选的这条边拆解为另外的边，但他们的贡献更少（或者出现了环之类的东西）。
毕竟重点是猜结论，赛时很难证明的。。
\(\text{What I learned}\)
-
如果你需要算除开 \(a_i\) 的一些信息，考虑对动态规划进行回退（例如背包，当然有些无法回退）。
-
如果是 \(n\) 个点，每个点都要用一次，且每个点可以使得另外一个点配合上会产生一个与这两个点信息有关的权值，可以任意配合，考虑生成树。
-
对于生成树上的边，如果是由很多条基本边合在一起的，可以考虑将他们拆解开。
\[\large \text{Round 12 : AtCoder Beginner Contest 321} \]
一言:
只要你在，我便无所不能。
——进击的巨人
感觉只有最后一道题有点意思，其他的就是时间问题，但是速度还是不够快，思维要跟上啊。
有意思的是，周考考了回退背包，这里居然又来一次。。
\(\text{G : Electric Circuit}\)
这个期望又是拿来唬人的，直接状压得到所有的连通块具体包含了哪些点，然后算概率，加起来就是答案。
首先先预处理每个状态中，在 \(a\) 数组中出现了多少次，在 \(b\) 数组中出现了多少次，假设为 \(num1[statu],num2[statu]\)。
首先，如果 \(num1[statu] \not = num2[statu]\)，显然这个连通块是构造不出来的。
然后，我们只考虑 \(num1[statu]\) 和 \(num2[statu]\) 这些点。首先有一个乱排的总方案 \(num1[statu]!\)。但是显然有一些方案是不合法的，它会使得这个连通块不完整，所以要减去这些方案。
考虑从前面的状态转移的到这个减去的方案。先枚举状态 \(k\)，显然满足 \(k\) 是 \(statu\) 的子状态。那么显然，如果你将 \(k\) 状态中的所有 \(num1[k]\) 与 \(num2[k]\) 完全匹配，那么就会使得 \(k\) 这个连通块被独立出来，然后对于其他剩下来的，乱排就可以了，故要减去 \(\sum dp[k] \times (num1[statu]-num1[k])!\)。
减完之后，统计答案的时候，由于只考虑了 \(num1[statu],num2[statu]\) 这些点，所以要将 \(dp[statu]\) 乘上 \((m-num1[statu])!\)，也就是其他边乱排。
最后乘个逆元就行了。
\(\text{What I learned}\)
-
AT 的期望全是唬人的，就是把所有状态的贡献加上就行了。
-
有些时候，为了减去不合法的方案，这些方案数可能可以从其他合法的子状态中转移得到。
\[\large \text{Round 13 : AtCoder Regular Contest 171} \]
一言:
我并不是要失去自由，而是要去收获那无可替代的不自由。
——SSSS.电光机王
几年没写了，但是我们仍然要捡回来！
没啥好写的，T1，T2能力范围之内，T3不会，T4感觉很好，但是没做出来。
\(\text{D : Rolling Hash}\)
这题无论是对 \(\texttt{Hash}\) 的转化，还是转化后染色问题的状压想法，都是非常重要的。
首先，看到要求是一段区间的哈希值不为 \(0\)，我们考虑定义一个前缀哈希 \(s_i\)，其实就是让你 \((s_{r+1}-s_l)\times b^? \not=0\)，也就是 \(s_{r+1}\not=s_l\)。
然后由于 \(s_i\) 与 \(a_i\) 本质上是可以做到一一对应的，所以我们看可不可以构造出一个合法的 \(s\) 即可。
然后这题就转化为：有一个点数量为 \(n+1\) 的图和 \(m\) 条边，现可以用 \([0,p]\) 中的任意整数对图上的点进行染色，要求图上边上的两点颜色不同，问有无合法方案。
接下来就是我确实觉得只能用“技巧”来形容的地方：
我们定义 \(dp_{S}\) 表示对所有在 \(S\) 集合中的点进行合法的染色之后，所需要的最少颜色数量。
显然，我们在染色时，只能对一个独立集进行染色，所以我们考虑枚举 \(T\)，满足其是 \(S\) 的子集，且是个独立集，然后有 \(dp_{S}=\min\{dp_{S},dp_{T}+1\}\)。
最后看 \(dp[2^{n+1}-1]\) 是否小于等于 \(p\) 即可。
\(\text{What I learned}\)
-
面对一段区间的哈希时，可以转化为 \((s_{r+1}-s_{l})\times b^?\)，可能方便处理。
-
面对染色问题，一定想到状态压缩，以及二分图中的一些概念。
\[ \mathrm {To \ Be \ Continued} \] 标签：当网赛,text,可以,溜进,times,枚举,悄无声息,考虑,dp From： https://www.cnblogs.com/SFsaltyfish/p/18049286