PKUWC2019题解

PKUWC2019
菜鸡博主去不了ccf WC
目前题解都是口胡的,等loj有题面先吧……(似乎不会有了?如果做法假了请务必指出)

upd:好羞耻啊把以前的游记删了

D1T1 拓扑序计数

题意:n点m边有向图,求边集的子集下每个图的合法拓扑序之和,$n \le 20$

一个合法拓扑序的权值为$2^{m-不能有边数}$,设$f(S)=带权方案数$,通过/2来转移就好了,$O(n2^n)$

D1T2 你与虚树的故事

题意:$n \le 1e5$点树,给个点有颜色,定义点集的虚树为最小的包含所有点的子图,$\forall i求颜色集合大小恰为i,虚树交非空$

考虑单个i怎么求,不可容斥考虑唯一计数,注意到树交还是树,而树的根是唯一的,设$f_x=根恰为x,g_x=根为x祖先$

则$ans_i=\sum f_x=\sum (g_x-g_{fa})=\sum g_x(1-son_x)$,而显然$g_x=这个点在交上=C_{T_x}^i,其中T_x=子树内外都有的颜色数$,可以建出虚树后树上差分线性求。把式子化开就是$ans_i*i!=\sum (1-son_x)*(T_x)!*\frac{1}{(T_x-i)!}$,直接FFT优化即可,$O(nlogn)$

D2T1 递增序列

题意:统计多少个长度为n的严格递增序列b,满足$b_i \in [L_i,R_i]且a_i \subseteq b_i,其中l,r,a \in [0,2^{60}),n \le 100$

首先如果没有a的限制,那么就是apio2016划艇

二进制题肯定优先想怎么拆位做,比较大小也很自然会想从高到低位做,计数没法直接算也很自然地考虑dp

注意到递增是唯一将不同位置沟通起来的限制,那么$dp(i,l,r)$表示做到第i位且目前l到r是一样的,那么就是在前面填一段0在后面填一段1然后两边就独立了,边界i=-1的时候必须满足l=r即可

然后a的限制其实就等价于限制了划分点必须在一个区间,仅此而已

只剩下值域区间限制了,注意到我们只关心有哪些元素在前面是顶格的(类似数位dp),开一个维表示前面具体是什么,但如果在区间内都没出现过,那就是不用管的,这样的状态是$ \le 2(r-l+1)+1$个的,小常数$O(60n^4)$,因为限制的存在要用的状态可能不多,听说可过

其实把值域下界、值域上界独立处理成递增的,那么那个维就变成$[0/1][0/1]$表示是否是$R_l及L_r$了,$O(60n^3)$

D2T2 环图

题意:给一个n点$m \le 2e5$边有向图,对其每个简单环在新图中建一个点,新图中的无向边(x,y)存在当且仅当环x和环y有公共边​,问新图联通块个数

应该挺多人都是猜个结论感受一下挺对就写了过了的

注意到两个环有公共边的话一定在同一个SCC中;自环、同向的重边是没有意义的

考虑在一个SCC中两个环,没有公共边的情况是怎样的?瞎jb画点情况发现似乎边的方向性不再重要了

注意到两个环有连边的充要条件可以看做两个环的基图是点双,于是就是在SCC内看做无向边求v-DCC数,$O(n)$

D2T3 防御塔

题意:给出n个圆心,m次独立询问点A,n个圆心过A做圆,问n个圆心的最大子集使得圆的并不变,$n,m \le 1e5$

杠了一场,发现有趣的东西,理论上70分但过不去,调了很久搞不出来,把凸包去掉就拿了47

这题就不back了,因为当时为啥有问题至今不知道,希望有朝一日能把数据公布

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