Connected Component on a Chessboard

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。可以按照如下构造,

1
2
3
wbwb b b
bwbwbwbw
b b b

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

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

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

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#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;
}