Atcoder ARC-150
A - Continuous 1 给定一个长度为 nnn 的只包含0,1,?的字符串,是否只存在一种替换?的方案使得字符串仅有 kkk 个1且所有的 1 在某 ...
Read more
同余最短路
被[国家集训队]墨墨的等式吊打力~ 例题:P3403 跳楼机 给定x,y,z≤105,h≤263−1x,y,z \leq 10^5,h\leq 2^{63} ...
Read more
SAM后缀自动机
在学完 SAM 后的三周,某场CF的E题,结果忘了 SAM 的写法… 本文忽略了复杂度证明,在 OI wiki 上证明的很详细了,这里为对 SAM 的原理的介 ...
Read more
斜率优化
斜率优化可以在动态规划中根据斜率的性质优化时间。 当转移出现ai×bja_i\times b_jai​×bj​的时候,单调队列优化不再适用,就要使用斜率优化。 ...
Read more
NOI2018-你的名字
题意 给定一个文本串sss,若干询问,每次询问给定一个区间[l,r][l,r][l,r]和一个模式串ttt,求 ttt 中不存在于sl...srs_l...s ...
Read more
PKUWC2018-随机游走
传送门 题意 给定一个有根树,qqq次询问,每次询问给定树上点的一个集合SSS,求从根出发随机游走(根视为已经经过),经过SSS的所有点需要的期望次数,模99 ...
Read more
非旋treap
treap是一种弱平衡树,它以用随机创造随机来使自身平衡(头铁随机数)。 treap分为非旋treap(FHQ-treap)和旋转treap,然而非旋treap ...
Read more
Atcoder Ex - 01? Queries
problem 给定字符串 s,si∈{0,1,?}s,s_i \in \{0,1,?\}s,si​∈{0,1,?} , ?可以视为0或1任意一种,若干次单点 ...
Read more
莫比乌斯反演
莫比乌斯函数 设正整数NNN分解质因数的结果为N=p1a1p2a2...pmamN=p_1^{a_1}p_2^{a_2}...p_m^{a_m}N=p1a1​ ...
Read more
NOI2018屠龙勇士
链接 先用multiset(或手写平衡树)预处理出打每条龙用的剑伤害值,记为 BiB_iBi​ 注意:题意意思是只能攻击一个来回 正题 根据题意可以写出方程: ...
Read more