PKUWC2019 游记与题解

PKUWC2019
菜鸡博主去不了ccf WC
目前暂时没有题解,等loj有题面先吧……

其他人的游记:
bztMinamoto
xzz

day1

自闭了,被广大附中的hz大爷d飞了,才人家的一半……

t1:n个节点m条边,求边集的子集下每个图的合法拓扑序之和,n小于20
题解:
考虑统计贡献相同的排列出现次数
设$f(S,tot)$表示当前用了S这些点,然后已知有tot条给出的边已知被满足,那么贡献次数就是$2^{tot}$
然后直接dp就是$2^n n^3$的
先考虑优化空间,按照1的数量滚动数组即可
优化时间,灵光一闪发现可以只处理到选n/2个1,大概210000个,dp就很快乐
然后关键是合并,一开始没有算复杂度就写写写,到这里以为要枚举tot1和tot2,心态就崩了,以为这个做法凉凉了,又忘记算一算
后来因为有点不甘心又想了想,发现可以分别求和然后乘法原理起来
然后卡卡常就过了,可能不是最优秀的做法,花了2.5h,同时间大把人已经切了两道题了
upd:不难发现我sb了,状态的第二维是没有必要的,因为2的次幂不像阶乘那样不能分解

t2:n个点的树,每个节点有颜色,定义点集的虚树为内部路径的并
求多少个颜色的集合,满足这些颜色的虚树的并非空
n小于1e5
题解:虚树的并还是树,然后贡献到树的深度最浅的节点上
然后就不会了……大概是set启发式合并+生成函数+fft什么的

t3:地主斗,给定至少包含的牌,然后判多少种方案平手【无法在某次询问中一个能出牌另一个不行】,规则很繁琐
题解:不会

day2

上午是数学,啥都不会

下午继续上机
t1:给出3个长度为100值域在ll内的数组a,l,r,求严格递增序列b,满足bi在[li,ri]内,而且是ai的超集
经历:开场就写了个22的暴力,然后就不会了……
题解:

t2:对于有向图G求无向图G’,用简单环对应点,然后有公共边就连接,求其联通块数,n在2e5内
经历:没时间写暴力了,爆0
题解:

t3:给出2e5个点,然后2e5次给定询问点,然后以原本的点为圆心,过询问点作圆,求最多去掉多少个圆后总面积不变
经历:杠了一场,发现有趣的东西,理论上70分但过不去,调了很久搞不出来,把凸包去掉就拿了47
题解:

我校两位神仙又让分了……

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