AtCoder
ABC 347
- D: 很简单不说了
- E: 每个 query \(q_i\) 求一下当时的 \(|S|_i\) ，同时求出每个数 \(a_j\) 出现的位置，然后对 \(|S|_i\) 求前缀和，最后从 \(a_1\sim a_n\) 分别用前缀和的出现位置求一下即可，最后的复杂度应该是 \(\mathcal{O}(n\log{n}+n)\)
- F:
- 这种处理高维信息的题真是我的弱项啊
- 一开始按照以前的经验在想一维的情况下要怎么搞，然后要怎么转化为二维，结果就是没想出来
- 不应该陷入经验主义怪圈的，样例还是要手玩一下的，毕竟我连样例给了几张图都没发现，也许看到样例的图片会有新的发现
- 题解的做法是观察发现所有不重合的小正方形之间必然可以以一个点为分界将整个大正方形划分为三个矩形区域，使得每个小正方形分别处于一个矩形区域中，而只要矩形区域是确定的，那么求出其中和最大的一个小正方形区域是（在思路上）很简单的一件事，因此我们只需要枚举这个分界点即可，求最大小正方形可以用二维的线段树来解决
- 不过我不会树套树（，flag: 争取省赛前能学一下
- G:
- 可恶，怎么又是二维
- 对于每个点的 cost 就是它与它上下左右的点的差的平方和，观察样例给出的“热力图”，然后想到了 3b1b 介绍卷积的那个视频，但是我忘了怎么卷积了，然后又突然想到了网络流，但是网络流我也不会（，遂看题解
- 好好好，确实是转化为网络流中的最小割问题，不过还得先搞成一个 Monge array 的形式，这又是啥？
- Project Selection Problem
- 4-6 Monge arrays
- flag: 省赛前真有必要学一学网络流
ABC 346
- D: 如果是把 \(S\) 转换为相邻字符不同的字符串，那么只需要扫两遍 \(S\)，分别为
0 开头和以 1 开头，如果和前面的字符相同就加上 \(C_i\)，最后将 01 串转换为一个 good string 只需找到之前加上过的最大的 \(C_i\) 减掉即可，两种 \(S^\prime\) 取较小值即可。
- E: 倒着做一遍所有操作，这样不需要记忆前面操作对后面的操作的具体的影响。如果当前将第 \(i\) 列涂为 \(x\)，那么对 \(x\) 的贡献是 \(H-cnt_{row}\)，其中 \(cnt_{row}\) 表示前面被操作过的行数，如果当前列已经被操作过了，那么贡献是 0，可以用 bitset 来记录行列的被操作的情况。最后统计颜色 \(0\) 的数量就用 \(H\times M\) 减去当前统计颜色数量总数即可。
- F: 稍微手玩一下样例可以看出可能的构造方式，然后就会发现二分会比较好做。
- G:
- 第一个想法是 DP 计数，然后就会发现去重十分困难，遂看题解
- 题解的思路是按照一个数 \(A_i\) 的贡献来计算的，假设上一个与它相等的数下标为 \(j\)，下一个的下标为 \(k\)，那么 \(i\) 的贡献为 \((i-j)\times(k-i)\)，之后再考虑去重的问题，可以发现重复的部分就形式来看与矩形重叠部分相似，于是问题转化为左下角坐标为 \((i, j)\) 右上角坐标为 \((k, i)\) 的矩形之间面积求并了，这时候用扫描线解决
- 其实一开始就是觉得“按照一个数 \(A_i\) 的贡献来计算的”的方式根本无法去重才没有考虑的，之后应该看到去重与坐标（区间）之间的相对位置严格相关、并且贡献的计算公式是区间坐标之间的乘积形式（矩形面积计算），可以考虑一下是否能转换为扫描线问题
- 还有一种解法是 DS 优化建图，不会，有空学学
ABC 345
- D: 按照左上角坐标爆搜，大力出奇迹
- E:
- 唉，DP
- 虽然一开始也想到了用 DP，但是没考虑到当前小球的状态只与前一个被保留了的小球有关，而不是它的上一个小球，看题解死活没看懂他们咋用的滚动数组，唉
- 过了两天，我好像搞懂了很多题解的思路了。
- 首先设 DP 方程为 \(f_{i,j,k}\) ，其中 \(i\) 表示当前枚举到第 \(i\) 个小球并强制保留它（这样设置会比较方便），\(j\) 表示上一个被保留的小球的颜色，\(k\) 表示当前移除的小球的数量，\(f_{i, j, k}\) 表示当前剩余小球的最大价值。如果上一个保留的小球的下标为 \(pos\) ，那么存在约束 \(i-pos-1 \le k\) ，因此暴力枚举上一个保留的小球的话只需要枚举最多 \(K\) 次，此时的复杂度是 \(\mathcal{O}(nk^2)\)
- 然后考虑优化。如果第 \(i\) 个小球的答案是由第 \(p\) 个小球的答案转移过来的，那么它们肯定满足 \(k_p=k_i-(i-p-1), C[i] \not= C[p]\) ，并且 \(f_p\) 是所有满足上述约束中最大的，因此我们枚举完第 \(i\) 个小球的时候可以用 \(f_i\) 去更新后面 \(K\) 个小球的答案 \(f_{s, C[i], k_i-(i-p-1)}\) ，此时我们可以省掉中间一维的状态，总的状态数是 \(\mathcal{O}(nk)\) 的，但是转移的复杂度是 \(\mathcal{O}(k)\) 的（一个 \((i,k)\) 可以更新到多个 \((p,k_p)\) ）
- 再观察 \(k_p=k_i-(i-p-1)\) ，它可以变形为 \(k_p-p-1=k_i-i\) （ \(p\) 去更新 \(i\) ），这样等式左右两边都只与 \(i\) 相关，方便我们维护某些有效状态，根据这个式子，我们可以对每个 \(k_p-p\) 都维护一个最值，用这个最值来更新 \(f_i\) ，要满足颜色的限制的话只需要再多维护两个值，一个是这个最大值的颜色，另一个是与它颜色不同的最大值，这样就可以做到 \(\mathcal{O}(1)\) 转移了
- 最后还有一个细节就是得到的 \(f_{n,k}\) 是没有考虑删除第 \(n\) 个球的，因此我们需要在最后加上一个不存在的小球
- F: 先考虑图是一条链的情况，然后会发现无论如何操作点亮的灯数必然是偶数，所以 \(k\) 如果是奇数则输出
No 。之后考虑图是一棵树，发现可以先将叶子结点关灯，之后将叶子结点去掉得到的依然是一棵树，可以重复以上操作直到刚好亮了 \(k\) 盏灯，对于不是树的普通图在 dfs 的过程中得到的也是一棵树，于是一样的做法 dfs 一遍即可。
- G: 不会做，生成函数啥的也不会，想到了求解 \(x_1+x_2+\dots+x_n=m\) 方程的整数解数，尽管不能应付 \(x_n\) 是取 \(\min\) 的情况，但是感觉也是个不错的 idea
ABC 344
- E: 想复杂了，想到用类似于 BST 的数据结构来维护，没想到双向链表但是把前后的连边改成 map 映射就直接解决了🤡
- F:
- 想了很久，基本贪心策略都想到了，但是却不会最后的状态设计以及转移，真得好好练练 DP 才行
- 首先的一点是看到 \(N\le 80\) 应该要想到 \(\mathcal{O}(n^4)\) ，其中枚举当前位置 \((i, j)\) 必然占了 \(\mathcal{O}(n^2)\) ，既然已经想到了任何点都一定是由一个停留点直接转移过来的，那么这剩下的 \(\mathcal{O}(n^2)\) 必然就是枚举那个停留点了，哪怕没有 \(\mathcal{O}(n^4)\) 的提示也应该要这么想才对，DP 题不要怕枚举，如果觉得有点暴力不妨思考一下状态的转移会有什么优化
- 一开始只想到了枚举到终点的停留点，但是却不知道停留点的停留点要怎么找，然后想到到终点的最优路径也是由到停留点到最优路径直接转移来的，满足最优子结构，显然应该用 DP，既然如此，状态必然设成到某个点 \((i, j)\) 的最短时间，然后另外再枚举到那个点的停留点 \((x, y)\) ，既然已知了停留点和终点，那么 \(f_{(i, j), (x, y)}\) 必然就是由 \(f_{(x, y), (x, y)}\) 直接转移而来，然后我们考虑 \((i, j)\) 是否有可能成为停留点，既然路径上既会经过 \((x, y)\) 又回经过 \((i, j)\) 那么如果 \(P_{(i, j)}<P_{(x, y)}\) 我们肯定不如再在 \((x, y)\) 多停留一会儿，因此 \(f_{(i, j), (x, y)}\) 能够更新 \(f_{(i, j), (i, j)}\) 的充要条件是 \(P_{(i, j)}\ge P_{(x, y)}\) 。需要注意，除了用 \(f\) 记录最短时间，我们还需要用 \(g_{(i, j), (x, y)}\) 来记录一下最大金钱，因为转移方程还需要用到 \(g_{(x, y), (x, y)}\)
- G:
- 没什么思路，可能是我主观上觉得红题肯定切不掉导致的吧
- 首先 \((A,B)\) 数量级很大，看成 \(\mathcal{O}(Q)\) 个直线显然会比较麻烦，而 \(Y_i\ge A_i\times X_i+B_j\) 可以转换为 \(-A_i\times X_i +Y_i\ge B_j\) ，也就是以 \(-X_i\) 为斜率、\(Y_i\) 为截距的直线，这样直线的数量就减少到了 \(\mathcal{O}(N)\)
- 之后我们将 \((A,B)\) 看作点，想象一条线从左往右扫描，对于每一个 \(A\) ，将 \(B\) 排序，然后每一个 \(B\) 都二分答案即可求解，关键在于从左往右扫描时直线的先后顺序变化
- 假设 \(A_i < A_j\) ，在 \(A_i\) 处有 \(-A_i\times X_k + Y_k\ge -A_i\times X_l + Y_l\) 也就是说直线 \((X_k, Y_k)\) 在直线 \((X_l, Y_l)\) 上面，如果在 \(A_j\) 时它们的位置交换，变成 \(-A_j\times X_k + Y_k\le -A_j\times X_l + Y_l\) ，将这两个式子中的 \(A\) 孤立出来可以得到 \(-A_i\times (X_k-X_l)\ge Y_l-Y_k\) 和 \(-A_j\times (X_k-X_l)\le Y_l-Y_k\) ，然后我们可以得到 \(A_i\ge \dfrac{Y_k-Y_l}{X_k-X_l}\) 和 \(A_j\le \dfrac{Y_k-Y_l}{X_k-X_l}\) ，于是我们只需要维护相邻两条直线的 \(\dfrac{Y_k-Y_l}{X_k-X_l}\) ，如果从 \(A_i\) 扫到 \(A_j\) ，它们与 \(\dfrac{Y_k-Y_l}{X_k-X_l}\) 到大小关系发生了变化，我们就将这两条直线的位置交换即可
- 具体而言，先将 \((A,B)\) 按照先 \(A\) 后 \(B\) 从小到大排序，然后考虑 \(A=-\infty\) 时直线的大小关系，也就是将 \((X, Y)\) 按照先 \(X\) 后 \(Y\) 从小到大排序，然后用一个小根堆维护相邻直线之间的 \(\dfrac{Y_k-Y_l}{X_k-X_l}\) ，对每个 \(A_i\) 先用小根堆交换好直线的位置关系，然后 \(B_i\) 再二分答案
ABC 343
- E:
- 唉，越做越菜了是怎么回事
- 首先应该不难想到我们肯定可以固定一个立方体的坐标在 \((0,0,0)\) ，而另外的两个立方体任何一个轴上的坐标都可以限定在 \([0, 7]\) ，这样我们只需要暴力枚举剩下两个立方体的坐标即可
- F:
- 丢人，线段树板子题都没做出来，还在想什么带修莫队、CDQ 分治🤡
- 还是太久没做数据结构题了，居然觉得线段树做不了
- G:
- 甚至想到了在 AC 自动机上 dfs，虽然不知道对不对，但总之感觉这种做法很玄学
- 首先两个字符串的拼接求一个 KMP 可以轻松求出答案，那么我们只需要考虑 \(n\) 个字符串的拼接顺序即可，直接暴力枚举的复杂度是 \(\mathcal{O}(n!)\) 的，显然不行
- 由于 \(N\le 20\) ，我们应该想到状压 DP 来优化。用 \(i\) 表示状态，第 \(k\) 个 bit 为 1 就代表当前的拼接字符串已经考虑过第 \(k\) 个字符串了，想要将第 \(x\) 个 bit 翻转为 1，就需要知道它在状态 \(i\) 的字符串中放在哪一个位置，而我们没有保存 \(i\) 的字符串顺序，并且原来最优的顺序拼接上 \(x\) 后并不一定最优，因此我们需要增加一维状态来限制可能的字符串顺序到只有一种，一种方案就是仅考虑将 \(x\) 插在最后面，牵扯到也只有原来的字符串的最后一个字符串了，具体而言，将 \(f_{i,j}\) 表示状态为 \(i\) 以第 \(j\) 个字符串结尾的最短拼接字符串长度，我们预处理出任意两个字符串拼接的最短长度即可直接进行转移了
- 在考虑如何转移时出现了 undeterministic 的情况时，一般来说是状态的设置问题，要么状态设置少了（记忆少了），要么就是设置了错误/无关的状态
ABC 342
- E: 显然是建反图然后求最短路
- F:
- 私密马赛，在高铁上随便想了想，浪费了一道 DP 概率好题
- 不难发现我们和对手掷骰子的过程是独立的，因此很自然地会想到先求出 \(y\) 取值为 \(i\) 的概率 \(p(i)\) ，然后第 \(k\) 次掷骰的结果显然是依赖于第 \(k-1\) 次的结果，因此我们考虑 DP 计数，也就是 \(p(i)=\sum_{j=i-D}^{i-1} \dfrac{p(j)}{D}\) ，注意边界条件 \(p(0)=1\)
- 之后考虑我们的决策。假设当前 \(x=i\)，我们有两种选择：继续掷骰子或者停止，需要求出的是此时的胜率 \(f(i)\) ，不妨分别计算两种选择的胜率
- 继续的胜率 \(c(i)\) : 取决于 \(x=i+1, \dots, i+D\) 时的胜率，即 \(c(i)=\sum_{j=i+1}^{i+D}\dfrac{f(j)}{D}\)
- 停止的胜率 \(s(i)\) :
- 若 \(i>N\)，则 \(s(i)=0\)
- 否则 \(s(i)=\sum_{j=N+1}^{\infty}p(j)+\sum_{j=1}^{i-1}p(j)\)
- 于是 \(f(i)=c(i)+s(i)\) ，\(f(0)\) 即是要求的答案
- G: 数据结构水题