Source
A 绝境
B 命运
题意补充:注意可以有重边,本来以为是平面图所以可以用欧拉定理保证复杂度
$$
\\显然dp(i,x1)表示确定了前i-1个,i-1和i之间的边,上面有x1条,下面有p_{i-1}-x1条的方案数
\\考虑dp(i,x1)转移到dp(i+1,x1-a1+b1),其中a为结束多少条线,b为开始,转移系数=1,考虑转移条件
\\x1+x2=p_{i-1},x1+x2-a1-a2+b1+b2=p_i,a1+a2+b1+b2=d_i(可见若lim=p_i-p_{i-1}+d_i为奇数就无解)
\\不等式有0 \le a1 \le x1,0 \le a2 \le x2,b1,b2 \ge 0,初中知识解方程得出下列转移条件
\\max(0,lim-p_{i-1}+x1) \le a1 \le min(x1,lim/2),0 \le b1 \le\frac{p_i-p_{i-1}+d_i}{2}
$$
具体怎么写可以先写暴力:
1 | int n=qread(),sm=0;fo(i,1,n) d[i]=qread(),sm+=d[i];fo(i,1,n-1) p[i]=qread(); |
然后一维差分:
1 | fo(a1,max(lim/2-p[i-1]+x1,0),min(x1,lim/2)) |
发现可以二维差分,于是就是$O(n^2)$
C 终焉
题意:给出一棵n个点的树,每个点有个20位的二进制数a,一条边是好的充要条件是$a_x\&a_y>0$,每次修改一个点的a,并输出n-好边数,$n,q \le 1e5$
显然每次统计一个点周围有多少条不好的边即$a_x \& a_y=0即a_y \subseteq (a_x的补集)$会好做,先假设每个点需要提供给别人的信息已经有了要怎么回答询问,那么现在的复杂度就是$2^{cnt_0}$
这种时候如果能找出一个复杂度为$2^{cnt_1}$的做法,那么这道题就能解决了,然后我想了半天并不会
这种找子集的时候,有一种推广性很好的做法(感觉做题多的应该都知道),那就是将二进制状态切半,咋一看好像没啥区别,具体说做法给大家感受一下:已知$f(x,S1,S2)$表示节点x相邻的节点,前半恰是S1,后半的超集为S2,那么回答询问就是枚举第一部分然后去查表,$O(2^{m/2})$
然后这个东西的维护,直接想要考虑度数(根号分治啥的可能可以?),但注意到是棵树只考虑存孩子,父亲的那条边好不好直接判就行了,也是$O(2^{m/2})$
现在就是空间比较爆炸,是$O(n2^m)$的,但很明显有用的地方不会超过时间复杂度,写个hash表就行了
虽然不开c++11但可以用些技巧(见stl一章)开unordered,但这玩意很慢,本机9s,然后我随便写了个hash表跑了12s……
其实很明显d小的时候枚举度数会快一点,但考虑到不影响时间复杂度就没咋想,但其实取$d=2^{m/2}$的话只有$n/d$个点是要开表的,于是我们就能愉快地使用数组了,code