意识流。

loj3966. 「JOISC 2023 Day1」两种货币

咋看着这么像主席树板子。

*loj3967. 「JOISC 2023 Day1」JOI 国の节日 2

最近咋这么多题差一步/fn

让我翻翻草稿本。

首先发现计数序列等价于计数配对方案。然后发现真实的最优解是按照右端点排序选。

那么能不能考虑确定每个数的配对情况的同时确定答案呢？可以的，所以可以设计状态 \((i,j,k,x,y)\) 表示答案分别为 \(j,k\)，有 \(x\) 个左端点没匹配，\(y\) 个左端点是在最优解最后一个右端点出现的。这样是五次方。

发现只关心 \(j-k\)，四次方。

发现 \(j-k\leq 1\)，三次方。

然后怎么搞呢？其实可以注意到 \(x,y\) 都在系数里面，所以可以尝试把它放进决策里面之类的技巧。或者尝试拿转移换状态，但是转移的系数非常麻烦。

不过可以发现 \(x-y\) 其实比较无关紧要，因为这些区间既不包含在贪心解也不包含在最优解里面，所以可以尝试把这些左端点先解决掉，之后就不要考虑它们的状态了。

但是，有问题啊！假如说我们为它钦定了右端点，但是在真实的右端点处不还是要做一步决策吗？这样不是有后效性了吗？

其实很简单，由于确定了这些位置之后并不影响其它决策，将这些右端点忽略即可。

卡在最后一句话了，火大。

loj3968. 「JOISC 2023 Day1」护照

口胡，感觉不难？

题意相当于求最小集合 \(S\)，满足 \(S\) 覆盖 \([1,n]\) 并且 \(X_i\in S\)。

那么先把 \(X_i\) 加进去，之后就变成了求最小集合 \(S\) 使得 \(S\) 覆盖 \([1,L_{X_i})\cup(R_{X_i},n]\)。拆开变成求覆盖前缀和后缀，这里只讨论前缀。

那么设 \(f_i\) 表示覆盖 \(i\) 前缀的答案，转移形如 \(f_{i}=\min f_j+1\)，条件是存在区间同时包含 \([i,j]\)。

那么线段树一下就可以了？

我测，这个覆盖可能有交。

哦但是如果有交的话就跟 \(X\) 没啥关系了，可以尝试把没有后面一个条件的最优解 \(+1\)。

*loj3969. 「JOISC 2023 Day2」传送带

考虑链怎么做，发现每次把模 \(3\) 的拿出来，然后删掉一些点，然后乱做，就好了！

考虑树怎么做，发现菊花有一次询问的做法，推广到树有 \(\mathcal{O}(\max dep_u)\) 的做法。考虑优化，发现没有二度点就非常好做，有二度点套链的做法，大概是可以做的！

但是这样也太愚蠢了！其实我们人为破坏了问题的很多自然性，只要仿照链，取出模 \(3\) 同余的点，然后询问，套用上面那个做法的判断，就可以了。删掉一些边之后可以套用同样的做法。

但是实际上这个做法也破坏了非常多自然性，其实都根本没必要删边，只需要每次都取出模 \(3\) 最多的，保证所有点都有至少一条出边，就好了！

所以实际上是简单题，但是为啥做了这么久？

loj3970. 「JOISC 2023 Day2」议会

shaber 题遇上了 shaber。

大概就是找到那些在边上的议案，最后相当于要找到剩下的树中与上一个值 \(0\) 的个数最多是多少。这个随便高维前缀和。但是你发现要记录标号，不然可能会重复，所以写的有点烦人，最后实现的是 vector 存，每次合并 vector、去重、排序。

*loj3971. 「JOISC 2023 Day2」水羊羹 2

很好的题，感觉可以放 NOI 的某个 T2。

首先你可以 DP，但是太困难了！

考虑找一点性质，发现小的长度只有可能是 \(1\)，那么可以考虑按小的 DP，二维偏序优化做到单 \(\log\)。

但是这样还是不够优美。考虑继续找性质，发现对于某个点 \(i\)，如果找到最近的点 \(j\)，使得 \(i,j\) 能放在一起，那么 \(j\) 后面的任意点都可以作为 \(i\) 的后继。这是因为如果不合法，那么 \(d_k>d_j,k>j\)，那么 \(j\) 肯定更优。所以可以考虑一个建图：把每个点拆成两个点，一个点连 \(i+1\)，另一个点连 \(j\)，跳的时候交替跳，答案是最长路。

继续探索性质，因为图上的刻画还是太丑陋了，问题在于，对于第二类点，我们能否直接找到最优结点。答案是可以的，我们只需要找到后缀的所有 \(i\) 中满足 \(j\) 最小的位置即可，容易发现这样是最优的。所以直接预处理可以过掉没有修改的包。

其实上述模型还是可以简化的，我们可以只记录跳到的第二类点，然后每次找到后缀 \(j\) 最小的 \(i\)，然后直接跳过去，得到一个子问题。

