nb 的题单

link

完成度：\(4/50\)。

335.P9293 [ROI 2018] Addition without carry

二分答案，判断当前位是否能为 \(0\)，然后钦定后面位全是 \(1\)，这样匹配一定最优。

假设当前 \(\max a_i=A\)，填到第 \(B\) 位，讨论：

• 若当前位是 \(0\)：
  • 若 \(|A|\ge B\)，无解；
• 若当前位是 \(1\)：
  • 若 \(|A|>B\)，无解；
  • 若 \(|A|=B\)，删掉 \(A\)，加入 \(A-2^B\)；
  • 若 \(|A|<B\)，直接删掉 \(A\)；
• 当 \(a_i\) 为空时有解。

考虑 \(a_i=2^{k_i},k_1\ge k_2\ge \cdots \ge k_n\)，则最优解中 \(\sum b_i\) 的最高位 \(L_b=\max_{i=1}^{n}(k_i+i-1)\)。

证明：必要性，\(i\) 前面的数至少要一位来填；充分性，取 \(b_i=2^{l_b-i+1}\ge 2^{k_i}\)，一定可行。

由此推广到普遍情况，设 \(2^{k_i}\le a_i<2^{k_i+1}\)，则 \(L_b\ge \max_{i=1}^{n}(k_i+i-1)\)，令 \(a_i=2^{k_i+1}\)，有解，则 \(L_b\le \max_{i=1}^{n}(k_i+i)\)。

每次判断一个 \(L_b\)，找到取到 \(\max\) 对应的 \(k_t\)，首先 \(k_1,\cdots k_{t-1}\)，一定是直接删除，\(k_t\) 判断一下就好了，就能转化为 \(L_b\) 更小的一个子问题。

一种递归，我们可以先判断 \(L_b=\max_{i=1}^{n}(k_i+i-1)\) 是否有解，若无解就考虑 \(L_b=\max_{i=1}^{n} (k_i+i)\)。

我们需要预处理 \(a_i\) 的所有后缀的排名，每次查询区间 \(\max\)，加入删除支持区间加，还要知道每个数第二个 \(1\) 对应的后缀。

时间复杂度 \(\mathcal O(\sum L_i\log (\sum L_i))\)。

若 \(h=h_0\) 失败，由于 \(k_t-1=h_0'\ge k_{t'}\)，最多递归 \(\mathcal O(k_t)\) 次，然后移除 \(k_t\)。

所以我们统计递归失败的总复杂度，即左右儿子都不合法的时间复杂度，而如果 \(h_0\) 失败，会先花费 \(\mathcal O(k_t)\)，然后 \(t\) 这个串直接消失，所以左右儿子都不合法的每一个串都是不同的，太nb了，复杂度得证。！！

336.P10573 [JRKSJ R8] C0mp0nents

很妙的题。

可以想到将 \(\bmod k\) 同余的点和边一起处理，转化为 \(k=1\) 的情况。

思考这个转化的过程，“感染”，某个 \(x\) 与 \(x+1\) 相邻，那么 \(x\) 变为 \(x+1\)，然后这个联通块与 \(x+2\) 相邻，再将 \(x+2\) 加入联通块。

反过来同理，感染的过程可以分成两个部分，\(<s\) 的变为 \(s\)，大于 \(s\) 的变为 \(s\)，分别独立。

以从小往大染色为例，考虑找到若干极大关系对 \((x,y)\)，使得从 \(x\) 开始染最大可以染到 \(y\)，若两个关系对有交，可以合并成更大的关系对，于是 \(1\sim n\) 可以转化为若干极大关系对 \((l1_i,r1_i)\)。

同理从大到小处理出极大关系对 \((l2_i,r2_i)\)。

找到 \(l1_i\le s\le r1_i\)，\(l2_j\le s \le r2_j\)，记 \(L=l1_i,R=r2_j\)。

• 若 \(L<s<R\)，则答案为 \(R-L+1\)；
• \(L=s=R\)，则答案为 \(1\)；
• 若 \(L=s<R\)，这个情况比较特殊，将 \([s,R]\) 的点全部变为 \(s\)，那么 \([l1_{i-1},r1_{i-1}]\) 的点，先变为 \(s-1\)，可能可以与 \([s,R]\) 合并，判断 \([l1_{i-1},r1_{i-1}]\) 与 \([s,R]\) 是否有连边即可；
• 若 \(L<s=R\)，同理。

判断可以二维数点做，也可以直接暴力（？？？），好像说复杂度是对的。！！

337.P10861 [HBCPC2024] MACARON Likes Happy Endings

一看就是个划分序列问题，一看就满足四边形不等式，于是有决策单调性。

！！！注意，对每一维 \(k-1\to k\) 进行分治！！！即可，是对的。

记录一种反四边形不等式

即包含优于交叉，则每个决策点只会被之前的决策点反超。

https://www.cnblogs.com/Jue-Fan/articles/18116228#概述另一种凸优化

用二分栈优化，栈内存最优决策点。

若次栈顶超过栈顶的时间 \(\le\) 栈顶超过 \(i\) 的时间，那么弹出栈顶。

加入决策点 \(i\)。

如果次栈顶超过栈顶的时间 \(\le p_i\)，那么一直弹出栈顶。

“二分栈的写法需要注意！！”

\(w(l,r),w2(l,r)\) 满足四边形不等式，那么 \(a\cdot w(l,r)+b\cdot w2(l,r)\) 也满足。

注意，分治只能解决离线的决策单调性！！！

不过现在还没弄清楚决策点的顺序，每个决策点只会被之前的决策点反超，是什么意思？？》？？？

哦，好像懂了。

设 \(f_i\) 的最优决策点是 \(s_i\)，那么后续点的最优决策点不可能出现在 \((s_i,i)\)。

338.P5244 [USACO19FEB] Mowing Mischief P

考虑转化为一维问题来做，相当于价值最小的最长上升子序列。

我们记点 \(i\) 的类型为以 \(i\) 结尾的最长上升子序列长度，则关于价值的转移发生在相邻两个类型中，且满足二维偏序。

注意到同一类型中，当 \(x\) 单增时，\(y\) 单减，则满足二维偏序的是一段区间。

考虑权值函数，并不能斜率优化，考虑决策单调性，发现是反四边形不等式，但是每个点有维度的转移限制。

相邻两个类型转移时，考虑将前者插入线段树区间（后者对应的区间）上，注意到此时并没有每个点需要转移到后面的点的限制（因为这两者已经是不同类了），所以可以直接分治，具有决策单调性，\(i<j,p_i\ge p_j\)。