记录一下 JOISC 2023 的做题记录
Day1 T1 Two Currencies
给定一棵树，在边上有总计 \(m\) 个检查站，经过一个检查站需要叫 \(1\) 枚金币或者若干枚银币。\(Q\) 次询问，问一个人有 \(X\) 枚金币和 \(Y\) 枚银币，能否从 \(u\) 走到 \(v\)，同时回答最多可以留下多少枚金币。
发现一定是用银币卖掉价值路径上银币代价前 \(k\) 小的检查站，考虑用整体二分，使用树状数组维护重链剖分维护，时间复杂度 \(O(n\log^3n)\)。
Day1 T2 Festivals in JOI Kingdom 2
给出一个错误的贪心方式，问有多少种构造可以使得这个DP假掉。
首先我们要知道正确的 DP 怎么写。
将所有的区间按照右端点排序，每一次选择右端点最小且与没有与已经选择的区间有交的区间。
我们称正确的算法选中的区间为红区间，错误的算法选中的区间为蓝区间，两个算法都选择了的区间叫做紫区间，两个算法都没有选择的区间叫做黑区间。
显然，任何红区间两两无交，蓝区间两两无交。
而且，相邻的两个红区间的右端点之间不会包含任何的完整区间；相邻两个蓝区间的左端点之间不会包含任何区间的左端点。
我们不好考虑红区间比蓝区间多的情况，但是我们可以考虑他们相等的情况，然后用 \(\prod\limits_{i=1}^{N} (2*i-1)\) 减去即可。
则我们可以将红蓝区间两两配对，则红蓝数量相等的情况下，每一对红蓝区间必然有交。
我们还可以证明第 \(i\) 个红区间的右端点必然大于第 \(i-1\) 个蓝区间的右端点（否则红蓝无法匹配），必然小于第 \(i\) 个蓝区间的右端点（否则不满足正确算法的贪心）。
由于所有的红蓝区间是配对的，所以考虑依次插入每一对红蓝区间。
插入的同时，我们可以处理所有右端点在两次的红区间之间的所有黑区间，这些区间的左端点必然在上一个红区间的右端点之前。
所以我们需要设计状态：\(f_{i,k,0/1}\) 表示插入了前 \(i\) 个红蓝区间，预留了 \(k\) 个空位给黑区间的左端点。转移需要枚举插入的黑区间数 \(j\)，复杂度是 \(O(n^3)\) 的。
枚举插入的黑区间数是不可避免地，考虑优化DP的状态。
我们发现我们专门用了一位 \(k\) 来维护黑区间的左端点，所以考虑反转整个过程，\textbf{从右向左}加入每一对红蓝区间，只需要保证插入的黑区间右端点在上一个红区间的右端点之后即可。而对于这些黑区间的左端点，只需要保证不在下一个区间的右端点和上一个区间的左端点之间即可。
考虑设计状态：\(f_{i,0/1}\) 表示插入了后 \(i\) 个区间，由多少种方案，转移枚举插入的黑区间数 \(j\)。
对于转移来源和转移结果的 \(0/1\) 状态不同，我们可以得到如下的四种转移：
\(f_{i+j+2,1}\gets f_{i+j+2,1}+f_{i,1}\times (j+1)\times (j+2)\times (2i-3+j)^{\underline{j}}\)。
\(f_{i+j+1,0}\gets f_{i+j+2,0}+f_{i,1}\times (j+1)\times (2i-3+j)^{\underline{j}}\)。
\(f_{i+j+2,1}\gets f_{i+j+2,1}+f_{i,0}\times (j+1)\times (2i-2+j)^{\underline{j}}\)。
\(f_{i+j+1,0}\gets f_{i+j+2,0}+f_{i,0}\times (2i-2+j)^{\underline{j}}\)。
这样就可以做到 \(O(n^2)\) 的复杂度，卡一卡常就可以通过了。
但是还可以优化，状态不可能再优化了，所以考虑优化转移。
例如对于第一个转移：
\(f_{i+j+2,1}+= f_{i,1}\times (j+1)\times (j+2)\times (2i-3+j)^{\underline{j}}\)
我们令 \(k=i+j+2\)，可以得到：
发现式子中只有 \(i\) 和 \(i+k\)，我们最终要得到的是 \(k\)，典型的差卷积形式。
其他三个式子也是类似的，这样我们处理的问题就变成了一个半在线卷积的问题。
使用任意模数 NTT 可以做到 \(O(n\log ^2n)\)，使用 Karatsuba 算法可以做到 \(O(n^{\log_23})\)，均可通过此题。
Day1 T3 Passport
你可以在第 \(i\) 个国家消耗 \(1\) 的代价获得一个可以到达 \([L_i,R_i]\) 国家的通行证 \(L_i\leqslant i\leqslant R_i\)，\(Q\) 次询问，问初始在第 \(X_i\) 个国家，至少需要消耗多少的代价才能到达任何国家。
由于 \(L_i\leqslant i\leqslant R_i\)，所以只需要能够到达 \(1\) 和 \(N\) 就可以到达任何节点。
所以不难得到最终的行走方案是先一起走一段路，然后分叉分别走向 \(1\) 和 \(N\)。
例如考虑只走向 \(1\) 的情况，设 \(f_i\) 为从第 \(i\) 个节点走到 \(1\) 至少要几步，则可以得到转移 \(f_i=\min\limits_{j=L_i}^{R_i}f_j+1\)，使用 Dijkstra 优化转移，用线段树合并优化建边。
时间复杂度 \(O(n\log^2n)\)。
Day2 T1 belt conveyor
Day2 T2 council
有 \(N\) 个议员和 \(M\) 个议题，每个人都对每个议题持支持或反对的态度，要选择一个主席和副主席，对于每一个议题，如果除两位主席外支持的人数不小于 \(\left\lfloor\dfrac{N}{2}\right\rfloor\)，这个议题就会通过，问每一个人当主席的时候，最多会通过多少个议题。
发现对于某一个人为主席的时候，只有那些当前是 \(\left\lfloor\dfrac{N}{2}\right\rfloor\) 票的议题才有可能会因为副主席而不被通过，假设这些议题的集合为 \(T\)。
记每一个议员通过的议题构成集合 \(S_i\)，则对于每一个 \(i\)，要求 \(\max\limits_{i\neq j}(\operatorname{popcount}(T\& S_j))\)。
对于每一个数 \(S_i\)，使用前缀和得到他的所有子集，每一个子集对应的答案就是他的 popcount，则最终我们就是要找到一个最大的 popcount，使得存在它的一个子集是有值的。
时间复杂度 \(O(m2^m+nm)\)。
Day2 T3 Mizuyokan 2
Day3 T1 Chorus
有 \(2N\) 只海狸唱歌，其中有 \(N\) 只唱高音，有 \(N\) 只唱低音，初始给定他们的位置，问至少要调换多少对海狸，才能使得可以将这个 \(2N\) 的序列分成 \(k\) 个子序列，每个子序列都是前 \(\dfrac{len}{2}\) 个为高音，剩下的唱低音。
将 \(AB\) 序列转化成一条折线，遇到一个 \(A\) 就向上走，遇到一个 \(B\) 就向右走。则对于一个满足条件的折线，要至少能找到这样一个序列 \(p_0,p_1,p_2\dots p_k\)，其中 \(p_0=0,p_k=N\)，要求点 \((p_{i-1},p_i)\) 在折线下方。对于一条不合法折线，它的代价就是和一个满足条件的折线的面积差的最小值。
我们设计状态 \(f_{l,k}\)，表示当前处理到 \(p_k=l\) 时的答案。发现转移为 \(f_{r,k+1}=\min(f_{l,k}+S(l,r))\)。
发现 \(S(l,r)\) 具有凸性和包含性，所以 \(k\) 为可以 WQS 二分处理掉，然后发现 \(l\) 维可以斜率优化，复杂度 \(O(n\log V)\)。
Day3 T2 Cookies
有 \(N\) 中饼干，其中第 \(i\) 种有 \(A_i\) 个；现在要把所有的饼干装进盒子，有 \(M\) 种大小的盒子，问至少需要多少个盒子，才能让每个盒子装满且里面的饼干互不相同。