2020-2021 BUAA ICPC Team Supplementary Training 04¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 2/16 | 9 | 9 | 11 |
P¶
solved by 2sozx Bazoka13 JJLeo
题意¶
消消乐，场地大小为 \(R \times C\)，一共有 \(K\) 种颜色，每次可以放一个 \(1 \times 2\) 或 \(2 \times 1\) 的块下落，上面的颜色随意。相同颜色超过 \(1\) 的连通块会消失，上面的块会继续掉落，现在给出一个稳定的局面，构造一种方案达到这种稳定局面。(\(R=C=4\) 或者 \(R=C=20\)，\(3 \le K \le 6\))
题解¶
因为最终局面稳定，我们可以先把数量为奇数的列最下面那块放好，然后再 2 个 2 个放竖直块即可，上述过程中所有局面都是最终局面的一个部分，必然合法。
考虑如何把数量为奇数的列最下面那块放好，比赛时做法复杂了，还考虑了最后两列的边界问题，实际上很简单：对于所有数量奇数的列，设下面那块颜色为 \(x\)，找另外一种不同的颜色 \(y\)，放两个竖着的块，构成如下效果： $$ \begin{aligned} \color{red} y \newline \color{red} y \newline \color{blue} y \newline \color{blue} x \end{aligned} $$ 上面三个块消掉了，就只剩下 \(x\) 了，注意周围的块高度都不超过 \(1\)，且高度为 \(1\) 的块必然不为 \(x\)（否则就不稳定了），所以这样做中途不会受到其它块的影响。
Q¶
solved by 2sozx
题意¶
开始是空串，每次操作给出一个字母或者 \(-\) 。若为字母则向末尾添加这个字母，否则删除最后一个字符，求每次操作后的回文子串个数。\(q\le10000\)
题解¶
考虑暴力算法，维护每个回文串的开头和结尾，串最多 \(q^2\) 个，删除时直接删除回文串的末尾为删除位的串，添加时考虑新增的回文串的构成一定是这个字符与前面回文串的组合，特殊考虑仅有 \(1,2\) 个字符组成回文串即可。
R¶
upsolved by
题意¶
题解¶
S¶
upsolved by
题意¶
题解¶
T¶
upsolved by
题意¶
题解¶
U¶
upsolved by
题意¶
题解¶
V¶
solved by 2sozx JJLeo
题意¶
给定一个 \(n\) 个点 \(m\) 条边的带权无向图，其中一些点是特殊点，仿照 V 图的定义，每条边上每个点属于离它最近的那个特殊点，如果有多个特殊点满足条件，取编号更小的那一个。问每个特殊点有多少长度的边上的点都属于它。(\(1 \le n \le m \le 250\,000\))
题解¶
多源 dijkstra，记录每个点距离哪个特殊点最近和对应的距离，那么每条边就可以根据两个端点上的信息和这条边的长度，快速计算哪些部分属于两侧的哪个点了。
W¶
solved by 2sozx JJLeo
题意¶
给定一个长度为 \(n\) 的 \(\texttt{01}\) 串，可以选择一个子串（可以为空）将其变为 1 个 \(\texttt{1}\)，求得到字符串字典序最大的方案。(\(1 \le n \le 10^6\))
题解¶
最优方案一定是先忽略前缀 \(\texttt{1}\)，然后选择一段进行操作，对后面的部分求后缀数组排序比较选择最大的即可。
X¶
solved by 2sozx JJLeo
题意¶
给定一个 \(n\) 个点 \(m\) 条边的无向带权图，无自圈重边，求从 \(1\) 到 \(n\) 恰好经过 \(k\) 条边的简单路径长度的最小值，或判断不存在这样的路径。(\(2 \le n \le 10^6\)，\(1 \le m,k \le 10^6\)，\(\min(n,m,k) \le 5\))
题解¶
当 \(m < k\) 或 \(n - 1 < k\) 时必然无解，从而有解时 \(\min(n,m,k) = k \le 5\)。
考虑 \(k=5\) 的情况，可以处理出从起点和从终点出发，经过两条不同的边，对于每个点来说，到达该点经过距离的最小的三个值，以及对于每个值中间所经过点的编号。枚举所有边，将该边当作所求路径中的第三条边，将这条边的两个端点一个从由起点出发的最小的三个值中选取，另一个从由终点出发的最小的三个值中选取（当然还要反过来再来一遍），通过中间节点的编号可以得到经过六个节点，将有重复的方案排除掉，可以证明上述九种方案中必然存在合法的，从而以该边为第三条边的方案中的最小值必然存在于这九种方案中，因此最终所有节点的合法的值的最小值即为答案。
对于 \(k<5\) 的情况，是上述算法的简化版，仿照上述算法完成即可。
Y¶
upsolved by
题意¶
题解¶
Z¶
solved by JJLeo
题意¶
签到题。
题解¶
然而读错题了，血崩开局，本以为这把寄了，后期靠崔佬几何题成功翻盘。
记录¶
总结¶
- MJX：不要再写反变量了，最后越写越紧张
- ZYF：从头失误到尾，签到题读错了，X题读错了，最后写正解时又忘记转移变量，dijkstra写错了...
但是最后罚时并没有影响排名