Category Archives: 2019.3

ZJOI Round1

Cptraser/ 三月 27, 2019/ 2019.3/ 0 comments

Day1 早上-镇海中学罗煜翔 清华集训2016如何优雅地求和 基础期望DP练习题 卷积? 听得一脸懵逼。 下午-温州中学孔朝哲 RRR-WorldFinal2017 考虑没有变异的情况,那么肯定有唯一前驱。 ChipGame-CF1033G 枚举a+b分类讨论 MatchAreNotaChild’s

Read More

LCT刷题记录

Cptraser/ 三月 21, 2019/ 2019.3/ 0 comments

【模板】Link Cut Tree (动态树) #include <cstdio> #include <cctype> #include <algorithm> using namespace std; char tc(){static char tr[10000],*A=tr

Read More

[NTT]LOJ#6261一个人的高三楼

Cptraser/ 三月 19, 2019/ 2019.3/ 0 comments

题面传送门 对原数列建生成函数: 求一次前缀和相当于将卷上生成函数 相当于我们要求 直接快速幂会,但有一些奇妙的性质: 的意义是选个自然数使得和为 通过插板法得知 那么我们直接即可。 #include <cstdio> #include <algorithm> using namespac

Read More

可持久化01trie

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

可持久化01trie 类似主席树,在已有的基础上修改,空间。 Thu Summer Camp 2015异或运算 考虑到比较大,对建可持久化01trie然后最多同时查询次(同一棵01trie)。 #pragma GCC optimize(2) #include <cstdio> using namesp

Read More

斯坦纳树

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

        第一个是从子集转移,第二个类似松弛操作,用即可。 WC2008游览计划 // luogu-judger-enable-o2 #include <queue> #include <cstdio> #include <cstring

Read More

[线性基]albus就是要第一个出场

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门 这题需要解决两个问题,一个是在线性基里排第几,一个是每个数出现了几次。 对于问题①,我们已经知道了如何求出去重后B数组的第k小,而这题其实是反过来的给你一个数q,求出它是第几小。 步骤: 1. 求出线性基后线性基内所有元素从小到大排序,并且只保留最高位 2. 之后将q二进制拆分,初始化rank=0,如

Read More

[线性基]WC2011最大XOR和路径

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门 考虑最终的答案一定是一条的链和若干个环组成。 所以预处理出所有环的放入线性基中。 考虑下面两种情况: 对答案有贡献的环需要从路径上走过去再走回来,那么过程中的影响会因为来回走而抵消。 度过存在另一条更优秀的的路径,那么这条路径和我们随意选择的路径构成了环,那么它一定会被放在线性基内。 #include

Read More

[高斯消元]HNOI2013游走

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门 将题目中的边的期望转化为点的期望。 设表示被经过的期望。那么:         号点比较特殊,因为在出发时它是起点,就已经经过了一次。 号点比较特殊,因为游走到号点就结束了,所以转移是不可以从点转移过来的。 #include <cstdio> #in

Read More

[高斯消元]HNOI2011XOR和路径

Cptraser/ 三月 18, 2019/ 2019.3/ 0 comments

题面传送门 按每一位考虑期望,设表示这一位的期望,那么:         将度数移到左边然后高斯消元即可。 #include <cstdio> #include <cstring> #include <algorithm> using n

Read More