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
  3. 再匹配 str_i
  4. 再通过 * 匹配 str_j, i
  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 次。
综上,如果我们只做有效的检查,那么这题暴力就可以过了。

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

代码