2024.05 做题笔记

P6617

由于 \(w\) 是固定的，容易想到去维护前驱。具体而言，对于每个 \(i\)，维护 \(i\) 之前第一个 \(w-a_i\)，这样可以解决不带修的部分分。

发现带修就寄了！因为一次可能修改 \(\mathcal O(n)\) 个位置的前驱。但是考虑到我们只需要判断是否存在，因此如果 \(a_i\) 前的第一个 \(w-a_i\) 为 \(a_j\)，且 \(j,i\) 之间有 \(a_i\)，那么 \((j,i)\) 这个 pair 显然不优。我们只需要维护所有支配点对，这时候每次修改只会影响 \(\mathcal O(1)\) 个位置，用线段树 + set 维护，时间复杂度 \(\mathcal O(n\log n)\)。

P5179

神秘题。

容易证明最小化分母等价于最小化分子。

当 \(\frac{a}{b}<1<\frac{c}{d}\) 时肯定取 \(\frac{1}{1}\)，当两个数有共同整数部分的时候可以扣除，这时候 \(\frac{a}{b},\frac{c}{d}<1\)。我们考虑翻转，即求 \(\frac{d}{c}<\frac{v}{u}<\frac{b}{a}\)，继续递归即可，复杂度同欧几里得 gcd，为 \(\mathcal O(\log n)\)。

P6060

观察到 \(D(n^k)\) 是关于 \(k\) 的 \(\omega(n)\) 次多项式。求出多项式的前缀和，每次询问直接代入求值即可。复杂度 \(\mathcal O(n\omega(n)+T\omega(n))\)。

ABC313G

所有的结局序列一定可以通过先做若干次全局 \(-1\)，再做若干次全局 \(+1\) 得到。那么我们将原序列进行排序，枚举最终消到了哪个 \(a_i\)，最后求和形如 \(\sum\limits_{i=1}^{n}\lfloor\frac{ai+b}{c}\rfloor\)，直接万能欧几里得即可。

AGC003D

如果质因数分解完成了，问题容易解决：只需要将每个质因子的次幂对 \(3\) 取模，那么每个数都有一个对应的不能选的数，用一个 map 统计即可，需要特判完全立方数不能同时选。如果用 Pollard-Rho 可以做到 \(\mathcal O(nV^{\frac{1}{4}}+n\log n)\)。

但是 PR 有点麻烦。我们考虑三次根号分治，对于 \(\le V^{\frac{1}{3}}\) 的质因子，直接暴力筛出来，剩下的只可能形如 \(1,p,p^2,pq\)（\(p,q\) 为质数），只需要判断这个剩下的部分是不是完全平方即可，因为无论是 \(p\) 还是 \(pq\) 都只需要乘上剩余部分的平方。时间复杂度 \(\mathcal O(n\pi(V^{1}{3})+n\log n)\)。

ABC240Ex

考虑一组合法的解长成什么样。观察相邻的串的长度，如果上一个选的长度为 \(l\)，那么下一个选的长度不可能超过 \(l+1\)（如果超过 \(l+1\)，那么把最后一个字符截掉肯定不劣），因此所有串长不超过 \(\mathcal O(\sqrt n)\)。直接全部插入 trie 树，按照 trie 树的顺序做二维偏序即可。时间复杂度 \(\mathcal O(n\sqrt n\log n)\)。

ABC240F

枚举整段的取到了哪里，设为 \(i\)。那么考虑 \(i+1\) 段内部的贡献，设前 \(i\) 段前缀和为 \(s\)，那么选出 \(c\) 个会贡献 \(s+\frac{c(c+1)}{2}x_{i+1}\)，可以直接三分求答案。时间复杂度 \(\mathcal O(n\log n)\)。