Google Code Jam 2020 R1A

正文索引 [隐藏]

Problem A：Pattern Matching
题目大意
样例
思路
代码
Problem B: Pascal Walk
题目大意
思路
代码
Problem C: Square Dance
问题大意
题解
代码

题目链接：https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74（需要飞机）

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

Problem A：Pattern Matching

题目大意

给你 $n$ 个包含至少一个 * 字符串，例如 V*W。
* 可以字符串匹配中匹配任意字符串（也可以是空串），例如 V*W，就可以匹配 VIW、VW、VXXW……
现在问你是否能找到一个字符串，可以匹配给定的 $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 步）

匹配 $leftStr$
通过 * 匹配 $str_j, j < i$
再匹配 $str_i$
再通过 * 匹配 $str_j, i < j$
最后匹配 $rightStr$。

代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 55;
int n;
char str[MAXN][150];
int lstr[MAXN], rstr[MAXN];
vector<char> strB, strE;

inline void solve(int T){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%s", str[i]);
        lstr[i] = 0;
        rstr[i] = strlen(str[i]) - 1;
    }

    bool flag = true;
    strB.clear(); strE.clear();
    while(true){
        char com = 0;
        for (int i = 1; i <= n; i++){
            char cur = str[i][lstr[i]];
            if (str[i][lstr[i]] == '*') continue;
            if (com == 0 || com == cur){
                com = cur;
            }else{
                flag = false;
            }
            ++lstr[i];
        }
        if (com == 0 || !flag) break;
        if (flag) strB.push_back(com);
    }
    while(true){
        char com = 0;
        for (int i = 1; i <= n; i++){
            char cur = str[i][rstr[i]];
            if (str[i][rstr[i]] == '*') continue;
            if (com == 0 || com == cur){
                com = cur;
            }else{
                flag = false;
            }
            --rstr[i];
        }
        if (com == 0 || !flag) break;
        if (flag) strE.push_back(com);
    }

    printf("Case #%d: ", T);
    if (!flag){ printf("*\n"); return ; }

    for (auto c: strB) printf("%c", c);
    for (int i = 1; i <= n; i++){
        for (int k = lstr[i] + 1; k < rstr[i]; k++){
            if (str[i][k] == '*') continue;
            printf("%c", str[i][k]);
        }
    }
    reverse(strE.begin(), strE.end());
    for (auto c: strE) printf("%c", c);
    printf("\n");
}

int main(){
    int T = 0; scanf("%d", &T);
    for (int i = 1; i <= T; i++) solve(i);
    return 0;
}

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAXN = 55;

int n;

char str[MAXN][150];

int lstr[MAXN], rstr[MAXN];

vector<char> strB, strE;

