Connected Component on a Chessboard

Created by LXC on Thu May 9 19:14:39 2024

https://codeforces.com/problemset/problem/1196/E

ranting: 1800

tag: constructive algorithms, implementation

problem

有T组数据

给出一个像国际象棋一样黑白染色的图，点 $(1,1)$ 为白色。
Tips: 其实就是如果点坐标是 $(x,y)$，$x+y$ 为偶时是白色，$x+y$ 为奇时是黑色。

你需要构造连通的含有b个黑点,w个白点的图。

如果无法构造，输出”NO”。

否则，输出”YES”，并在第2~(w+b+1)行输出构造方法，方式是“x y”，表示图上有点坐标为(x,y).

solution

不妨设黑色个数b大于白色w。

那么至少有$\lceil \frac{b-1}{3}\rceil$个白色，除了第一个黑色，剩下每多一个白色可以再增加最多三个黑色。
例如b=10,w=6。可以按照如下构造，

wbwb b b
bwbwbwbw
 b b b 

先构造出三行黑色的位置。并记录各自最右端的位置。

然后先构造第二行的白色个数，确保连通性。剩下的白色可以在一或三行进行填充。

对于白色大于黑色的情况，按照黑色大于白色的情况构造，每个位置向下偏移一位恰好对应。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll b, w;
    cin >> b >> w;
    if (b >= (w+1)/3 && w >= (b+1)/3) {
        cout << "YES\n";
        int mw = w > b;
        if (w > b) {
            swap(w, b);
        }
        int m1 = 0, m2 = 0, m3 = 0;
        vector<pair<int,int>> ans;
        for (int i=0, j=1; i<b; j+=2) {
            if (i++<b) {
                // cout << "2 " << j << "\n";
                ans.emplace_back(2, j);
                m2 = max(m2, j);
            }
            if (i++<b) {
                // cout << "1 " << j+1 << "\n";
                ans.emplace_back(1, j+1);
                m1 = max(m1, j+1);
            }
            if (i++<b) {
                // cout << "3 " << j+1 << "\n";
                ans.emplace_back(3, j+1);
                m3 = max(m3, j+1);
            }
        }
        // cout << m1 << " " << m2 << " " << m3 << endl;
        int cw = 0;
        for (int i=2; cw<w && i<=m2+1; i+=2, cw++) {
            ans.emplace_back(2, i);
        }
        for (int i=1; cw<w && i<=m1+1; i+=2, cw++) {
            ans.emplace_back(1, i);
        }
        for (int i=1; cw<w && i<=m3+1; i+=2, cw++) {
            ans.emplace_back(3, i);
        }
        // cout << ans.size() << " " << w << " " << b << endl;
        // cout << ans << endl;
        for (auto [x, y]:ans) {
            cout << x+mw << " " << y << "\n";
        }
    } else {
        cout << "NO\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}