我们在夏日编织花冠

luogu2048 [NOI2010]超级钢琴

要是今年 NOI 也是这种水水的题就好了 qwq。

luogu2048 [NOI2010]超级钢琴

luogu1712 [NOI2016]区间

先按照长度降序排序,然后一条条加入线段。当发现某个点被覆盖超过 $m$ 次后就开始不断统计答案并由长到短地删掉加了的线段(像是尺取法)直到没有超过 $m$ 次的。正确性显然。

luogu1712 [NOI2016]区间

loj2303 「NOI2017」蚯蚓排队

先想出一个暴力,拿链表模拟蚯蚓的 merge 和 split,每次操作把受影响的长度为 $50$ 以内的子串扔进哈希表计数。查询的时候就是直接查哈希表乘起来。复杂度 $mk^2+s$。

loj2303 「NOI2017」蚯蚓排队

loj2302 「NOI2017」整数

首先 $n\log^2 n$ 的暴力还是很好想的,二进制分解 $a$ 然后加加减减就行了。退位进位的 $1$ 用线段树找。

然后压个 $30$ 位就好了。

loj2302 「NOI2017」整数

loj2007 「SCOI2015」国旗计划

先拆环成链每个人复制一遍(因为可能有跨越 $m$ 的人)。

然后可以发现,每个人的下一个战士都是固定的。ST 表搞出来优化暴力覆盖就行了。

loj2007 「SCOI2015」国旗计划

luogu4103 [HEOI2014]大工程

先建虚树,然后树形 dp 一下就好了。转移看代码吧。

luogu4103 [HEOI2014]大工程

虚树讲解和 luogu2495 [SDOI2011]消耗战

虚树挺劲爆的,得学一学……

虚树讲解和 luogu2495 [SDOI2011]消耗战

bzoj3514 Codechef MARCH14 GERALD07加强版

ref
这题好神啊……主要要有一个思想,强制在线,又是区间,想着用主席树,搞出一个能代表每个边的东西来。我反正想不到>_<。

bzoj3514 Codechef MARCH14 GERALD07加强版