=====比赛信息===== * **日期：2020.7.18** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5668#rank|传送门]] * **做题情况：lxh(CG)，tyx(BDL)，gyp(AEF)** =====题解===== ====A - All with Pairs==== ===solved by -, upsolved by tyx=== ===题意=== ===数据范围=== ===题解=== ====B - Classical String Problem==== ===solved by tyx=== ===题意=== 给一个字符串，每次操作把前$k$个放到最后或者把后$k$个放到最前，期间会询问字符串的第$x$位的字符 ===数据范围=== $1 \le |s| \le 2 \times 10^6$，$1 \le Q \le 8 \times 10^5$ ===题解=== 看似十分麻烦，但是实际上每次操作就是把字符串的起始位置变化了一下，我们每次把头指针更换位置，查询的时候mod长度就可以了 ====C - Operation Love==== ===solved by gyp, written by lxh=== ===题意=== 给出一些点坐标，让你判断组成的图形是左手还是右手。 ===数据范围=== 点数为 $20$ ===题解=== 由于手上始终有最长的 $9$ 和 $10$ 两条相邻的边，我们对其做叉积来判断左右手即可。 ====D - Points Construction Problem==== ===solved by tyx=== ===题意=== 现在让你把平面上的$n$个整点涂黑，并且计算答案时，每有一个黑点和白点相邻答案就加一，问当涂黑$n$个点时答案能否为$m$，如果可以构造一组答案 ===数据范围=== 多组数据，$1 \le T \le 1000$，$1 \le n \le 50$，$1 \le m \le 200$ ===题解=== 首先如果每个黑点不相邻，答案最多是$4 \times n$，然后我们很容易发现答案最少的情况是尽量把黑点摆成一个$x \times x$的矩形，我们预处理出$n$个黑点最少是多少并且先把点放好，如果$m > 4 \times n$或者$m$小于我们预处理出的数就是无解。另外，因为只要黑点和黑点相邻，答案比最多的情况就会减少二，所以如果$m$是奇数也肯定无解。然后我们根据$m$的大小，从我们预处理出的点里面逐步移动其中的点，保证每次答案增大二，直到达到$m$的大小即可 ====F - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====G - Operating on a Graph==== ===solved by lxh，gyp=== ===题意=== 给出一些点和一些边，每次选定一个点，使这个点所代表的集合通过延伸出去的边覆盖周围的集合（被覆盖的集合无法再扩展） ===数据范围=== 点数 $ 2 \le n \le 800005 $ 边数 $ 1 \le m \le 800005 $ ===题解=== 我们可以发现，每次扩展中，已经用于扩展的点就不会再次使用了。利用这个性质，我们可以通过手写链表对每个集合含有哪些点进行处理，每次将链表弹空并通过枚举边和并查集判断加入新点即可。 ====H - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====I - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====J - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====L - Problem L is the Only Lovely Problem==== ===solved by tyx=== ===题意=== 给出一个字符串，问这个字符串是否是以"lovely"开头 ===数据范围=== 并不重要 ===题解=== 直接判断即可 =====Replay===== 第一小时：tyx发现L是签到题于是过了L，gyp和lxh开始想A并通过，tyx开始想B并通过，tyx发现C题并不麻烦于是和另外两人交流了一下，lxh随后通过了C 第二小时：三个人开始想G并想出，lxh开始写G并直接通过 第三小时：gyp和lxh开始想E，tyx开始想D，tyx写的D错了两次，gyp写的E答案错误后发现方法有问题，更换方法后通过E 第四小时：tyx发现了D题的问题，改正后通过了D，gyp开始想F，tyx和lxh开始想H，gyp通过F 第五小时：三个人一起想H并写了一个线段树维护的版本，但是最后没能在结束之前交上去（交上去以后超时） =====总结===== * 利用别人写代码的时间思考其它的问题非常重要