题解：P13214 [GCJ 2015 Qualification] Ominous Omino

· · 题解

怎么莫名其妙比别人快了 1ms 啊，成最优解了。

\Large\text{Solution}

为简化文章，我们先设 \mathbf R\le\mathbf C。

首先排除掉 \mathbf{RC}\not\equiv 0\pmod {\mathbf X} 的情况，显然无法填满。后文中有很多结论都建立在不考虑这种情况的基础上。

有一个比较重要也比较显然的性质，那就是放好要求图形后，当且仅当被分割成的每一个连通块大小都是 \mathbf X 的倍数时有解。

正式开始做。观察题目中给出的图发现 \mathbf X\ge 7 时可以围一个被孤立的块，那就肯定无解了，所以 \mathbf X 的实际范围马上被缩小了，那就可以分讨了。

::::info[\mathbf X\ge 7] 略。 ::::

::::info[\mathbf X=1] 显然永远可以填满。 ::::

::::info[\mathbf X=2] 不难发现只有一种样式，且一定可以填满。 ::::

::::info[\mathbf X=3] 只有两种样式：一排三个和拐一下的三个。\mathbf R=1 时用后者就可以卡掉。否则可以把拐点放在角落，剩下的方格一定连通，所以一定可以铺满。 ::::

::::info[\mathbf X=4]

如果 $\mathbf R=2$，那么可以使用如下两种样式： ``` . . . . . . . . ``` 这样一定会把剩下的格子分成两半且个数都为奇数。所以无解。 $\mathbf R$ 更大的情况可以发现无法分成两个连通块，所以一定可以放满。 :::: ::::info[$\mathbf X=5$] $\mathbf R\le 2$ 的可以构造一个 L 型，长宽都是 $3$，所以可以卡掉。 考虑 $\mathbf R=3$，如果样式可以摆在两行里，那么显然分不断剩下的格子，所以考虑有三列的情况。那么有下面几种： ``` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ``` 由于 $\mathbf X = 5$，我们只考虑 $\mathbf C=5k,k\in \Z^+$ 的情况。容易发现，当上面四个样式摆在 $3\times 5$ 的方格中间时，两边都会刚好空 $5$ 个，所以一定可以放满。而第二行的两个可以通过手玩发现 $\mathbf C=10+5k,k\in \Z^+$ 时才能摆下。 $\mathbf R\ge 4$ 时和上面同理，无法分断。 :::: ::::info[$\mathbf X=6$] 顺着 $\mathbf X=5$ 的情况很容易做出来。 首先去掉 $\mathbf R \le 2$。然后同上考虑 $\mathbf R=3$，可以发现由于把占三行的样式放进去，左右平移两次对两侧模 $6$ 的余数实际上不会影响，所以随便构造一个就永远放不满。 例如： ``` . . . . . . ``` 最后考虑 $\mathbf R=4$，其实容易发现如果只占三行是无法分断其他格子的，而占四行可以直接横过来，就变成三行了，所以永远能放满。那更大的 $\mathbf R$ 也不用管了。 :::: 把上述分讨变成代码即可。完结撒花。 $\Large\text{Code} 
//By _pig_&_buta_
//Ciallo～(∠・ω< )⌒★
//#pragma GCC optimize O(2)
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
#define Testify 2221
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
typedef array <int, 2> arr2;
typedef array <int, 3> arr3;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 1e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;

signed main()
{
    cin.tie (0), cout.tie (0);
    ios :: sync_with_stdio (false);
    int t; cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": "; 
        int x, n, m; cin >> x >> n >> m;
        if (n > m) swap (n, m);
        if (n * m % x) cout << "RICHARD\n";
        else if (x <= 2) cout << "GABRIEL\n";
        else if (x == 3)
        {
            if (n == 1) cout << "RICHARD\n";
            else cout << "GABRIEL\n";
        }
        else if (x == 4)
        {
            if (n <= 2) cout << "RICHARD\n";
            else cout << "GABRIEL\n";
        }
        else if (x == 5)
        {
            if (n <= 2) cout << "RICHARD\n";
            else if (n == 3)
            {
                if (m >= 10) cout << "GABRIEL\n";
                else cout << "RICHARD\n";
            }
            else cout << "GABRIEL\n";
        }
        else if (x == 6)
        {
            if (n <= 3) cout << "RICHARD\n";
            else if (n >= 5) cout << "GABRIEL\n";
            else cout << "GABRIEL\n";
        }
        else cout << "RICHARD\n";
    }
    return 0;
}//Ciallo~(∠·ω<)⌒☆