AC自动机 这些东西还是交给wiki 模板 #include<cstdio> #include<iostream> #include<cstring> #include<iomanip> #include<cmath> #include<stack> #include<q…

Jisoo 13秒，跑，往死里跑 犹豫就会wa #include<cstdio> #include<iostream> #include<cstring> #include<iomanip> #include<cmath> #include<stack> #include<…

Rose 非常有趣的构造题 看到这奇怪的数据范围就只要要依据这个搞事情 $f(x+10^{18})=f(x)+1$推而广之 $sum_{a-p}^{10^{18+a-p-1}}equiv(modquad a)$ 且有$sum_{i=1}^{10^{18}-1}f(i)equiv p(modquad a)$ 然后这个p可以推算得$81*10^{18}…

Rose 不是一般的01背包 因为有后效性，也就是因为重量可以是负的（钩子越放越多） 为了抵消这种影响，按照钩子数量从大到小排序 #include<cstdio> #include<iostream> #include<cstring> #include<iomanip> #include<cm…

Jennie 反悔贪心 显然要把逃生能力弱的先送出去，也就是排个序。 这时候剩下的怎么办，万一有一些手长腿短的怎么办 先假设所有小矮人站成一排，然后一个个逃。 逃无可逃时候，看看把已经逃出去的中腿最长的拉下来会不会答案更优。 #include<cstdio> #include<iostream> #include<cs…

Jennie 分块，对于每一个块，排个序 就可以了 #include<cstdio> #include<iostream> #include<cstring> #include<iomanip> #include<cmath> #include<stack> #include&…

Jinnie 看到莫名其妙的异或题，应该考虑按照位数处理。 这样我们分别考虑每一位的答案，需要先取模。 排序，让序列有了单调性，并且可以观察到，对于第k位只有两个数的和属于 $[2^k,2^{k+1}-1]cap[2^{k+1}+2^k,2^{k+2}-2]$才行 最后的右边界是什么东西？我们取模了啊. 双指针解决。 #include<cst…

Jisoo 众所周知，这个式子就是$sum_{i=1}^n(k-i*lfloorfrac{k}{i}rfloor)$ 也就是$nk-sum_{i-1}^n(ilfloorfrac{k}{i}rfloor)$ 右边的东西用数论分块+等差数列搞一下就可以了 数论分块的每一块的右边界是$lfloorfrac{k}{lfloorfrac{k}{i}rflo…

可持久化线段树 如果我们要维护一个可持续的，支持查询历史版本的数组该怎么做 给每一个版本建立一颗线段树？那太占空间了。 我们可以不同版本公用一些节点，对于每个版本，只把和上一个版本不一样的部分建立线段树的新节点。这样我们就有了可持久化线段树。 [Lisa]() 需要的前置知识：动态开点。 依照上面的思想，这个题只有单点修改和单点查询，很容易解决。 …

左偏树 一种可以合并的堆 前置知识 dist 对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 为 ，一个不是外节点的节点 为其到子树中最近的外节点的距离加一。空节点的dist为0。 那么左偏树就是一颗满足堆的性质的二叉树，它的左儿子的dist大于等于右儿子的 核心 核心操作是合并，合并到时候，要满足堆得性质，对于小根…