2021-2022 BUAA XCPC Team Supplementary Training 03¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 4/19 | 7 | 11 | 12 |
A¶
solved by JLK
题意¶
给一张照片，里面紧密排列着有若干长宽相同的窗户（由#分隔），两个窗户本质相同当且仅当某一个旋转若干次后和另一个重合。求本质不同的窗户数。
\(1 \le r,c \le 111\)
题解¶
首先得到每个窗户的长宽，然后枚举两个窗户，判断是否相同。注意只有正方形才可以转90度或270度。
而且窗户有可能是1x1的形状，最多可能有2500+个窗户。需要注意数组。
B¶
upsolved by TYB
题意¶
给出一个左边\(n\)个点，右边\(m\)个点的二分图，点有点权，选出若干个点，满足点权和\(\ge t\)且这些点是某个匹配方案的子集（即是匹配边的其中一个端点）。
\(n,m\le 20\)
题解¶
首先我们知道Hall定理：对于二分图\(G=(S\bigcup T,E)\)，设\(T\)中与\(S'\)中的点有边相连的点集为\(\Gamma(S')\)，它存在完美匹配当且仅当\(\forall S'\subseteq S\)，\(|S'|\le|\Gamma(S')|\)。对于这题，我们可以突发奇想猜一个结论：某个左边存在完美匹配的点集与某个右边存在完美匹配的点集合起来可以构造出一个覆盖它们的匹配。考虑证明：令左边的点集为\(A\)，右边的点集为\(B\)，若一条边存在于\(A\)的完美匹配中，从\(A\)向\(B\)连一条对应的边，若存在于\(B\)的完美匹配中，从\(B\)向\(A\)连一条对应的边。那么现在的图每个点的出度都为\(1\)，而且形成了若干条长度大于\(1\)的路径和若干个环，考虑由这个构造出一个合法的匹配，只需要保留路径或环上的第偶数条边即可。
C¶
solved by JLK
题意¶
有\(n\)个形状（边长为1的等边三角形，边长为1的正方形，直径为1的圆形）底部在水平线上排成一行。要用一个绳子把所有形状包起来，求最小长度。
\(1 \le n \le 20\)
题解¶
分类讨论较多。主要是要考虑三角形的顶点和正方形、圆形相切。需要用一些几何方法。
D¶
upsolved by JLK
题意¶
有\(6\times 6\)个柱子，\(n\)个大小不同的圆盘，一开始按给定顺序排列在\((1,1)\)的柱子上。每次移动可以选择一个柱子顶上的若干连续圆盘，一起移动到右边或者下边紧邻的柱子的顶上。要求最后在\((6,6)\)柱子上按从小到大（向下看）的顺序排列。给出方案。
\(1 \le n \le 4\times 10^4\)
题解¶
如果对于\((i,j)\)的柱子，能够在\((x,y)(x\lt i ||y\lt j)\)的若干柱子上反序排列若干圆盘，那么就可以用归并来把这里面所有的圆盘正序放到\((i,j)\)上。而在\((x,y)\)上按顺序放圆盘又是一个小规模的同样问题。
可以用递归解决这个问题。\(Solve(i,j,n,k)\)表示要在\((i,j)\)柱子上放\(n\)个圆盘，\(k\)表示正序或反序。那么每次递归到\((x,y)\)柱子，让它排序若干个圆盘，解决之后归并，每次把某个柱子的顶上一个圆盘移动到\((i,j)\)。在\((1,2)\)或\((2,1)\)的时候特判，可以从\((1,1)\)至多两步到达目标。
现在讨论这样做能够排序多少圆盘。令\(F_{i,j}\)表示\((i,j)\)柱子上最多能有多少个有序的圆盘。那么\(F_{i,j}=\sum\limits_{x\lt i||y \lt j}F_{x,y}\)。
有初始值\(F_{1,1}=1,F_{1,2}=F_{2,1}=2\)。可以发现\(F_{6,6}=42960 \gt 40000\)，故这个做法可以通过。
在递归的时候，让每个柱子排序不超过\(F_{i,j}\)个圆盘即可。由于一个圆盘被移动\(11\)次，故总复杂度为\(O(11nlog36)=O(n)\)。
E¶
solved by YZW
题意¶
给出 \(n,k\)，求 \(n\) 组 \((a_i,b_i,c_i)\) 使得 \(\sum_{\text{cyc}}a_i^2=1+k\sum_{\text{cyc}}a_ib_i\)，并且所有 \(a_i,b_i,c_i\) 互不相同。
\(1\leq n,k\leq 1000\)
题解¶
易知一组平凡解 \((1,k,k^2+k)\)。
可以发现对于一组 \((a,b,c)\) 固定 \(a,b\) 可以推出另一组 \((a,b,c')\)，\(c'>c\)；固定 \(a,c\) 同理。可以暴力列式利用 Vieta 定理求得 \(c'\)。
从平凡解 BFS 推出更多解，若一组解与答案集合没有重复元素就将其加入答案，直到求得 \(n\) 组答案为止。
答案可能很大，一起来做 Python 战士吧！复杂度不会分析。
F¶
solved by TYB
题意¶
签到，考验题意理解。
题解¶
略。
G¶
upsolved by JLK
题意¶
有一个\(2^n\times 2^n\)的方格。编号方式如下：
总共有\(2n\)个二进制位，按位从大到小依次赋值。
每次先把按x坐标分成两半，小的那一块这一位为0，大的为1。
然后按y坐标同理。
这两步循环进行\(n\)次后得到每个点的编号。
现在用一个\(m\)个点的多边形框出若干格子，要求选不超过\(k\)个编号区间，使得这些区间的并集覆盖了所有框出来的格子，并且并集最小。
\(1 \le n \le 30,1 \le m \le 200\)
题解¶
如果把被框出来的格子编号标1，否则标0，那么在编号的序列上，选\(k\)个区间的最优方案是，标1的最左到最右的距离减去\(k-1\)个最大的连续0的区间。
如果能处理出0的区间，询问就很方便了。
最暴力的方法是，按题目给的方法分治，分治到的一块实际上对应着一个连续编号区间。每次记编号最小和最大的连续0长度，然后合并得到跨过分治中心的0区间。
这样处理也可以直接得到\(k=1\)的答案（总长-整个区间的最左0区间和最右0区间）。
但这样至少是\(O(2^{2n})\)，无法承受。
实际上\(m\)较小，而且会有很多分治的小块是本质相同的。如果当前向下分治的时候，两个块本质相同，那么就可以只分治到一边，对它得到的所有0区间个数都乘2。
对于按\(x\)分两半的情况，本质相同就是都完全被多边形覆盖、都没有被多边形覆盖或者只是被\(y\)相同的若干条边切开。\(y\)分两半同理。
这样的状态数其实不多。因为对于指定\(a\times b\)的矩形，用它依次整齐排列去覆盖整个\(2^n\times 2^n\)的格子，只保留包含多边形顶点以及和这个四联通的矩形，剩下的矩形本质上都可以表示成保留下来的矩形。
那么对于某个分治小块，把这一层所有相同大小的块拿出来，实际上也是用这个小块去覆盖整个格子。那么这一层就只有\(O(m)\)个本质不同的矩形。
一共会遍历到\(O(nm^2)\)的状态（存疑，可以看一看这个博客），每次\(O(m)\)判断是否需要分治下去，总复杂度为\(O(nm^3)\)。
最后把提取出来的区间排序，询问的时候直接二分即可。
H¶
solved by YZW
题意¶
给出一个 \(n\times n\) 的地图，地图中可能有障碍物。
\(q\) 次询问，每次询问给出地图中两个点 \(A,B\)，询问最大的矩形边长，使得矩形中心能从以 \(A\) 位置出发，不经过障碍物与边界，到达 \(B\) 位置。显然矩形边长是奇数。
\(1\leq n\leq 1000\)，\(1\leq q\leq 3\times 10^5\)
题解¶
BFS 求出地图每个点与边界或障碍物的最近距离。
由大到小枚举答案，将与边界或障碍物最近距离不小于当前枚举的答案的相邻点在并查集里合并，合并是不需要撤回的。合并之后枚举所有询问，判断对应点是否属于同一并查集，若是则更新答案。
\(O(nq+n^2\log n)\)
也可以 Kruskal 重构树。
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by TYB&JLK
题意¶
有\(n\)个点，给出一条长度为\(d\)的路线（可能有重复的点），要求依次经过路线上的点，从一个点到另一个点有两种方式，一是通过单程票，从\(a\)到\(b\)花费\(c\)；二是通过双程票，从\(a\)到\(b\)，再从\(b\)到\(a\)，总共花费\(c\)，两次旅程不必连续，但必须按照给定的顺序，也可以只用双程票的前一程，但不能只用后一程。共有\(m\)种票，求最小花费。
\(n,m,d\le3\times 10^5\)
题解¶
把所有出发点和终点是相同两点的路径拉出来，即把所有\(x->y\)和\(y->x\)的路径拉出来，不同的之间不会互相影响。把\(x->y\)的路径记作\(A\)，\(y->x\)的路径记作\(B\)，问题转化为有一个\(AB\)序列，可以用\(Cost_{AB}\)的代价消去一个\(AB\)，要求\(A\)在\(B\)的前面，\(Cost_{BA}\)的代价消去一个\(BA\)，同样要求\(B\)在\(A\)前面，\(Cost_A\)消去一个\(A\)，\(Cost_B\)消去一个\(B\)，求最后消去所有的最小代价。通过一些处理可以使\(Cost_{AB},Cost_{BA}\le Cost_A+Cost_B\)，那么肯定是尽量用双程票，即尽量两个两个地消去，那么只需要贪心地先用花费小去消即可。简要证明一下，尽量用双程票，那么最后只会剩下一种字母，其花费是固定的；而对于双程票，它总共的使用次数也是固定的，所以只要尽量用花费小的即可。
K¶
solved by TYB
题意¶
给出一个长度为\(3n\)的\(01\)串，每次可以取反相邻的两个位置，最多取反\(n\)次，使得最后至少有\(2n-1\)的位置相邻的数不同。
题解¶
因为长度是\(3n\)，最后要求\(2n-1\)，容易想到每三个位置贡献两个。对于三个位置的所有八种情况，除\(000\)和\(111\)外，都可以通过最多取反一次得到\(010\)或者\(101\)，那么\(000\)和\(111\)就考虑和前一段做出贡献。如果\(000\)的前一位是\(1\)，那么取反前两个，否则取反后两个。\(111\)同理。因为第一段没有上一个，所以第一段可能只能贡献一，总共为\(2n-1\)。
L¶
solved by YZW
题意¶
给出 \(n\) 个未知元 \(x_i\) 的 2-SAT 的三个不同的解，构造一个 \(m\) 个形如 \((!)x_i\rightarrow (!)x_j\) 限制的 2-SAT 使得解有且仅有给出的三个解，或是判定不存在。
\(2\leq n\leq 50\)，\(1\leq m\leq 500\)
题解¶
首先根据某个特定未知元在三个解中的值，可以将未知元划分为至多 \(2^3\) 个等价类。等价类选取代表元 \(x_i\)，与其他未知元 \(x_j\) 建立限制 \(x_i\rightarrow x_j\) 且 \(x_j\rightarrow x_i\) 即可建立等价关系，这部分产生的限制至多 \(2n\leq 100\) 个。
接下来考察 \(8\) 个等价类，将两两代表元之间所有成立的限制（最多 \(8\) 个：\(x_i\) 推 \(x_j\) 和 \(x_j\) 推 \(x_i\)；\(x_i\) 是否取反；\(x_j\) 是否取反）全部建立限制，这贪心地将 2-SAT 解的个数降到最低。这部分产生的限制至多 \(4\times 8^2=256\) 个。
暴力枚举所有等价类的可能取值，共 \(2^8\) 种情况，计算解的个数，若为 \(3\) 即得到答案，否则不存在满足条件的 2-SAT。
构造的限制总数至多 \(356\) 个，小于 \(m\)，可以 AC。
记录¶
开局JLK看AC都可做，选择先写C，分类讨论麻了。
TYB先写了F，题意读错了WA1。
C WA1后改了特判AC(0:51)。
不久F也过了(0:54)。
JLK继续写A，没有考虑到极端情况RE1后AC(1:07)。
TYB过K(1:13)。YZW随后写H，以为时限足够写了个\(O(n^3)\)然后TLE1。改了后AC(1:59)。
JLK叫YZW对E打表，然后尝试找规律，本地尝试多次后AC(3:13)。
JLK和TYB讨论J，先扔了个错误的贪心。
之后YZW挤下来写L，AC(4:19)。
J又讨论了很久贪心，换了个做法还是WA。
赛后全部改成long long后AC了。（因为INF设置为0x3f3f3f3f，但是两个1e9加起来大于了。由于原来怕乘起来爆long long，就只设置了int内的INF。
总结¶
JLK：开场看到几个简单题时，应该选择分类讨论较少的题来写。J这个错误也是很难检查到的，下次要注意。
TYB：提高英语阅读能力，对于题意有疑问尽量求助队友。想点办法少点想假做法。
Dirt¶
A(-1)
C(-1)
F(-1)
H(-1)