# 日常摸鱼

记录一些刷的水题以及伞兵错误。

# 2022

# 2022 - 01

• 洛谷 P2572 [SCOI2010] 序列操作

原题。线段树水题，首先肯定要维护 $1$ 的状态。对于取反的操作，只要再维护 $0$ 的状态就可以了，提交记录。

• 洛谷 P2486 [SDOI2011] 染色

原题。树剖模板，直接维护区间左端点、右端点和颜色段数即可，提交记录。
不过一开始写错了。对于查询，需要 $u$ 和 $v$ 两个点一起往上爬。我的维护方式是 resu 表示 $u\to \text{LCA}$ 的路径， resv 表示 $\text{LCA} \to v$ 的路径。在合并 resu 时，应该把每次查询得到的路径左右端点取反（即 query(dfn[top[u]], dfn[u]).revese() ）。

• 洛谷 P3455 [POI2007] ZAP-Queries

原题。莫反水题，提交记录。
不过数论分块写错了所以说数论这种东西很容易忘啊 kora。然后加的时候忘记开 long long （强制类型转换）。

• 洛谷 P1829 [国家集训队] Crash 的数字表格 / JZPTAB

原题。莫反应用题，提交记录。
推式子之后分析了一下，认为 $O(n\log n)$ 能过，没必要像题解里那样优化。但自信就会白给，于是我还是老老实实地做了两边数论分块，一个 $O(\sqrt n)$，总和 $O(n)$。我曾在极度愤怒的情况下 define int long long ，不过还是挂了。最后发现是因为在 debug 的时候 const int top = 10 了。

• 洛谷 P1505 [国家集训队] 旅游

原题。树剖水题，一遍秒了。提交记录。

• DTOJ #5700. 可怜的木偶

原题。莫反，提交记录。注意到最后的答案其实就是 $\sum_{x_1=1}^k \cdots \sum_{x_n=1}^k \gcd(x_1, \cdots, x_n)$ ，直接反演就行。一遍秒了。

• DTOJ #4996. 数学作业

原题。莫反，提交记录。挺套路的，就是老推错。变换枚举 $\mu(x)$ 的时候老容易弄错。

• 洛谷 P4213 【模板】杜教筛（Sum）/ DTOJ #4658. sum

DTOJ / 洛谷。模板，洛谷提交记录 / DTOJ 提交记录。分块预处理分大了，偏小一点可能会更快，$5\times10^6$ 之类的。非常恶心地整型溢出了，简直就是绝世好题：

• DTOJ #4996. 数学作业

原题。莫反，提交记录。系数上的次方非常的缭乱，毒瘤。

• 洛谷 P3768 简单的数学题

原题。杜教筛，提交记录。非常恶心地整型溢出了。

• DTOJ #4704. 求和

原题。杜教筛，提交记录。式子看花了，迪利克雷卷积看成直接相乘了，还好手算了下。还是分块的问题，分的块有点偏大，$10^6$ 会更好。