P9622 [ICPC2020 Nanjing R] Ah, Its Yesterday Once More 题解

· · 题解

简化题意

对于给定的 n×m 的方格，0 代表障碍，1 代表袋鼠。有一串随机生成的长为 5×10^4 的指令，仅包含 LRUD 字符，分别表示将所有袋鼠同时向某个方向移动（若能移动，即不经过障碍、不超出方格范围）。现要求构造一个 n×m 方格图，使得对于随机生成的 500 串指令，至少有 125 个满足执行后，所有袋鼠不都在同一个方格。要求构造的袋鼠方格连通、且不含环。

by uid 1001552。

题目解法

一道非常可爱（怕）的题。

尽量用蛇形路径（约 50\% ），如果构造不出来了，就用阶梯型路径（约 75\%），这样可以减少利用率。

对于蛇形路径的解释：

01
10

很明显是 \displaystyle \frac{2}{4}=\frac{1}{2}。

阶梯型路径：

01
11

是 \displaystyle \frac{3}{4}。

拿出纸笔模拟下，就可打出一张表格。

大概率可以过，如果一次过不了，就交两次。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout<<20<<" "<<20<<"\n";
    puts("11111101111101111101");
    puts("10010110010110010111");
    puts("01011011011011011001");
    puts("11101101101101101101");
    puts("10110110110110110110");
    puts("11011011011011011011");
    puts("01101101101101101101");
    puts("10110110110110110111");
    puts("10011011011011011001");
    puts("11101101101101101101");
    puts("10110110110110110110");
    puts("11011011011011011011");
    puts("01101101101101101101");
    puts("10110110110110110111");
    puts("10011011011011011001");
    puts("11101101101101101101");
    puts("10110110110110110110");
    puts("11011011011011011011");
    puts("01001101001101001101");
    puts("11110111110111110111");
}