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

1
2
3
4
5
6
7
8
9
10
11
12
13
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);

然后一维差分:

1
2
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

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/40ba8320.html
转载请注明出处,谢谢!