比赛名称¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 19/72 | 7 | 9 | 11 |
A¶
solved by JLK
题意¶
规定一个字体，在这个字体下有很多水平反转、竖直翻转和旋转180度的字母对称关系。判断两个串是否能被经过某些变换变得相同。
题解¶
模拟题，但是有一些要注意的地方。
显然最多只会变换一次，两次及以上可以当做一次或零次变换。
题目给出的对称关系有些是可以推出另外关系的。
还要注意判断两个串是否长度相同。
B¶
solved by JLK
题意¶
链表模拟题，略
题解¶
C¶
solved by YZW
题意¶
在网格图上画首尾相连的一笔画封闭图形，求至少多少个颜色能相邻不同色地染除无限平面外的区域。
题解¶
猜答案为 1 或者 2，配合平面图转对偶图之类的操作判断有没有一条边与两个染色的区域相邻，有则答案为 2，否则答案为 1。可以用环路积分符号判断是有限区域还是无限平面。
D¶
upsolved by
题意¶
题解¶
E¶
solved by JLK
题意¶
有一个披萨，平均切成\(n\)份，第一份和第\(n\)份的边界水平于桌面边界，圆心和桌面的边界距离为\(d\)。现在要每次取走一份披萨，如果有一部分连在一起的披萨重心落到桌面外，就会掉落。求不掉落的方案数。
\(1 \le n,r,d \le 100\)
题解¶
首先要判断某一连续区间的披萨的重心是否在桌面上。这可以用积分算，换成极坐标积分即可。
然后就是一个经典的区间DP。\(dp_{i,j}\)表示\([i,j]\)区间的披萨取完一共有多少方案，每次枚举下一个取的披萨转移，乘上左右的方案数和组合数。
由于是一个圈，可以先扩展成长度\(2n\)的序列做区间DP，然后枚举第一次取的披萨算答案即可。
\(O(n^3)\)
F¶
solved by TYB
题意¶
有点麻烦的string模拟题。
题解¶
略。
G¶
solved by YZW
题意¶
解非满秩四元线性方程组。
题解¶
推式子即可。
H¶
upsolved by TYB
题意¶
给出一些2-sat的变量和限制关系，变量分为两类：第一类取值固定，第二类取值可以调整。设第一类变量有\(k\)个，求对于第一类变量所有\(2^k\)种取值情况，是否可以找到一组第二类变量的取值，使得满足所有的限制条件。若\(2^k\)种都不行，则输出NO；若\(2^k\)种都可以，则输出YES；否则输出MAYBE。
变量和限制关系都是\(10^5\)级别。
题解¶
按题意建出2-sat，NO的情况就是这个2-sat无解。把强连通分量缩点后得到一个DAG，考虑什么时候是MAYBE。如果一个强连通分量里有大于一个表示第一类变量的点（下面简称特殊点），则它们的取值会互相影响，是MAYBE。如果一个特殊点能到达另外一个特殊点，也是MAYBE。此外的情况是YES。在DAG上简单DP即可。
I¶
upsolved by
题意¶
题解¶
J¶
solved by TYB
题意¶
\(n\)个点\(m\)条边的无向平面图，点和边上都有权值，经过会获得其权值，多次经过则获得多次，求出从哪些点出发，经过所有点和边期望获得的权值和最小，并输出其权值（以浮点数形式输出）。
\(n\le8\)
题解¶
只要经过了所有边，则一定经过了所有点。\(8\)个点的完全图边数是\(28\)，猜想有了平面图这个限制后，边数不会多于\(21\)（实际上平面图的点数、边数这些是满足欧拉公式的，但我仍然不太会求它的上界），于是就有了暴力做法，\(f[i][S]\)表示现在在\(i\)点，已经经过的边的状态是\(S\)，要经过所有边期望的权值和。这个东西转移的时候会成环，需要用高斯消元。但由于这个是一个跟\(S\)有关的分层图，每层其实只有\(n\)个变量，所以复杂度为\(\mathcal{O}(2^mn^3)\)，可以通过。注意要预处理哪些是合法状态，不合法的状态要特殊处理。
K¶
upsolved by JLK
题意¶
平面图欧几里得最小生成树的最大边。
题解¶
套板子。
记录¶
TYB写F，WA1后AC(0:33)。
JLK签B(0:42)。A也可以写，但是怕没有看清题意。
YZW先写过G(0:48)。
JLK写A，WA1后AC(1:21)。
然后看J，觉得可以写，TYB上手写，调了许久之后AC。(3:10)
JLK写E，中间有一些不确定的地方，和TYB写H交替进行。
YZW给了建议之后过了E(4:21)。
之后H也写好了，但是一直WA。JLK开始抄K板子，没抄完。
总结¶
JLK:中间J题写的有点慢。当一个人写题遇到瓶颈的时候剩下人应该多帮助一下。
TYB：J题写得慢一方面是代码能力确实不行，可能要多vpCF训练一下；一方面是高斯消元这种能自己写出来但不够熟练的东西没有准备板子，有的地方写错了，应该也要准备模板。
Dirt¶
A(-1)
F(-1)