题解 P6476 【[NOI Online 2 提高组]涂色游戏color】

· · 题解

本题解法同 https://codeforces.com/contest/1260/problem/C

不难发现，出现的较为密集（即p1和p2中的较小值）的颜色才会导致不符合k个方块内不同色的要求。

因此我们假设p1 \le p2（红方块不比蓝方块出现得稀疏），如果不符合，可以将p1和p2换过来，不影响最终答案。

将所有需要涂颜色的方块排在一起后，我们发现红色方块会被一个个的蓝色方块方块隔开。

我们现在所需要考虑的就是在每两个相邻的蓝色方块之间，最多能够有多少个红色方块，并检验这些红色方块的数目有没有大于等于k。

当蓝色方块下一个就是红色方块时，这个区间内的红色方块数目肯定是最多的，因为有最多的空间留给红色方块继续出现。

当\gcd(p1, p2) = 1的时候，一定能找到这样两个编号连续的方块，，因为方块的位置一定对应p1 * x - p2 * y = 1 的解。

此时，我们需要检验的就是\lceil\frac{p_2 - 1}{p1}\rceil \le k - 1。

在这个蓝色方块到下一个蓝色方块之间，有p_2 - 1个空位，而这些空位最多可以塞入\lceil\frac{p_2 - 1}{p1}\rceil个红色方块。因此如果任意两个蓝色方块之间最多只能塞下 k - 1个红色方块，就不会导致出现无聊的填色方案。

而如果\gcd(p1, p2) \ne 1，我们只需要把p1,p2每一个数都除以它们的最大公约数，使得\gcd(p1, p2) = 1，再判断即可，不影响最终结果（因为只是相当于把中间那些没有涂色的方块个数缩了一下），如下图：

这里还需要加特殊判定（我考试的时候也没加，看了讨论帖才发现有必要qwq)。 即k = 1的时候不论如何方案都是无聊的。

代码：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
    {
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c & 15);
        c = getchar();
    }
    return x;
}
long long gcd(long long x, long long y)
{
    return (y == 0) ? x : gcd(y, x % y);
}
int T;
int main()
{
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    T = read();
    while (T--)
    {
        long long p1, p2, k;
        p1 = read();
        p2 = read();
        k = read();
        if (k == 1)
        {
            printf("No\n");
            continue;
        }
        if (p1 > p2) swap(p1, p2);
        long long g = gcd(p1, p2);
        p1 /= g;
        p2 /= g;
        if ((k - 1) * p1 >= p2 - 1)
        {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}