A. marshland
考试时想到了网络流，然而不会建图，就死了。
正解是最大费用可行流。
比较容易想到的是将每个点拆为两个点，
s连没有危险值的入点，
没有危险值的入点连有危险值的入点，入点出点之间限流有费用，
出点再连没有危险值的出点，这些出点连向t。
不断跑spfa，通过有流量的边，记录下前趋。
将前趋的边的流量改变，EK算法。
B. party
因为只有单向边，达成尽快到齐的条件是，终点为c个点的lca。
m的范围比较小，于是可以用bitset维护。
比较容易想到了在倍增求lca的同时维护bitset，取并集。
然而空间刚好卡到600多MB，时间也死了。
树链剖分。
空间返回到O(n*m)级别，比倍增少一个log。
问题转化为每个人从自己所有集合中选择相同数量的最多元素，要求互不相同。
网络流+二分可行。
源点向每个人建流量为mid的边，每个人向它包含元素建流量为1的边，每个元素向汇点建流量为1的边。
左部点流满就表示可行。
如果将每个人拆为若干个点，问题其实是求二分图完美匹配。
于是想到霍尔定理（？？？）：
一个二分图 G 存在完美匹配, 当且仅当 X 中的任意 k 个点都至少与 Y 中的 k 个点邻接. 二分答案，枚举$2^{c*mid}$显然是可行的，然而复杂度真的死了。
考虑不同的左部点只有c个，枚举$2^c$，
1表示考虑这个人。
将答案与 所有考虑的人的bitset并集中1的个数除以考虑的人数 取min。
总复杂度为$O(\frac{qlog^2nm}{32})$。
考虑到没有修改操作，直接维护每个点到重链顶的bitset，可以将复杂度降低一个$logn$。
推荐$unsigned long long$手写$bitset$，
主要是可以将$O(n)$的$count$函数通过预处理变成$O(\frac{n}{32})$，
或者继续循环展开将所有操作改为$O(1)$。
1 struct bitset{ 2 #define lowbit(x) (x&-x) 3 unsigned long long bit[16]; 4 inline void reset(){ 5 bit[0]=0; 6 bit[1]=0; 7 bit[2]=0; 8 bit[3]=0; 9 bit[4]=0; 10 bit[5]=0; 11 bit[6]=0; 12 bit[7]=0; 13 bit[8]=0; 14 bit[9]=0; 15 bit[10]=0; 16 bit[11]=0; 17 bit[12]=0; 18 bit[13]=0; 19 bit[14]=0; 20 bit[15]=0; 21 } 22 inline friend void operator |=(bitset &a,const bitset &b){ 23 a.bit[0]|=b.bit[0]; 24 a.bit[1]|=b.bit[1]; 25 a.bit[2]|=b.bit[2]; 26 a.bit[3]|=b.bit[3]; 27 a.bit[4]|=b.bit[4]; 28 a.bit[5]|=b.bit[5]; 29 a.bit[6]|=b.bit[6]; 30 a.bit[7]|=b.bit[7]; 31 a.bit[8]|=b.bit[8]; 32 a.bit[9]|=b.bit[9]; 33 a.bit[10]|=b.bit[10]; 34 a.bit[11]|=b.bit[11]; 35 a.bit[12]|=b.bit[12]; 36 a.bit[13]|=b.bit[13]; 37 a.bit[14]|=b.bit[14]; 38 a.bit[15]|=b.bit[15]; 39 } 40 inline friend bitset operator |(const bitset &a,const bitset &b){ 41 bitset ans; 42 ans.bit[0]=a.bit[0]|b.bit[0]; 43 ans.bit[1]=a.bit[1]|b.bit[1]; 44 ans.bit[2]=a.bit[2]|b.bit[2]; 45 ans.bit[3]=a.bit[3]|b.bit[3]; 46 ans.bit[4]=a.bit[4]|b.bit[4]; 47 ans.bit[5]=a.bit[5]|b.bit[5]; 48 ans.bit[6]=a.bit[6]|b.bit[6]; 49 ans.bit[7]=a.bit[7]|b.bit[7]; 50 ans.bit[8]=a.bit[8]|b.bit[8]; 51 ans.bit[9]=a.bit[9]|b.bit[9]; 52 ans.bit[10]=a.bit[10]|b.bit[10]; 53 ans.bit[11]=a.bit[11]|b.bit[11]; 54 ans.bit[12]=a.bit[12]|b.bit[12]; 55 ans.bit[13]=a.bit[13]|b.bit[13]; 56 ans.bit[14]=a.bit[14]|b.bit[14]; 57 ans.bit[15]=a.bit[15]|b.bit[15]; 58 return ans; 59 } 60 inline void set(const int x){ 61 bit[x>>6]|=(unsigned long long)1<<(x&63); 62 } 63 inline int count(){ 64 register int cnt=0; 65 cnt+=ct[bit[0]&65535]+ct[(bit[0]>>16)&65535]+ct[(bit[0]>>32)&65535]+ct[(bit[0]>>48)&65535]; 66 cnt+=ct[bit[1]&65535]+ct[(bit[1]>>16)&65535]+ct[(bit[1]>>32)&65535]+ct[(bit[1]>>48)&65535]; 67 cnt+=ct[bit[2]&65535]+ct[(bit[2]>>16)&65535]+ct[(bit[2]>>32)&65535]+ct[(bit[2]>>48)&65535]; 68 cnt+=ct[bit[3]&65535]+ct[(bit[3]>>16)&65535]+ct[(bit[3]>>32)&65535]+ct[(bit[3]>>48)&65535]; 69 cnt+=ct[bit[4]&65535]+ct[(bit[4]>>16)&65535]+ct[(bit[4]>>32)&65535]+ct[(bit[4]>>48)&65535]; 70 cnt+=ct[bit[5]&65535]+ct[(bit[5]>>16)&65535]+ct[(bit[5]>>32)&65535]+ct[(bit[5]>>48)&65535]; 71 cnt+=ct[bit[6]&65535]+ct[(bit[6]>>16)&65535]+ct[(bit[6]>>32)&65535]+ct[(bit[6]>>48)&65535]; 72 cnt+=ct[bit[7]&65535]+ct[(bit[7]>>16)&65535]+ct[(bit[7]>>32)&65535]+ct[(bit[7]>>48)&65535]; 73 cnt+=ct[bit[8]&65535]+ct[(bit[8]>>16)&65535]+ct[(bit[8]>>32)&65535]+ct[(bit[8]>>48)&65535]; 74 cnt+=ct[bit[9]&65535]+ct[(bit[9]>>16)&65535]+ct[(bit[9]>>32)&65535]+ct[(bit[9]>>48)&65535]; 75 cnt+=ct[bit[10]&65535]+ct[(bit[10]>>16)&65535]+ct[(bit[10]>>32)&65535]+ct[(bit[10]>>48)&65535]; 76 cnt+=ct[bit[11]&65535]+ct[(bit[11]>>16)&65535]+ct[(bit[11]>>32)&65535]+ct[(bit[11]>>48)&65535]; 77 cnt+=ct[bit[12]&65535]+ct[(bit[12]>>16)&65535]+ct[(bit[12]>>32)&65535]+ct[(bit[12]>>48)&65535]; 78 cnt+=ct[bit[13]&65535]+ct[(bit[13]>>16)&65535]+ct[(bit[13]>>32)&65535]+ct[(bit[13]>>48)&65535]; 79 cnt+=ct[bit[14]&65535]+ct[(bit[14]>>16)&65535]+ct[(bit[14]>>32)&65535]+ct[(bit[14]>>48)&65535]; 80 cnt+=ct[bit[15]&65535]+ct[(bit[15]>>16)&65535]+ct[(bit[15]>>32)&65535]+ct[(bit[15]>>48)&65535]; 81 return cnt; 82 } 83 };
C. platform
后缀数组。
然而完全忘记了怎么打。
没改到，鸽了。
京公网安备 11010502036488号