XYD 7.25 记录

今天是精品题单。

早上过来把几道简单题都写了

AGC055_b Ad-hoc，昨天晚上回去想了一些，觉得可能是区间之间不会影响，所以说每个区间单独考虑一下。今天来发现任何形如 XABC 的串都可以变成 ABCX 这样的串，对于 BCA 和 CAB 也是同理，所以直接把所有这样的串删掉然后判断是不是相等就行了，复杂度 $\mathcal{O}(n)$ 太逆天了。

CF1188B 一道数学题，要你数区间满足

的有序对数量，$k,p$ 给定。因为题目保证 $a_i< p$ 所以 $(a_i-a_j,p)=1$，直接两边同时乘上变成

于是我们就构造出两个同构的式子，直接拿个桶来装然后边扫边统计就行了，复杂度 $\mathcal{O}(n)$。

ARC145_d Ad-hoc，我一开始想的是从差开始考虑，每次加入新的差值，保证不能用前面已有的若干差值和构造出来，但是这样每次插入新的差值然后暴力更新后面用不了的值是 $\mathcal{O}(n^2)$ 的，没敢写，题目给的 $n\le 10^4$，后来 GYC 告诉我他 $\mathcal{O}(n^2)$ 过了，就跑了 46 ms。有一种 $\mathcal{O}(n)$ 的做法是考虑三进制，因为你题目是要保证 $\forall i<j<k,a_j-a_i\neq a_k-a_j$ 变换一下就是 $a_i+a_k\neq 2a_j$ ，如果 $a_i,a_j,a_k$ 在三进制下都只有 $0,1$ 组成那么加起来一会的数一定会有 $1$ 因为 $a_i\neq a_j$ 则必定存在 $x$ 使得 $a_i,a_j$ 第 $x$ 位一个为 $1$ ，另一个为 $0$。而 $2a_j$ 因为只有 $0,1$ 组成所以两倍只有 $0,2$，所以左右两边一定不等，这样我们很容易能满足 3 个条件，对于 $\sum\limits_{s\in S}s=m$ 这个条件我们可以考虑给这个序列整体加上 $\lfloor \frac{\Delta}{n} \rfloor$ 这显然对结果无影响，除不尽的问题可以考虑把所有数最后一位空出来，然后随机选择 $\Delta\mod n$ 位末尾加上 $1$，注意这里应该先补全除不尽的部分再整体加，否则整体加的时候会把末尾的 $0$ 改变。时间复杂度 $\mathcal{O}(n\log n)$，这题复杂度看起来正常一点（确信

P6189 完全背包可以拿 70pts，据说可以卡到 80pts，然而我完全背包看了好久才看出来，已经降智了。然后有一种解法是数论分块，对于 $\le \sqrt{n}=m$ 的数字直接完全背包，复杂度 $\mathcal{O}(n\sqrt n)$，然后对于大于的情况换一种方式计算，令 $g_{i,j}$ 表示选了 $i$ 个总和为 $j$ 的方案数。

因为 $\geq\sqrt n$ 的数字最多选 $\sqrt n$ 个，所以 $i$ 的上限是 $\sqrt n$ 所以复杂度 $\mathcal{O}(n\sqrt n)$。统计就是

三部分复杂度都是 $\mathcal{O}{n\sqrt n}$。

中午回来在学 ODT，珂朵莉是我唯一完整看过的日漫，但是一直没学珂朵莉树，今天讨论昨天 T1 的时候他们提到珂朵莉树，我就去浅浅看了下发现不难，所以中午学一下，中午代码是写完了，但不得不说这是真容易 RE，中间 RE 两次，一次是运算符重载反了，导致 t.erase(l, r); 实际上是 t.erase(r, l); 直接就爆炸了，还有一次就是因为边界了。交上去 WA 好几发都是因为某个神秘的地方没开 long long，找了好久找到，lxl 这个基于随机的真的很乱搞。

AGC066_c Ad-hoc 一道黑题，充要条件注意到之后就和那些 AT 特别喜欢出的蓝色 Ad-hoc 一样，就是只要保证首位至少有一个 B，然后中间 A 等于 B 的两倍就能保证中间能被消完。然后数一下最少会留下来多少做一个 dp 就行了。

晚上来学多项式。