按解决顺序排列
目录F
二分答案ans,放最小的前ans个bi(变成必须放完)
因为bi=2^k,所以小的放了可能会拆散大的空间,大的把小的地方占了的话小的可以塞其他地方,所以先放大的
然后暴力能放则放,最多log次指针回到开头
所以一次求解O(nlogn),总复杂度log^2
A
模拟,暴力枚举暴力异或
注意X串要多留k-1位
I
把限制Pa!=b变成叉掉点(a,b),画一下发现问题等于求多少个内部没有叉的合法矩形 (a~b,L~R)
经典问题(疑似),枚举R,维护每个点(x,R)左边的最大长度,那么一对a0,b0对应 min L[x] (x in (a0,b0)) 个 (a0~b0,某L,R) 的矩形,单调栈维护,在弹掉时可以求出跨过某x的方案
D
枚举r,倒着枚举l,依次把a[l]在权值数轴上点亮
然后经典问题维护连续区间个数,个数=点-边,边就是相邻两个都点亮了的,个数<=2合法
(tips:可以做到O(nlogn)……)
H
题意:每次把当前图的x->y->z->...->x且权值和<=3的环的权值变为0,然后持续操作直到不能变为止,求最短路
一开始会把三元环给边0,然后 三元环点->x->(y)->三元环点 的点变0,如此反复
可以发现权值变为0等于缩点,缩得的团内的边都是0,团外边位1,现在要模拟缩点的过程
记点x的入边对应团集合为In[x],出为Out[x],那么 团内点->x->(y)->团内点 的判定条件为 In[x]&Out[y]!=0,枚举x,y(若没有y则会枚举y=团内点,也可以判到),bitset优化判断即可
一共缩n次,每次枚举m条边,check复杂度n/ω,所以总复杂度O(n^2m/ω)
E
神题,我懂得欣赏
https://www.cnblogs.com/gmh77/p/18550020
C
(咕)