2020-2021:teams:hotpot:2020nowcoder8
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 11:09] misakatao 创建 |
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 16:37] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====比赛信息===== | =====比赛信息===== | ||
| - | * **日期：2020.8.1** | + | * **日期：2020.8.3** |
| - | * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5672?&headNav=www#rank|传送门]] | + | * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5673#rank|传送门]] |
| - | * **做题情况：lxh(C)，tyx(J)，gyp(BDH)** | + | * **做题情况：lxh(A)，tyx(AG)，gyp(EIK)** |
| =====题解===== | =====题解===== | ||
| - | ====A - ==== | + | ====A - All-Star Game==== |
| - | ===solved by === | + | ===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 - ==== | ====B - ==== | ||
| 行 49: | 行 55: | ||
| ===题解=== | ===题解=== | ||
| - | ====E - ==== | + | ====E - Enigmatic Partition==== |
| - | ===solved by === | + | ===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 - ==== | ====F - ==== | ||
| 行 69: | 行 81: | ||
| ===题解=== | ===题解=== | ||
| - | ====G - ==== | + | ====G - Game SET==== |
| - | ===solved by === | + | ===solved by tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给出$N$张互不相同的牌，每张牌有四种属性，每一种属性有三个类别或者是$*$代表万能属性。现在三张牌能够组成一个set当且仅当对于每一个属性，这三张牌的类别各不相同或完全一样，问能否找出这样一个set | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 多组数据，$1 \le T \le 1000$，$N \le 256$ | ||
| ===题解=== | ===题解=== | ||
| - | ====H - Harmony Pairs==== | + | 直接记录下来哪些卡有，然后枚举两张卡看看第三张满足的是否有即可，虽然理论复杂度是$O(N^3)$的，但是远远达不到。标程做法更为巧妙，无法构成set的集合最大也就只有20个，所以我们往后枚举21张总能找到一个set或本身就是无解 |
| + | |||
| + | ====H - ==== | ||
| ===solved by === | ===solved by === | ||
| 行 120: | 行 138: | ||
| =====Replay===== | =====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也成功通过 |
| =====总结===== | =====总结===== | ||
| - | * | + | * 要注意团队合作，必要的时候可以分别负责一部分代码 |
2020-2021/teams/hotpot/2020nowcoder8.1596769774.txt.gz · 最后更改: 2020/08/07 11:09 由 misakatao
