XYD 7.25 记录

· · 个人记录

今天是精品题单。

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

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

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

i<j \vee(a_i+a_j)(a_i^2+a_j^2)\equiv k\pmod{p}

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

(a_i^4-a_j^4)\equiv ka_i-ka_j\pmod{p}\\ a_i^4-ka_i\equiv a_j^4-ka_j\pmod{p}

于是我们就构造出两个同构的式子，直接拿个桶来装然后边扫边统计就行了，复杂度 \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 的方案数。

g_{i,j}=g_{i-1,j-m}+g_{i,j-i}

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

\sum\limits_{i=0}^{n}(dp_{m-1,i}\times\sum\limits_{j=0}^{m}{g_{j,n-i}})

三部分复杂度都是 \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 就行了。

晚上来学多项式。