# 日常摸鱼

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

# 2022

# 2022 - 01

  • 洛谷 P2572 [SCOI2010] 序列操作

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

  • 洛谷 P2486 [SDOI2011] 染色

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

  • 洛谷 P3455 [POI2007] ZAP-Queries

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

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

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

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

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

  • DTOJ #5700. 可怜的木偶

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

  • DTOJ #4996. 数学作业

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

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

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

  • DTOJ #4996. 数学作业

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

  • 洛谷 P3768 简单的数学题

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

  • DTOJ #4704. 求和

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

更新于 阅读次数