=====比赛信息===== * **日期：2020.8.3** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5673#rank|传送门]] * **做题情况：lxh(A)，tyx(AG)，gyp(EIK)** =====题解===== ====A - All-Star Game==== ===solved by tyx,lxh=== ===题意=== 有$n$个球员和$m$个粉丝，每个粉丝有可能是多个球员的粉丝，如果一个粉丝是某个球员$i$的粉丝或者他粉的球员的粉丝中有球员$i$的粉丝，那么他就回去看球员$i$的比赛，现在要选择若干个球员使得所有粉丝都来看比赛，问最少选几个，并且有$q$次询问，每次更改一个粉丝和球员的关系 ===数据范围=== $1 \le n,m,q \le 2 \times 10^5$，粉丝和球员的粉丝关系$\le 5 \times 10^5$ ===题解=== 单独一个状态的问题可以通过并查集解决，然后题目还有$q$次询问，是比较经典的动态图连通块个数判断，只需要把所有的边按照出现时间挂在时间线段树上，然后从根往叶子走，经过的边加入即可，为了可以回溯，需要用可以撤销的并查集，并查集部分需要像一般的按秩合并并查集一样维护点个数，还需要维护粉丝的个数来方便答案的统计。 ====B - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====C - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====D - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====E - Enigmatic Partition==== ===solved by gyp=== ===题意=== 定义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) ====F - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====G - Game SET==== ===solved by tyx=== ===题意=== 给出$N$张互不相同的牌，每张牌有四种属性，每一种属性有三个类别或者是$*$代表万能属性。现在三张牌能够组成一个set当且仅当对于每一个属性，这三张牌的类别各不相同或完全一样，问能否找出这样一个set ===数据范围=== 多组数据，$1 \le T \le 1000$，$N \le 256$ ===题解=== 直接记录下来哪些卡有，然后枚举两张卡看看第三张满足的是否有即可，虽然理论复杂度是$O(N^3)$的，但是远远达不到。标程做法更为巧妙，无法构成set的集合最大也就只有20个，所以我们往后枚举21张总能找到一个set或本身就是无解 ====H - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====I - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====J - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====K - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== =====Replay===== 第一小时：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也成功通过 =====总结===== * 要注意团队合作，必要的时候可以分别负责一部分代码