2022.10.16

模拟赛
2019 China Collegiate Programming Contest Final (CCPC-Final 2019)

L

题意：只能直行或者右转，问有多少种走遍一个矩阵的方法。
解法：构造题，考虑任意一种方案可以分成从内向外的螺旋和从外向内的螺旋，中间由一条位于矩形边缘的边连接，所以答案就是2(n-1+m-1)，注意到n,m为1的情况，特判即可。

H

题意：给出若干字符串，求拼接方式，使得结果包含最多SAD
解法：分析题，内部SAD预处理，考虑边缘情况。两边各有匹配0/1/2三种情况，此外需要特判单独一个字符A。考虑1-2匹配和2-1匹配和所有匹配数量，涉及到的字符串数量不能等于匹配数量（此时意味着环），如相等则减一。再考虑A，每次等价于将?-1变成?-2，此处需要讨论?的取值，贪心取即可，最后对所有情况取max。

E(口胡)

题意：给出若干大小相同的正方形，依次放在平面上，如果放上去时与一个已经放好的正方形重合超过固定比例，则不放上去，问最终哪些放上去了。
解法：考虑整个平面按边长划成网格块，左上角顶点在同一个网格内的正方形数量不会很多，最多是四个（总之是常数），所以找到枚举九宫格内所有正方形复杂度可以接受。

B(口胡)

题意：给出一副带权有向图，求0到1节点字典序最小的路径。
解法：除去不能到达1的节点，求出k步后字典序最小的点集，共求n+eps步即可，如果在此之前已经到达1，则输出答案。