inline void solve(int T){

scanf("%d", &n);

for (int i = 1; i <= n; i++){

scanf("%s", str[i]);

lstr[i] = 0;

rstr[i] = strlen(str[i]) - 1;

}

bool flag = true;

strB.clear(); strE.clear();

while(true){

char com = 0;

for (int i = 1; i <= n; i++){

char cur = str[i][lstr[i]];

if (str[i][lstr[i]] == '*') continue;

if (com == 0 || com == cur){

com = cur;

}else{

flag = false;

}

++lstr[i];

}

if (com == 0 || !flag) break;

if (flag) strB.push_back(com);

}

while(true){

char com = 0;

for (int i = 1; i <= n; i++){

char cur = str[i][rstr[i]];

if (str[i][rstr[i]] == '*') continue;

if (com == 0 || com == cur){

com = cur;

}else{

flag = false;

}

--rstr[i];

}

if (com == 0 || !flag) break;

if (flag) strE.push_back(com);

}

printf("Case #%d: ", T);

if (!flag){ printf("*\n"); return ; }

for (auto c: strB) printf("%c", c);

for (int i = 1; i <= n; i++){

for (int k = lstr[i] + 1; k < rstr[i]; k++){

if (str[i][k] == '*') continue;

printf("%c", str[i][k]);

}

reverse(strE.begin(), strE.end());

for (auto c: strE) printf("%c", c);

printf("\n");

}

int main(){

int T = 0; scanf("%d", &T);

for (int i = 1; i <= T; i++) solve(i);

return 0;

}

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$ 转化为二进制作为到底取哪些行的方案即可，这样实现起来也简单。

代码

#include <cstdio>

using namespace std;

inline void solve(int T){
    printf("Case #%d:\n", T);
    int n = 0, ext = 0; scanf("%d", &n);

    if (n <= 50){
        for (int i = 1; i <= n; i++) printf("%d 1\n", i);
        return;
    }

    bool left = true;
    n -= 30;
    for (int i = 1; i <= 30; i++){
        if (left) {
            printf("%d 1\n", i);
        }else printf("%d %d\n", i, i);

        if (n & 1){
            if (left){
                for (int k = 2; k <= i; k++)
                    printf("%d %d\n", i, k);
            }else{
                for (int k = i - 1; k >= 1; k--)
                    printf("%d %d\n", i, k);
            }
            left = !left;
            ++ext;
        }
        n /= 2;
    }
    for (int i = 31; i <= ext + 30; i++){
        if (left) {
            printf("%d 1\n", i);
        }else printf("%d %d\n", i, i);
    }
}

int main(){
    int T = 0; scanf("%d", &T);
    for (int i = 1; i <= T; i++) solve(i);
    return 0;
}

#include <cstdio>

using namespace std;

inline void solve(int T){

printf("Case #%d:\n", T);

int n = 0, ext = 0; scanf("%d", &n);

if (n <= 50){

for (int i = 1; i <= n; i++) printf("%d 1\n", i);

return;

}

bool left = true;

n -= 30;

for (int i = 1; i <= 30; i++){

if (left) {

printf("%d 1\n", i);

}else printf("%d %d\n", i, i);

if (n & 1){

if (left){

for (int k = 2; k <= i; k++)

printf("%d %d\n", i, k);

}else{

for (int k = i - 1; k >= 1; k--)

printf("%d %d\n", i, k);

}

left = !left;

++ext;

}

n /= 2;

}

for (int i = 31; i <= ext + 30; i++){

if (left) {

printf("%d 1\n", i);

}else printf("%d %d\n", i, i);

}

int main(){

int T = 0; scanf("%d", &T);

for (int i = 1; i <= T; i++) solve(i);

return 0;

}

Problem C: Square Dance

问题大意

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

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

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

题解

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

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

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

代码

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#define LL long long
#define PII pair<int, int>
#define MP(x, y) make_pair(x, y)

using namespace std;

const int MAXN = 3e5 + 500;

struct Link{
    int l, r;
    int u, d;
}link[MAXN];
queue<PII> dque, que[2];
bool inque[2][MAXN], isdel[MAXN];
int n, m, val[MAXN];
int gid(int x, int y){ return x * (m + 2) + y; }

inline void in_que(int c, int x, int y){
    int idx = gid(x, y);
    if (inque[c][idx]) return;
    if (isdel[idx]) return;
    que[c].push(MP(x, y));
    inque[c][idx] = true;
}

inline void solve(int T){
    scanf("%d%d", &n, &m);

    while(!que[0].empty()) que[0].pop();
    while(!que[1].empty()) que[1].pop();
    while(!dque.empty()) dque.pop();

    for (int i = 0; i < n + 2; i++){
        for (int j = 0; j < m + 2; j++){
            int idx = gid(i, j);
            link[idx].l = max(0, j - 1);
            link[idx].r = min(m + 1, j + 1);
            link[idx].u = max(0, i - 1);
            link[idx].d = min(n + 1, i + 1);
            inque[0][idx] = inque[1][idx] = false;
        }
    }

    LL ans = 0, sum = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int idx = gid(i, j);
            scanf("%d", &val[idx]);
            sum += val[idx];
            inque[0][idx] = true;
            isdel[idx] = false;
            que[0].push(MP(i, j));
        }
    }

    for (int rt = 0; ; rt++){
        int eli = 0; ans += sum;
        int cur = rt & 1;
        int nxt = cur ^ 1;

        while(!que[cur].empty()){
            int x = que[cur].front().first, y = que[cur].front().second;
            int idx = gid(x, y); que[cur].pop(); inque[cur][idx] = false;

            int cnt = 0, skill = 0;
            if (link[idx].u > 0) ++cnt, skill += val[gid(link[idx].u, y)];
            if (link[idx].d <= n) ++cnt, skill += val[gid(link[idx].d, y)];
            if (link[idx].l > 0) ++cnt, skill += val[gid(x, link[idx].l)];
            if (link[idx].r <= m) ++cnt, skill += val[gid(x, link[idx].r)];

            if (cnt * val[idx] < skill) dque.push(MP(x, y)), isdel[idx] = true;
        }

        while(!dque.empty()){
            int x = dque.front().first, y = dque.front().second; dque.pop();
            int idx = gid(x, y); ++eli;
            // printf("Del %d %d\n", x, y);

            sum -= val[idx];
            if (link[idx].u > 0) in_que(nxt, link[idx].u, y);
            if (link[idx].d <= n) in_que(nxt, link[idx].d, y);
            if (link[idx].l > 0) in_que(nxt, x, link[idx].l);
            if (link[idx].r <= m) in_que(nxt, x, link[idx].r);

            link[gid(link[idx].u, y)].d = link[idx].d;
            link[gid(link[idx].d, y)].u = link[idx].u;
            link[gid(x, link[idx].l)].r = link[idx].r;
            link[gid(x, link[idx].r)].l = link[idx].l;
        }


        if (eli == 0) break;
    }

    printf("Case #%d: %lld\n", T, ans);
}

