luogu1712 [NOI2016]区间
先按照长度降序排序,然后一条条加入线段。当发现某个点被覆盖超过 $m$ 次后就开始不断统计答案并由长到短地删掉加了的线段(像是尺取法)直到没有超过 $m$ 次的。正确性显然。
我们在夏日编织花冠
先按照长度降序排序,然后一条条加入线段。当发现某个点被覆盖超过 $m$ 次后就开始不断统计答案并由长到短地删掉加了的线段(像是尺取法)直到没有超过 $m$ 次的。正确性显然。
推公式推个爽。
推公式推个爽。
第一问答案显然是 $1$,考虑一下 $\mu$ 的计算过程就会发现平方数的 $\mu$ 是 $0$……。
$\varphi(i^2)=i \varphi(i)$ 这个也很显然,考虑一下欧拉函数的计算式就知道是对的了。
真鬼畜啊这蛐蛐题……
我们惊喜地发现傻叉哈希能拿 $95$ 分,那就不要想正解了,这就是 A 了。
贪心神题……
先想出一个暴力,拿链表模拟蚯蚓的 merge 和 split,每次操作把受影响的长度为 $50$ 以内的子串扔进哈希表计数。查询的时候就是直接查哈希表乘起来。复杂度 $mk^2+s$。