Contest Info

date: 2018.01.27 14:30-19:30

practice link

Solutions

B. Connect3

题目大意：两个玩家分别执黑白棋在 \(4\times4\) 的棋盘上游戏。每次只能落子在某一列的最低空闲位置。当一个玩家落子后，如果他的棋子连成了横、竖或者对角线的连续三颗，就取得了胜利，游戏结束。或者棋盘放满，也结束游戏。

求先手下 \((1,x)\) ，后手最后落子在 \((a,b)\) 并取得胜利的最终局面有多少种（不考虑落子的顺序）。

题解：显然输入只有 \(4\times16=64\) 种，可以搜出来打表。将局面状压成 \(16\) 位三进制数，bfs 将白子在 \((a,b)\) 获胜的局面插入到对应set中去重。

D. Happy Number

签到题。

F. Philosopher’s Walk

签到题，按题目描述递归计算即可。

G. Rectilinear Regions

题目大意：有两段左右无限延伸的楼梯（由水平线和竖直线组成） \(L\) 和 \(U\)，它们可能相交在一起形成一些闭合区域，求其中以 \(L\) 为底，\(U\) 为顶的闭合区域的个数及它们的面积之和。

题解：以两段楼梯的所有竖线所在直线为扫描线，从左到右扫描。

求区域的个数：记录当前是否在合法的区域中。扫描过程中，判断 \(L,U\) 是否相交（交于点或者线段）。如果不相交，那么什么都不发生。否则，若当前在一个合法区域中，表明这个区域已经结束，计数器加 \(1\)；若在这条扫描线后满足 \(y_{U}>y_{L}\) ，表明一个新的合法区域开始。

求面积之和：要求区域闭合，那么合法区域一定在 \(L,U\) 相交的最左、最右交点之间。我们枚举这之间所有相邻的两条扫描线，判断是否满足以 \(L\) 为底，以 \(U\) 为顶即可。

复杂度 \(\mathcal{O}((n+m)\log(n+m))\)。

H. Rock Paper Scissors

题目大意：给定两个字符串 \(a[0...n-1],b[0...m-1]\)。只由 'R','S','P' 三种字符组成，分别代表石头、剪刀、布。可以跳过字符串 \(a\) 的前若干个字母，然后开始依次比较。问 \(b\) 最多赢几次。

题解：对 \(b\) 的某个特定字符，我们求出从 \(a\) 的每个位置开始比较的赢的次数。以 \(b\) 中的 'R' 为例。

我们构造多项式：

\[ \begin{aligned} f(x)&=\sum_{k=0}^{n-1} [\text{a[k]=='S'}]x^k\\ g(x)&=\sum_{k=0}^{m-1} [\text{b[k]=='R'}]x^{m-1-k} \end{aligned} \]

那么 \([x^{k+m-1}]f*g\) 就是从 \(a_k\) 开始比较，\(b\) 中的 'R' 赢的次数。我们将每种字符加起来即可。

复杂度 \(\mathcal{O}(n\log n)\)。

K. Untangling Chain

题目大意：给出从原点 \((0,0)\) 开始的 \(n\) 条指令。每条指令给出移动距离 \(l_k\) 和到达之后的朝向 \(t_k\)。一开始朝着 \(x\) 轴正方向。要求你修改 \(\{l_k\}\) ，使得该折线是简单（所有线段只在端点相交）的，且修改之后的 \(l_k\in[1,n]\)。

题解：每次移动都恰好移动到当前图形在该方向的边界外面一个单位。

复杂度 \(\mathcal{O}(n)\) 。