int main(){
    int T = 0; scanf("%d", &T);
    for (int i = 1; i <= T; i++) solve(i);
    return 0;
}

100

101

102

103

104

105

106

107

#include <cstdio>

#include <queue>

#include <algorithm>

#include <iostream>

#define LL long long

#define PII pair<int, int>

#define MP(x, y) make_pair(x, y)

using namespace std;

const int MAXN = 3e5 + 500;

struct Link{

int l, r;

int u, d;

}link[MAXN];

queue<PII> dque, que[2];

bool inque[2][MAXN], isdel[MAXN];

int n, m, val[MAXN];

int gid(int x, int y){ return x * (m + 2) + y; }

inline void in_que(int c, int x, int y){

int idx = gid(x, y);

if (inque[c][idx]) return;

if (isdel[idx]) return;

que[c].push(MP(x, y));

inque[c][idx] = true;

}

inline void solve(int T){

scanf("%d%d", &n, &m);

while(!que[0].empty()) que[0].pop();

while(!que[1].empty()) que[1].pop();

while(!dque.empty()) dque.pop();

for (int i = 0; i < n + 2; i++){

for (int j = 0; j < m + 2; j++){

int idx = gid(i, j);

link[idx].l = max(0, j - 1);

link[idx].r = min(m + 1, j + 1);

link[idx].u = max(0, i - 1);

link[idx].d = min(n + 1, i + 1);

inque[0][idx] = inque[1][idx] = false;

}

LL ans = 0, sum = 0;

for (int i = 1; i <= n; i++){

for (int j = 1; j <= m; j++){

int idx = gid(i, j);

scanf("%d", &val[idx]);

sum += val[idx];

inque[0][idx] = true;

isdel[idx] = false;

que[0].push(MP(i, j));

}

for (int rt = 0; ; rt++){

int eli = 0; ans += sum;

int cur = rt & 1;

int nxt = cur ^ 1;

while(!que[cur].empty()){

int x = que[cur].front().first, y = que[cur].front().second;

int idx = gid(x, y); que[cur].pop(); inque[cur][idx] = false;

int cnt = 0, skill = 0;

if (link[idx].u > 0) ++cnt, skill += val[gid(link[idx].u, y)];

if (link[idx].d <= n) ++cnt, skill += val[gid(link[idx].d, y)];

if (link[idx].l > 0) ++cnt, skill += val[gid(x, link[idx].l)];

if (link[idx].r <= m) ++cnt, skill += val[gid(x, link[idx].r)];

if (cnt * val[idx] < skill) dque.push(MP(x, y)), isdel[idx] = true;

}

while(!dque.empty()){

int x = dque.front().first, y = dque.front().second; dque.pop();

int idx = gid(x, y); ++eli;

// printf("Del %d %d\n", x, y);

sum -= val[idx];

if (link[idx].u > 0) in_que(nxt, link[idx].u, y);

if (link[idx].d <= n) in_que(nxt, link[idx].d, y);

if (link[idx].l > 0) in_que(nxt, x, link[idx].l);

if (link[idx].r <= m) in_que(nxt, x, link[idx].r);

link[gid(link[idx].u, y)].d = link[idx].d;

link[gid(link[idx].d, y)].u = link[idx].u;

link[gid(x, link[idx].l)].r = link[idx].r;

link[gid(x, link[idx].r)].l = link[idx].l;

}

if (eli == 0) break;

}

printf("Case #%d: %lld\n", T, ans);

}

int main(){

int T = 0; scanf("%d", &T);

for (int i = 1; i <= T; i++) solve(i);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