WC2020游记

OI生涯没有WC没有APIO没有CTSC,有点伤心

Day1

路由器,DP推不出来,冬眠。下午没听懂,冬眠

Day2

没听懂,冬眠

Day3

没听懂,冬眠

Day4

没听懂,冬眠

Day5

考试,打铁了

Day6

咕咕咕


题解:

「WC2020」有根树

考场思路:考虑父亲肯定比儿子大,考虑维护集合,就在若干链上有分界线。每次修改时维护分界线即可。但是没仔细想怎么维护

实际上存在更简单的log^2做法:不需维护具体分界线,直接维护两个集合即可。具体来说,使用线段树维护集合。我们关心根集合的min,与非根集合的max。那么在修改时,考虑更新答案,即平衡max与cnt两者。这一操作可以通过线段树上二分找极值点实现

「WC2020」猜数游戏

考场思路:看错题了...之后发现是用若干操作覆盖点集,打了个状压跑路

首先容易用阶的那套理论求出若干关系:即用A可以删掉B。特别的,如果数与模数互质,则换另一套理论:这些数在log次幂内就会变成0

注意到这个关系有传递性,那么考虑一个点什么时候选:只有当不存在可以删它的点的时候

考虑题目要求的东西:每个集合里选多少点。这个可以转化为每个点对多少集合贡献。那么求出有多少点不能选后做一下就好了

「WC2020」选课

考场思路:只写了p=0的分。凸包卷积一下,考场不知道为什么没调出来。

还没补,咕咕咕咕咕咕。听说卷完之后加个爬山就能过。做法上面的基础上是自然的:即对特殊的状压即可。具体细节还没研究。。

  1. 头像 ywy_c_asm说道:

    %%%%参加WC的开神犇

    1. kai586123 kai586123说道:

      我好像真打铁了QAQ

  2. 头像 cbio说道:

    orzorzorz

发表评论

电子邮件地址不会被公开。必填项已用 * 标注