到这里不会做了。但其实有一个重磅结论：大段长度不超过 \(2\log V\)！！！

然后爱怎么做怎么做，可以用 LCT，也可以线段树加速跳跃，我写的是线段树。

然后是一些胡扯。感觉我做本题的时候找性质都只是找到那种能够转化问题模型的贪心性质，但是最后这个性质是优化规模的，问题模型并没有转变，以后可以多注意以下。另外这种模型的 \(\log V\) 性质其实挺典的阿，我咋没注意到！！！

loj3972. 「JOISC 2023 Day3」合唱

感觉是套路题阿。

首先你考虑怎么求最小分割，发现直接贪心。

但是刻画还可以更加清楚，注意到假如我们按顺序匹配男低和女低，那么匹配是固定的，假设我们把一个匹配看成一个区间，那么问题相当于划分出最少的区间集合使得集合内所有区间有交。如果定义一个区间完全在另一个区间右侧为一个偏序，那么问题相当于最小反链覆盖，转化为最长链，所以相当于我们要找到最长的互不相交的区间链，然后这个显然可以贪心。

那么考虑拿 DP 维护这个贪心，每次维护最长链贪心过程中当前区间集合的最右侧区间。那么找到下一个集合的最右侧区间，那么任务相当于把这两个点之间的所有左端点移动到下个区间最左侧区间的右端点前。我们定义一个左端点的位置 \(b_i\) 表示它之前有几个右端点，转移贡献形如 \(\sum_{k=j+1}^i\max(0,b_i-j)\)。

然后你发现这东西就是个分段问题，猜它有凸性，采用 WQS 可以平方 \(\log\)。

然后发现如果 \(\max b_i<j\) 不优，所以 \(\max\) 可以拆开，转化为一个斜率优化问题。复杂度 \(\mathcal{O}(n\log V)\)。

所以凸性怎么证阿。

*loj3973. 「JOISC 2023 Day3」曲奇

考虑假如我们用的桶的可重集为 \(S\)，如何判断是否合法。

暴力模拟是可行的，但是不够优美。

\(S\) 中所有数相等的情况是经典的，对于 \(S_1=2\) 的情况，条件相当于没有绝对众数。这个条件的根本问题在于，最大值可能根本减不到 \(0\)，仿照这个条件，可以猜出条件为 \(|S|\geq \max a_i\)，证明考虑归纳，每次操作之后的最大值必然 \(-1\)，否则可以发现操作次数大于 \(|S|\)。

不相同的情况是类似的，每次找到最大的 \(S\) 即可。

所以我们找到一个可重集 \(|S|\) 满足 \(|S|\geq \max a_i\) 并且和为 \(\sum a_i\) 即可，这是一个背包问题。如果暴力记录集合大小，集合的和，可以做到 \(\mathcal{O}(\dfrac{n^3}{w})\)。

但是实际上有奇怪的东西。假设 \(f_{i,j,k}\) 表示考虑 \(b_t\geq i\) 的桶，放了 \(j\) 个数，和为 \(k\) 是否可行。那么你发现 \(j\leq\dfrac{\sum a_i}{i}\)，所以状态数为 \(\mathcal{O}(n^2\log n)\)，完全背包转移是 \(\mathcal{O}(1)\) 的，bitset 做到 \(\mathcal{O}(\dfrac{n^2\log n}{w})\)。

假了，忘记证明有 \(k\) 个非零数了！！！但是背包是对的！！！

考虑判断一个可重集是否合法。考虑这样一个过程，方法是把同种 cookie 按照数量从大到小排成一列，然后一行一行取。这样取前 \(i\) 个数的时候只需要关心前 \(i\) 行的状态。猜测合法条件就是每次 cookie 的个数都够，形式化地描述，假设集合从大到小排序的结果是 \(S\)，那么条件为 \(\sum_{j\leq i} S_j\leq \sum_j\min(j, a_i)\)。

证明：考虑每次加一行的时候取出现次数最多的，出现次数相同的取 \(a_i\) 最小的。考虑非零元素的变化：如果上一次操作的非零元素数量没有减少，那么由于盒子大小递减，所以仍然合法；如果元素减少，那么这次操作会加入一些元素，如果和原来的元素有重叠，那么可以说明种类数和上次相同，仍然合法，如果没有重叠，那么非零元素个数和剩余元素个数相同，根据最上面的不等式，仍然合法。

拿这个条件就可以 DP 了。从大到小做，设 \(f_{i,j,t}\) 表示大于 \(i\) 的用 \(j\) 个，\(t\) 是否可行，bitset 的转移。由于 \(ij\leq m\)，所以复杂度为 \(\mathcal{O}(\dfrac{n^2\log n}{w})\)。

loj3977. 「JOISC 2023 Day4」Bitaro 之旅

nfls 模拟赛好像考过加强版。