我是彩笔，别人板刷AGC，我板刷ABC和ARC。/fad
ABC378
E - Mod Sigma Problem
注意到取模只对里面的 \(\sum\) 取，所以不能直接对每个数算贡献。考虑怎么把这个 \(\text{mod}\) 去掉，一般是要将其转化成大小比较的形式。现在只能尝试用前缀和改写和式为：\(\sum\limits_{1\le l\le r\le N}\left( (S_r-S_{l-1})\bmod M \right)\)，发现内层的括号是可以去掉的，也就是可以直接对前缀和 \(\bmod M\)，得到的结果就是：
\[\Large{ (S_r - S_{l-1}) \bmod M = S_r - S_{l-1} + \begin{cases} 0 & (S_{l-1} \leq S_r) \\ M & (S_{l-1} > S_r) \end{cases}} \]发现 \(M\) 的个数就是 \(S\) 中逆序对的个数，剩下的 \(S_i\) 直接分开算贡献即可。
F - Add One Edge 2
显然环的端点在原树上要是二度点，中间点是三度点，那么要找到所有合法的链。考虑从每一个三度点的连通块入手，求出这个三度点连通块连了多少个二度点，贡献就是 \(\frac{cnt\times(cnt-1)}{2}\)。注意要求得到的图是简单图，所以不能算上相邻的二度点。
ABC377
E - Permute K times 2
首先应该想到的是数之间的移动会形成多个环，然后打表观察规律，你会发现第 \(i\) 位在第 \(j\) 次操作后的数就是原来的数在他所在的环上走 \(2^{j-1}\) 步到达的数。于是对 \(k\) 模环的长度就能知道最终的数。
错因：不该直接观察整个数列的变化规律，应该问题精确到具体的数上。
F - Avoid Queen Attack
比EG难。转化成有多少个格子被覆盖，考虑对每个皇后的每个方向的覆盖来讨论，会有很多重复的贡献，可以手动容斥掉，较复杂。
G - Edit to Match
修改末尾的编辑距离，容易想到答案是 \(len_i+len_j-2\times LCP\)。多个字符串，有关前缀，考虑字典树。记录下里每个节点最近的结尾字符的距离 \(f[rt]\)，答案就是 \(f[rt]+n-i-1\)。
哈希做法就是对每个串哈希，直接枚举每个前缀对应的最短原串长度就行了，用 umap 维护即可。
错因：脑子笨没想到字典树。想到了哈希做法，但是复杂度想错了，总结为傻逼。
ABC376
E - Max × Sum
考虑按 \(a\) 从小到大排序，钦定最大值就是 \(a_i\)，也就是 \((a_i,b_i)\) 是必选的，剩下要选前面 \(k-1\) 个数使得 \(\sum b_i\) 最小，这个可以用优先队列维护。
错因：没想到排序（
G - Treasure Hunting
贪心难题，自己做根本想不到。首先想到一个假贪心：直接每次都选概率最大的点走。这样显然是不对的，但是注意到对于没有先后选择关系的集合而言这个贪心就是对的。考虑能不能转化成若干个集合合并起来的形式，也就是树上的连通块。考虑已经走到了父节点 \(u\)，有两个连通块 \(i,j\)，记 \(val_i\) 表示遍历连通块的最小期望，\(siz_i\) 是连通块大小，\(p_i\) 是概率之和。如果要 \(i\) 比 \(j\) 先合并到 \(u\) 上，推导出要满足：
\[\Large{ \begin{align*} val_i+siz_i\times p_i+val_j & <val_j+siz_j\times p_j+val_i\\ \frac{siz_i}{p_i} & <\frac{siz_j}{p_j} \end{align*}} \]于是可以用优先队列维护 \(\frac{siz_i}{p_i}\) 为关键字的连通块，每次合并信息，用个结构体封装一下。
总做法：先想不管先后关系的集合怎么做，然后考虑两个集合合并到答案上的先后关系，最有用优先队列来维护。
错因：没有想到转化成集合合并到答案上的先后关系。
ABC375
E - 3 Team Division
值域较小，考虑设 \(dp[i][j][k]\) 表示前 \(i\) 个人使得 A 组强度为 \(j\)，B 组强度为 \(k\) 的最小操作次数。\(j,k\) 的上界是 \(m=\frac{sum}{3}\)，转移式很简单，我都能秒，复杂度 \(O(nm^2)\)。
错因：一开始没想到只需要枚举两组的状态就行了。
F - Road Blocked
删边操作不好做，考虑时光倒流转化成加边，每次加边直接 \(O(n^2)\) 枚举每对点更新，具体来讲就是看 \(x\rightarrow u \rightarrow v \rightarrow y\) 还是 \(x \rightarrow v \rightarrow u \rightarrow y\) 还是仍然 \(x\rightarrow y\)。全源最短路直接Floyd预处理就行。
错因：不会时光倒流这个trick。
G - Road Blocked 2
要删边，很容易想到要从 \(1,n\) 都跑一遍最短路，然后判断 \([dis_{1,u}+w+dis_{v,n}=dis_{1,n}]\) 就可以知道这条边是否在某一条最短路上。但是实际上这条边要在每一条最短路上，所以我们考虑维护 \(1,n\) 到每个点的最短路方案数，如果同时满足 \([cnt_{1,u}\times cnt_{v,n}=cnt_{1,n}]\) 那么这条边就是必要的。注意方案数会很大，要对大质数取模。
错因：没想到计算方案数以及不会算方案数以及可以直接取模。
ABC374
E - Sensor Optimization Dilemma 2
最大的最小值，考虑二分答案。然后问题转化成对每个 \(i\) 求这个：两个物品 \(A,B\)，买一个价值分别为 \(v1,v2\)，代价为 \(w1,w2\)，求最少用多少代价达到 \(K\) 价值。做法是枚举 \(A/B\) 的个数小于 \(v2/v1\) 然后直接算，这样相当于把枚举的那个物品当作是较劣的，复杂度 \(O(v1+v2)\)。
错因：不会转化后的做法。
F - Shipping
首先会看出来这是个dp，并且简单贪心想一下可以观察到每次处理的 \(K\) 的订单都是连续的，那么有一个朴素做法设 \(dp[i][j]\) 表示前 \(i\) 个任务在第 \(j\) 天完成的最小代价，转移是在第 \(j\) 天枚举完成的任务段 \([k,i]\)。但是时间是不可能直接作为状态的。
一个优化思路是只保留有用的时间作为状态，发现有意义的时间点一定能表示成 \(t_i+j\times X,j\in[0,i)\)。那么就可以设状态 \(dp[i][j][k]\) 表示前 \(i\) 个任务在 \(t_j+k\times X\) 时间做完。转移考虑填表法，枚举转移到第 \(i+l\) 个任务：
\[\Large{ \begin{cases} dp_{i+l,j,k+1}=\min(dp_{i,j,k}+(t_j+(k+1)\times X)\times l-(sum_{i+l}-sum_i)) & t_j+(k+1)\times X\ge t_{i+l} \\ dp_{i+l,i+l,0}=\min(dp_{i,j,k}+t_{i+l}\times l-(sum_{i+l}-sum_i)) & t_j+(k+1)\times X\le t_{i+l} \end{cases}} \]按着转移来就行了。
错因：不会设状态优化。
G - Only One Product Name
显然是转化成图论问题考虑。先 \(O(n^2)\) 枚举 \(i,j\) 如果 \(i\) 第二个字符等于 \(j\) 第一个字符就连一条有向边，最后会出来一个一般有向图，问题转化成有向图最小路径覆盖。有几个注意点，首先图有环，考虑把强连通分量缩点。覆盖的路径可以相交，考虑做一遍传递闭包。然后就是经典模型：拆点，每条边 \((u,v)\) 表示左部的 \(u\) 连向右部的 \(v\)，答案是总点数减二分图最大匹配数。
错因：赛时会了做法，但是没写过也不会写，时间也浪费了很多导致没写出来。差点能场切了/ll
标签：记录,板刷,错因,sum,times,枚举,dp,rightarrow From： https://www.cnblogs.com/heshuwan/p/18535994