111
jyh8221
·
·
个人记录
1018
t1
【模板】单调栈
处理每个点贡献的区间长度，差分一下即可
t2
考虑对a_i建虚点，因为2^{20} \approx 10^6 可以把不用的也建了。\
注意到如果 x \operatorname{and} y = y 且 y \operatorname{and} z = z，x \operatorname{and} z = z。\
考虑对x和x \operatorname{or} y \ (\ \operatorname{popcount}(y) = 1 \ \text{且} \ \operatorname{popcount}(x \operatorname{xor}\ (x \operatorname{or} y)))=1的点建边。\
虚点和真正的点连w=0.5的边。\
注意a_i可能\ =0 。
t3
神秘计数，不会。
t4
大佬用 min25 筛，我不会。
xz001有一个神秘的做法。\
枚举较小的约数，贡献为\gcd(x,y) = 1\ (x\le y \le n/x)\
考虑解\gcd(x,y) = 1\ (y \le x)\
因为前7个质因数的乘积\le 10^6，分解质因数容斥即可。
模版练习
t1
类似字符串哈希，考虑在\bmod\ p意义下解方程。
t2
注意到m \le 2k \le 22 ,2^m \le 5\times 10^6 ，爆搜即可。
t3
【模板】manacher\
没啥好说的，求完回文半径后就很简单了，二分就可以。
div4
t4
先建trie树转化为树上问题。
就转化成了p3354。
设dp_{i,j,k,2}表示点i用的按钮是j,i的子树内有k个按钮，i有/没有按钮的权值。
显然是一个树上背包。
t1
开3个pq分别存每个点的3个值。
把目前的最大值pop出来
如果一个点有两个值相同，那么这个点就不能选，大标记删除。
找到第一个没被标记的点对就是答案。