Kangaroo Puzzle & Eva and Euro coins ICPC 2018 Nanjing R

[ICPC 2018 Nanjing R] Kangaroo Puzzle

题目链接： [ICPC 2018 Nanjing R] Kangaroo Puzzle 。

题目描述：

你的朋友制作了一款名为“袋鼠谜题”的电脑视频游戏，想让你帮他试玩一下。正如游戏名称所示，谜题中困着若干只（至少 22 只）袋鼠，玩家的目标是控制它们聚集在一起。只要谜题中的所有袋鼠都聚到一起，它们就能借助袋鼠的神奇力量逃出谜题。

谜题是一个包含 n×mn \times m 个格子的 nn 行 mm 列网格。某些格子是墙壁，袋鼠无法进入这些格子。其余格子为空地。袋鼠可以向上、下、左、右四个方向移动。保证一只袋鼠可以从任意一个空格子出发到达任意另一个空格子。同时保证谜题中不存在环——也就是说，袋鼠不可能从一个空格子出发，经过若干不同的空格子，再回到初始格子。

初始时，每个空格子上恰好有一只袋鼠。你可以通过按下键盘上的 U\texttt{U}、D\texttt{D}、L\texttt{L}、R\texttt{R} 键来控制袋鼠。所有袋鼠会根据你按下的键同时移动。例如，当你按下 U\texttt{U} 键时，一只袋鼠若其上方格子存在且为空地，则会向上移动一格；否则原地不动。你最多可以按键 5000050000 次。如果在 5000050000 步之后仍有两只袋鼠位于不同格子，你将输掉游戏。

大概感性理解一下，你玩 2048 的时候瞎按按键总是输掉，所以随机 5×1045\times 10^4 个字符就行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    char c[4]={'L','R','U','D'};
    mt19937 rnd(time(NULL));
    for(int i=1;i<=50000;i++)
        putchar(c[rnd()%4]);
    return 0;
}

[ICPC 2018 Nanjing R] Eva and Euro coins

GZ!

题目链接： [ICPC 2018 Nanjing R] Eva and Euro coins 。

题目描述：

有长度为 n≤106n\le 10^6 的 0101 状态 s,ts,t ，每次你可以将 ss 的一段长为 kk 的相同字符反转，问是否可以从 ss 得到 tt 。

首先注意到操作可逆。于是我们可以考虑为每一个字符串定义一个所谓“最简串”，然后判断 s,ts,t 的“最简串”是否相同。

然后……

注意到如下构造：

定义一个串 ss 的“最简串”为：

每次将 ss 的一个长为 kk 的相同字符删除。最后的最简的结果为“最简串”。

显然对于任意两个可以互相转化的串最简串都一样。

所以现在的问题是：为什么这个构造可以对应一种翻转方案。

注意到如下构造：

考虑这样的结构：

1
111....1110000...0001111....111

删除时，先把 00 删除后把 11 删除。

容易发现这个可以对应这个反转方案：

先把 00 反转为 11 ，然后将这 2k2k 个 11 反转为 00 ，最后将中间原本为 00 的地方反转为 11 。

于是实现了一一对应。

然后求这个“最简串”直接栈就行。

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
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
string s,t,S,T;
int n,k;
using pii=pair<char,int>;
int top;pii st[N];
void calc(string &s,string &S){
    top=0;
    for(int i=0;i<s.size();i++){
        if(top&&st[top].first==s[i])st[top].second++;
        else st[++top]={s[i],1};
        if(top&&st[top].second==k)--top;
    }
    S.clear();
    for(int i=1;i<=top;i++)S.append(st[i].second,st[i].first);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(cout.tie(0));
    cin>>n>>k>>s>>t;
    calc(s,S),calc(t,T);
    if(S==T)cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}