coj模拟赛1Day2

Source

coj模拟赛1Day2

A 绝境

考虑将答案集合分为A——恰覆盖n-1次，B——恰覆盖n次

统计A，枚举是哪个矩形没有覆盖这里，那么就是求其他矩形的并，矩形的并依然是矩形

然后这样每个B会被记录n次，减去n-1次即可

code

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}
$$
具体怎么写可以先写暴力：

int n=qread(),sm=0;fo(i,1,n) d[i]=qread(),sm+=d[i];fo(i,1,n-1) p[i]=qread();
if(d[n]!=p[n-1]){write2(0);continue;}
memset(f,0,sizeof f);f[1][0]=1;
bool tg=0;
fo(i,1,n-1) fo(x1,0,p[i-1]) if(f[i][x1])
{
	int lim=d[i]-p[i]+p[i-1];if(lim&1) tg=1;
	fo(a1,max(lim/2-p[i-1]+x1,0),min(x1,lim/2))
		fo(b1,0,(p[i]-p[i-1]+d[i])/2)
			add(f[i+1][x1-a1+b1],f[i][x1]);
}
if(tg) {write2(0);continue;}
ll ans=0;fo(x1,0,d[n]) add(ans,f[n][x1]);write2(ans);

然后一维差分：

fo(a1,max(lim/2-p[i-1]+x1,0),min(x1,lim/2))
add(f[i+1][x1-a1],f[i][x1]),add(f[i+1][x1-a1+(p[i]-p[i-1]+d[i])/2+1],MOD-f[i][x1]);

发现可以二维差分，于是就是$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……

code-unordered-tle

其实很明显d小的时候枚举度数会快一点，但考虑到不影响时间复杂度就没咋想，但其实取$d=2^{m/2}$的话只有$n/d$个点是要开表的，于是我们就能愉快地使用数组了，code