CVBB ACM Team

• 日期：2020.5.23

• 比赛地址： 传送门

• 做题情况：lxh(AG)，tyx(BCF)，gyp(DE)

给出一个森林，求一种链接方式，将森林连成一棵树，并让树的直径最短。

点数 $ 0 \le c \le 10000$

将两棵树连在一起之后，考虑最小化直径，采取和按秩合并并查集类似的思想，我们就将直径的中点作为根来链接，并对新的直径的大小进行分析，我们不妨记两棵树的直径长度分别为 $a,b$ 且 $a \le b$ ,则：

若$ b \ge a+3 $,则新树的直径长度仍为 $ b $,

若$ b == a+2 $,当 $b$ 为奇数时，新树直径为 $b+1$, 当 $b$ 为偶数时，直径长度不改变。

若 $ b == a+1 $, 新树直径为 $ b+1 $。

经过以上分析，采取贪心的思想，我们只需要考虑前三大的直径就能保证直径不再扩大。

表面上给出的数字范围很大，但我们关心的只有它包含哪些位，用状压的方式压含有哪些位进行hash即可

给定由以下符号$“<”, “>”, “^”, “v”, “o”, “x”, “|”, “-”, “/”, “\backslash”$组成的$n×n$矩阵,给定操作如$“<”, “>”$代表顺/逆时针翻转矩阵，$ “|”, “-”, “/”, “\backslash”$代表沿该方向中轴翻转矩阵，要求输出结果矩阵。

注：$"<"顺时针翻转后为“v”$.

$n≤100$ ，操作串$≤1000000$

显然这题类似大模拟，耐心的话我们可以完成翻转等操作的实现，但是由于操作串过长而超时，细心观察后我们可以发现，它这样操作所能得到的矩阵形态时有限的，所以我们可以通过操作串直接计算得到最后的形态并进行变换。

一棵树，n个点中选m个，要求不能有孤立点（即每个被选的点旁边还有选中的点）。求方案数。

$2\le m\le n\le 200$

dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。 递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。

时间复杂度：$O(nm^2)$

在一个平面给出一些点，再给出一些圆，问有多少点没有被覆盖。（一个坐标上可以有多个点）

点数圆数 $\le 100000$, 坐标 $0 \le xi,yi \le 10000$ ,圆的半径 $ r \le 100 $.

本体坐标的范围较大，我们不妨考虑从圆的半径这较小的一维来切入，采取对点每行用一个 $vector$ 来保存，之后对于每个圆，由于只涉及到最多 $200$ 行，对每一行取 $lower\_bound$ 和 $upper\_bound$ 来得到圆覆盖的位置，并采取在开始位置 $+1$， 在结束位置 $-1$ 的方式来标记覆盖的点（因此 $vector$ 里的变量应当是 $pair$）,最后遍历所有 $vector$ 来统计标记前缀和为 $0$ 的点的数量.

给长度为n的序列，每个元素两个参数t（时间）,v。保证t严格递增。m次询问，每次问大于/小于，在k以内之前的时间里所有v的最大/最小/平均的元素个数。

$n\le 10^5，m\le 10$

因为数据不大，直接线段树+二分即可。如果数据再大一些，比如n是$10^6$，可以用前缀和+单调队列。

时间复杂度：$O(n\log n m)$或$O(nm)$

有一个$N \times N$的方阵，每一行和每一列都由$N$个不同的字母组成，现在有一个字母放错了位置，问是哪一个。例如：

ABC
BCA
BAB

中第三行第一个字母应该是C。

$3 \le N \le 26$

先从前三行找到两行的字母集合相同，可以用多种方式，我这里用的是一个26位的2进制数，然后开始找不合法的地方。如果一个字母在一行或一列出现两次就不合法，或者一个字母没有出现在我们刚刚找到的字母集合里就不合法。找到后输出即可。

第一小时：gyp,lxh面对一堆题看中了F。发现F可做，于是gyp开始写F。lxh,tyx开始看B，并想出来了。gyp写F不过样例，让lxh先写B并1a。

第二小时：gyp继续调F，继续不过样例。让lxh先写，写完却发现计蒜客上没有这道题。tyx发现J过的人很多，尝试并迅速通过。

第三小时：gyp继续调F，lxh和tyx想H。gyp终于过了F，lxh和tyx也想出了H。lxh开始写H，tyx看G并想出，tyx与gyp交流G。

第四小时：lxh写H未果。tyx写G但wa。gyp想出I，gyp开始写I。gyp的I一直wa。lxh开始看D并产生思路。

第五小时：lxh开始写D。tyx发现gyp未加多组数据。I通过。tyx的G一直wa。lxh写完D却tle。

赛后，tyx的G交到cf上ac，cf上的标程交到计蒜客上wa。

• 一定要注意有没有多组数据！