CF1196E

FiraCode · 2024-01-06 12:58:21 · 题解

思路：

首先有一个性质，就是我们选中一个颜色后，在选另一个颜色，最多能解锁 3 个当前颜色，证明很简单，首先最多是四个，然后若是 4 的的话那么说明那个颜色与当前块不连通，所以至多三个。

由于矩形很大，于是可以考虑横着构造，若不够则在两边再选即可。

复杂度 O(Tn)。

Code：

#include <bits/stdc++.h>

using namespace std;

int T;
int x, y;

int main() {
    scanf("%d", &T);

    while (T--) {
        scanf("%d%d", &x, &y);
        if (3 * x + 1 < y || 3 * y + 1 < x) puts("NO");
        else {
            puts("YES");
            if (x == y) {
                int X1 = 100000, Y1 = 100000;
                for (int i = 1; i <= y; ++i) {
                    printf("%d %d\n", X1, Y1);
                    printf("%d %d\n", X1, Y1 + 1);
                    Y1 += 2;
                }
            } else if (x > y) {
                printf("%d %d\n", 100000, 100001);
                int X1 = 100000, Y1 = 100002;
                int tmp = max(0, x - y - 1);
                for (int i = 1; i <= y; ++i) {
                    printf("%d %d\n", X1, Y1);
                    printf("%d %d\n", X1, Y1 + 1);
                    if (tmp) {
                        printf("%d %d\n", X1 + 1, Y1);
                        --tmp;
                    }
                    if (tmp) {
                        printf("%d %d\n", X1 - 1, Y1);
                        --tmp;
                    }
                    Y1 += 2;
                }
            } else {
                printf("%d %d\n", 100000, 100000);
                int X1 = 100000, Y1 = 100001;
                int tmp = max(0, y - x - 1);
                for (int i = 1; i <= x; ++i) {
                    printf("%d %d\n", X1, Y1);
                    printf("%d %d\n", X1, Y1 + 1);
                    if (tmp) {
                        printf("%d %d\n", X1 - 1, Y1);
                        --tmp;
                    }
                    if (tmp) {
                        printf("%d %d\n", X1 + 1, Y1);
                        --tmp;
                    }
                    Y1 += 2;
                }
            }
        }
    }
    return 0;
}