1月做题记录

✩ trick
✯ 会大部分，要\(tj\)提示
✬ 会小部分/完全没想到，看了\(tj\)才会
◈ 脑电波
✡ 有某一算法的神秘通用性质
⊗ 待补

• 1月做题记录
  • [ABC363G] Dynamic Scheduling ✯✩
  • [ARC109F] 1D Kingdom Builder ✯

[ABC363G] Dynamic Scheduling ✯✩

对于这种问题，它的静态版是比较普遍的，大概有以下几种性质/做法：

• 最优方案放的数肯定也是最多的
• 最优方案可以按\((D_i,-P_i)\)排序，排序后显然也合法且更方便解题
• 有种贪心的做法，就是从后往前遍历当前时间\(i\)，然后选时限\(\geq i\)的还没放的最大的点放，这也做法也能证明第一点

再来考虑现在动态的问题，即能删除或插入元素，按照第二点维护当前的最优方案序列

对每个时间点记录一下\(val_i\)表示\(i-\)时限\(\leq i\)的放了的点数，那么合法显然要所有点都满足\(val_i\geq0\)

下面的\(val\)都指的原本的\(val\)即还未修改的，\(val'\)就是修改后的

• 对于插入\((d,-p)\)

若\(\forall i\geq d\)，都有\(val_i>0\)，显然\((d,-p)\)可以直接插入了

否则，说明若要插入\((d,-p)\)，则必删除一个元素，那么有两种选择

要么删除时限\(i<d\)的点，这个是直接选最小的那个就好

要么删除时限\(i\geq d\)的点，此时删时限\(i\leq t\)的值最小的元素，其中\(t\)是最小的满足\(val_t=0\)且\(t\geq d\)的时限

• 对于删除\((d,-p)\)

若该元素不在我们维护的最优方案中就不管，否则，考虑用什么元素去顶替它

若用时限\(i\leq p\)的元素顶替，则\(i\)要满足\(i>t\)，其中\(t\leq p\)且是最大的满足\(val'_t=0\)的点

若用时限\(i>p\)的元素顶替，就没有限制了，选个最大的就好

复杂度\(O(NlogN)\)

[ARC109F] 1D Kingdom Builder ✯

考虑判断最后怎样的情况是合法的，显然最后会是一个个连通块

考虑把这个放的过程倒过来，即考虑删的过程，要求每次删的时候，要么它有相邻的棋子，要么其它连通块的两侧没有它的颜色

显然每个连通块都会有个中心点，即最早放/最晚删的那个点

考虑第一个被删的中心点，设它的颜色是\(c\)，反色是\(c'\)，则此时其他连通块两侧都得有\(c'\)

把其它连通块的初始态分为纯色or非纯色，对于非纯色和纯\(c\)的，显然也能用\(c\)当中心点的颜色，即可以依次删完

则此时只剩下了纯\(c'\)色，显然只能至多一个，然后直接删了就行

总结一下合法的局面一定满足：

• 算上连通块两侧的点，第一个中心点被加入的连通块要存在子序列\(c'c'\)
• 算上连通块两侧的点，在中间中心点被加入的连通块的要存在子序列\(c'cc'\)
• 最后一个中心点被加入的连通块要存在子序列\(c\)

以下简称为第一个连通块，中间连通块，最后一个连通块

再考虑满足这个性质的是不是一定合法，显然可以把除最后一个连通块都弄成两侧只存在\(c'\)的情况，那么最后一个连通块和中间的连通块都可以直接删完了，现在只剩一个连通块显然也能删完

那么直接\(dp[i][0/1][0/1]\)表示第一个/最后一个是否被钦定，考虑前\(i\)个且第\(i\)个不选时的合法的局面中（即要选的都得选），最小的连通块长度之和

转移可以发现，满足每种转移需求的都是一个前缀（某些被钦定要选的点对应的转移点会被挖掉），那么子序列自动机+前缀最小值即可

子序列自动机说着多高级，其实就是\(to[x][c]\)表示\(x\)后的第一个\(c\)，如果\(|C|\)够小，直接转移，否则可持久化线段树就好

初始化的时候要给两边多塞\(3\)个，因为是可能会用到某一侧的\(2\)个多的数的，如\(hack\)数据

Input
42
wwwwwwwwwwwwbbbbwwbbbwwbbbbbbbwwwwwwwwwwww
____o___________oo___oo__________________o

Output
8

做法：44(b) -> 17(w) -> 18(w) -> 22(w) -> 23(w) -> 5(w) -> 43(b) -> 42(w)

而用\(3\)个肯定没有意义

复杂度\(O(N)\)