JOI 合集。
这个，大概是按，切题顺序
P14420 [JOISC 2014] 历史的研究 / HISTORICAL RESEARCH
这期讲过。
回滚莫队板子，莫队时枚举每个块，块内打暴力，块外以左端点为标准，从块右端点往左端点每次做 O(N)O(\sqrt N)O(N ) 的暴力转移，右端点一直移动即可。每个询问做完回滚状态数组规避直接删除元素。然后直接做。
P9525 [JOIST 2022] 团队竞技 / TEAM CONTEST
！？简单贪？！
考虑堆对每个能力维护最大值，如果没有重复则是最优，否则当前重复的元素是不可能和后面任何元素继续匹配的。然后发现做完了，不合法情况把重复的元素在三个堆里面都删除就行了。
P9599 [JOI OPEN 2018] 木琴 / XYLOPHONE
这期讲过。
简单题，查询每个长度为 222 和 333 的区间，前者显然能帮我们判断相邻元素差，后者能通过极差和排列性质让我们判断相邻的二元组是否单调，可以通过第一个二元组符号判断整个排列真实数值，考虑第一个二元组分别是上升和下降的情况哪个合法即可。
P9196 [JOI OPEN 2016] 销售基因链 / SELLING RNA STRANDS
板题。很有意思。
多个字符串对多个字符串进行贡献，每个有序对只有一次贡献，考虑能不能 ACAM。如果我们用 ACAM 一定是要转化的，要求一边能匹配前缀一边能匹配后缀，那我们把基因库里的字符串自己拼特殊字符拼自己，就有了一个后缀接特殊字符接前缀的性质，对查询串后缀拼特殊字符拼前缀即可。然后就是多模匹配，不跳 fail，最后做个前缀和，直接输出每个串末尾节点的答案。
P6116 [JOI 2019 FINAL] 有趣的家庭菜园 3 / GROWING VEGETABLES IS FUN 3
太牛了这题。我还得练。
小清新啊。交换两个同颜色的花盆没有必要，因此最后同一颜色的花盆内部顺序肯定是不变的。套路地设 f(i,j,k,l),l∈0,1,2f(i,j,k,l),l\in {0,1,2}f(i,j,k,l),l∈0,1,2 表示考虑前 iii 个花盆，jjj 个 000 颜色，kkk 个 111 颜色，第 iii 位为 lll 的次数。下面的 dp 思路都是考虑从上一个不同颜色的状态转移。如果以 222 颜色为例，若前 iii 个花盆中已经存在了 jjj 个 000 颜色和 kkk 个 111 颜色，我们直接让下一个 222
前移把多余的其他颜色挤开回去即可；否则如果目前要转移的原状态区间内某种颜色比原来更多了，肯定是之前的操作使这部分元素前移了，然后恰好前移多少个异类元素我们下一个要放到末尾的颜色就会后移多少（同一种颜色不会把它撞到后面去），分别统计另外两种颜色把它往后撞了多少（前缀和一下就可以快速查询区间里原来有多少个某种颜色），得到新位置，把它从新位置直接移到第 iii 位我们这个转移就是对的了。复杂度 O(n3)O(n^3)O(n3)。
P6879 [JOI 2020 FINAL] 集邮比赛 3 / COLLECTING STAMPS 3
还是太弱了，开题时有几个点没有想到。
很明显是个区间 dp，首先肯定需要做个化环为链，起点直接插中间，初始化可以确保状态从起点转移才是优的。dp 当然是哪个维度小我们就设哪个，时间这东西很不好转移，直接把答案（收集了多少个）拿过来当一个维度，收集时间变成 dp 维护的答案。另外两个维度自然是区间。一般区间 dp 转移需要 O(n)O(n)O(n) 的复杂度，我们的复杂度就是 O(n4)O(n^4)O(n4) 了，咋办？但是我们的移动确保了被收集的物品区间一定是逐步向外扩展的，dp 状态每次只扩展出一个，而不是像一般区间 dp 可以直接将两个被分割开的区间直接并一起，那么对区间 [l,r][l,r][l,r]，只用考虑
[l+1,r][l+1,r][l+1,r] 和 [l,r−1][l,r-1][l,r−1] 两个地方的状态即可，这其实是经典 trick。然后很快啊！注意到诶你走到的位置不是不在最左边就在最右边吗，那分讨两种状态不就把问题转化为 A+B Problem 了？转移时我们也可以轻松考虑爆炸的情况。显然地，最终答案是所有长度合法且所需时间不为初始值 inf 的区间中收集数这一状态最大的值。
P7405 [JOI 2021 FINAL] 雪球 / SNOWBALL
简单题，为啥没做出来，我是区。哦哦哦因为做过 USACO 某个神秘二维数点题导致以为这题也是 ds 数点。对啊，二分题怎么能评青呢，对啊。
哦哦哦每个点移动过程一模一样，相邻的球到底是怎样妨碍我的！哦哦哦如果我有一次占领了一个点，别人从来没到过，那这段区间肯定全是我的了！发现这是可以二分的，某个时间以前两球之间没被榨干，自此以后这段间隙里的雪一滴都不剩了，统一计算雪球每个时间点曾最左移动到哪和最右移动到哪就能找到这个冲突点，我移动的轨迹碰到别人轨迹了。然后对每个相邻的雪球都玩这么一套二分，过了过了。
P8162 [JOI 2022 FINAL] 让我们赢得选举 / LET'S WIN THE ELECTION
我们冲刺群的人已经就本次模拟赛题目难度达成一致。其原因是这模拟赛咋全是洛谷原题哦。拜谢 T3，沉迷水群水洛谷水按错宫导致我完全开摆了导致我这题打了点部分分连 O(n4)O(n^4)O(n4) dp 都没搓而且这场的数据是啥啊还有人假贪心过这题来着唉牛了牛了。
发现我们的演讲肯定是目前所有支持者一起进行同一个演讲，这样一定是比分头演讲更优的。并且每个州只有三种情况，不演讲、获得选票和既获得选票又获得支持者三种情况，这样就在多维 dp 的实现范围内了，看数据范围也能验证我们对做法的猜测。不演讲、获得选票和既获得选票又获得支持者三种情况分别为 A\text{A}A、B\text{B}B、C\text{C}C 类州，dp 状态为 f(i,j,k)f(i,j,k)f(i,j,k) 表示考虑 iii 个州，获得 jjj 个选票和 kkk 个 B\text{B}B 类的情况。
但是还要先钦定一种 dp 顺序，那我们尝试确定一种最优的顺序。发现 A\text{A}A 类州唯一的作用是加选票，无论顺序怎么放只要演讲过就有贡献，而 B\text{B}B 类演讲完可以提升后面的演讲效率且提升幅度是一样的。那肯定要把所有 B\text{B}B 放前面，所有 A\text{A}A 放后面。！？BA？！然后对于 B\text{B}B 类，反正贡献一样，越早把支持者拿下后面就越快，按 BiB_iBi 升序排序显然是最优的。所以我们 dp 前先对序列按 BiB_iBi 升序排序。
然后分三种情况，当前州不选，答案就直接是 f(i−1,j,k)f(i-1,j,k)f(i−1,j,k)；选为 B\text{B}B 类，前面吃过了 k−1k-1k−1 次加成，答案就加上 Bik−1\frac{B_i}{k-1}k−1Bi ；选为 A\text{A}A 类，我们的顺序肯定放在所有 B\text{B}B 类之后，但我们现在还不清楚最后要选多少个 B\text{B}B 类，只能每次钦定一个数 ttt，对 ttt dp 时这个转移就为
f(i,j,k)=f(i−1,j−1,k)+Ait+1f(i,j,k)=f(i-1,j-1,k)+\frac{A_i}{t+1}f(i,j,k)=f(i−1,j−1,k)+t+1Ai 。这样 dp 是 O(n4)O(n^4)O(n4) 的。
怎么优化呢？其实枚举 ttt 的做法还是有前途的，因为 B\text{B}B 类转移和 A\text{A}A 类转移没关系，我们可以只转移 B\text{B}B 再想着怎么去算 A\text{A}A。看起来，前面的序列既有 A\text{A}A 又有 C\text{C}C，这样很难搞。但是实际上序列并不是混合的，最后一个 B\text{B}B 类州之前肯定是没有 C\text{C}C 类的，因为这样不如把二者交换一个，原来那个 C\text{C}C 变成 B\text{B}B 之后 BiB_iBi 更小了，是更优的。所以，如果我们 dp 只考虑 B\text{B}B，前面的序列就只有
B\text{B}B 和 A\text{A}A 了，把原来那个 jjj 省略，定为 i−ki-ki−k 即可。dp 后还有若干个 A\text{A}A 州，显然应当取 AiA_iAi 最小的一组，这里排序后就能直接贪心。我们做完 O(n3)O(n^3)O(n3) 的 dp 后再逐个加上后面的贡献更新答案就行了。
