Google Code Jam 2020 R1A

正文索引 [隐藏]

题目链接:https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74(需要飞机)

这场感觉发挥不错,不过题目也都比较简单:两个构造、一个暴力。


排名

Problem A:Pattern Matching

题目大意

给你 $n$ 个包含至少一个 * 字符串,例如 V*W
* 可以字符串匹配中匹配任意字符串(也可以是空串),例如 V*W,就可以匹配 VIWVWVXXW……
现在问你是否能找到一个字符串,可以匹配给定的 $n$ 个带 * 字符串,可以输出任意方案,不可以输出 *

样例


Input Output

2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ

Case #1: COCONUTS
Case #2: *

思路

所有字符串开头向后到 * 与结尾向前到 * 的字符是一定需要完全匹配的,因为这部分内容没有办法通过 * 进行通配。

只要满足这个条件,我们就一定可以构造一个字符串能够匹配所有的给定匹配字符串。我们取所有字符串第一个 * 之前内容中最长的那个记作 $leftStr$,所有字符串最后一个 * 之后的内容中最长的那个记作 $rightStr$,第 $i$ 个字符串第一个 * 到最后一个 * 间的删去 * 的内容为 $str_i$

答案为:$leftStr + \sum_{i=1}^n str_i+ rightStr$,此处加法为字符串连接。

第 $i$ 个字符串匹配我们构造字符串的时候,过程都是这样的:(特殊情况下可能没有第 3、4 步)

  1. 匹配 $leftStr$
  2. 通过 * 匹配 $str_j, j < i$
  3. 再匹配 $str_i$
  4. 再通过 * 匹配 $str_j, i < j$
  5. 最后匹配 $rightStr$。

代码

Problem B: Pascal Walk

题目大意

你在一个杨辉三角形的 $(1, 1)$ 处,你需要走出一条连续且不重复的路径,使得路径上的数字和等于 $n$,输出方案。
其中 $n\leq 1e9$,而且路径的长度不能超过 $500$。


杨辉三角形

思路

因为路径存在联通性的要求,所以从单个格子的角度考虑这件事情是非常复杂的,因为我们既要保持联通性也要考虑和等于 $n$。

杨辉三角形的行和等于 $2^k$,而把一个数字分解成 2 的若干次幂是很容易的(就是二进制),所以我们的路径可以按行遍历这个杨辉三角形取走一行的数字,而行与行之间我们可以走边缘的 1,整理一下就是对于第 i 行,不取 n-=1,取 n-=2^(i-1)

因为 $1e9 < 2^{30}$,所以基本上前 30 行左右我们就能把 $n$ 给凑出来,所以我们可以强制规定最终答案中一定有 30 行不取,将 n-=1 操作提前执行掉,那么接下来我们只需要将 $n-30$ 转化为二进制作为到底取哪些行的方案即可,这样实现起来也简单。

代码

Problem C: Square Dance

问题大意

给你一个 $R \times C$ 的舞台,每个格子初始都有一个人,能力值为 $v_{i,j}$。

我们将进行若干轮舞蹈,第 $k$ 轮舞会的有趣程度为在场所有人的能力值之和。
连续两轮舞蹈间,我们将会淘汰一些人。对于每个人,如果他的能力值小于,他各向上、下、左、右四个方向寻找遇到的第一个人能力值的平均值,那么他将无法进入下一轮舞蹈。
当无法淘汰任何一人的时候,舞蹈停止。

问所有轮舞蹈的有趣值之和是多少。

题解

显然的一件事情,如果一个人现在没有被淘汰,且他四个方向找到的人也没有变化,那么他一直不会被淘汰。

所以,一个人需要被检查是否要被淘汰,仅在第一轮与四个方向的人产生变化的时候。所以此回合淘汰一个人,下一回合因他而要被检查的人最多为四个。
一共有 $R\times C$ 个人,假设他们最终都被淘汰,那么,那么我们也一共要被检查 $4\times R \times C$ 次。
综上,如果我们只做有效的检查,那么这题暴力就可以过了。

我们使用跳舞链快速查找一个人四个方向遇到的第一个人,用两个队列维护需要检查的人,就可以了。

代码