CVBB ACM Team

• 日期：2020.8.3

• 比赛地址： 传送门

• 做题情况：lxh(A)，tyx(AG)，gyp(EIK)

有$n$个球员和$m$个粉丝，每个粉丝有可能是多个球员的粉丝，如果一个粉丝是某个球员$i$的粉丝或者他粉的球员的粉丝中有球员$i$的粉丝，那么他就回去看球员$i$的比赛，现在要选择若干个球员使得所有粉丝都来看比赛，问最少选几个，并且有$q$次询问，每次更改一个粉丝和球员的关系

$1 \le n,m,q \le 2 \times 10^5$，粉丝和球员的粉丝关系$\le 5 \times 10^5$

单独一个状态的问题可以通过并查集解决，然后题目还有$q$次询问，是比较经典的动态图连通块个数判断，只需要把所有的边按照出现时间挂在时间线段树上，然后从根往叶子走，经过的边加入即可，为了可以回溯，需要用可以撤销的并查集，并查集部分需要像一般的按秩合并并查集一样维护点个数，还需要维护粉丝的个数来方便答案的统计。

定义n的一种划分为一个不减数列，相邻两项最多差1，首项和末项差2。f(n)为n的划分种数。求T组数据，f(n)。

$1\le T\le 10^4,1\le n\le 10^5$

设数列为m项。枚举$a_1，m$。对于这样的$a_1,m$的数列，计算其对f(a_1m+k)的贡献。发现，对$3\le k\le m$，其贡献为$\lfloor \frac {k-1}2 \rfloor$，对$m\le k\le 2m-3$，其贡献为$\lfloor \frac {2m-k-1}2 \rfloor$。设g(x)=f(x)-f(x-2)。先求g(x)，再得到f(x)

给出$N$张互不相同的牌，每张牌有四种属性，每一种属性有三个类别或者是$*$代表万能属性。现在三张牌能够组成一个set当且仅当对于每一个属性，这三张牌的类别各不相同或完全一样，问能否找出这样一个set

多组数据，$1 \le T \le 1000$，$N \le 256$

直接记录下来哪些卡有，然后枚举两张卡看看第三张满足的是否有即可，虽然理论复杂度是$O(N^3)$的，但是远远达不到。标程做法更为巧妙，无法构成set的集合最大也就只有20个，所以我们往后枚举21张总能找到一个set或本身就是无解

第一小时：gyp发现I比较简单于是直接通过，lxh开始想C，tyx开始想G

第二小时：tyx和gyp一起想K，gyp开始写但是WA了几次，后来发现了问题并通过。tyx发现G题非常简单于是迅速通过，lxh没有想出C开始想A

第三小时：gyp开始想E但是没有通过，lxh想出了一个A的方法后发现会丢失信息导致错误，于是重新开始和tyx一起想C

第四小时：gyp继续想E，tyx和lxh想出了A的方法于是开始码，lxh先写了可撤销并查集的部分

第五小时：tyx写了A题时间线段树的部分并成功通过，gyp想出了E也成功通过

• 要注意团队合作，必要的时候可以分别负责一部分代码