牛客多校6 G.Grid Coloring【构造】

做法：在注意到n==1,k==1,和无法让所有边均分颜色这几种情况无解后，因为横竖边数量的奇偶性不同，所以直接一排横一排竖地按（1~k）的顺序给每条边标号（染色）就能保证条件123同时成立

CODE

 1 #include <bits/stdc++.h>
 2 #define dbug(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5  
 6 using namespace std;
 7 typedef long long LL;
 8  
 9 const int inf = 0x3f3f3f3f;
10  
11 template<class T>inline void read(T &res)
12 {
13    char c;T flag=1;
14    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
15    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
16 }
17 
18 const int maxn = 207;
19 
20 int t, n, k;
21 
22 vector<int> l[maxn], r[maxn];
23 
24 int main()
25 {
26     read(t);
27     while(t--) {
28         read(n); read(k);
29         if(k == 1 || n == 1) {
30             puts("-1");
31             continue;
32         }
33         int num = (n * (n + 1)) * 2;
34         if(num % k) {
35             puts("-1");
36             continue;
37         }
38         for ( int i = 1; i <= n + 1; ++i ) {
39             l[i].clear();
40             r[i].clear();
41         }
42         int kk = 1;
43         int L = 0;
44         for ( int i = 1; i <= n + n + 1; ++i ) {
45             if(i % 2) {
46                 ++L;
47                 for ( int j = 1; j <= n; ++j ) {
48                     l[L].push_back(kk);
49                     kk++;
50                     if(kk > k) {
51                         kk = 1;
52                     }
53                 }
54             }
55             else {
56                 for ( int j = 1; j <= n + 1; ++j ) {
57                     r[j].push_back(kk);
58                     kk++;
59                     if(kk > k ) {
60                         kk = 1;
61                     }
62                 }
63             }   
64         }
65         for ( int i = 1; i <= L; ++i ) {
66             for(auto it : l[i]) {
67                 cout << it << ' ';
68             }
69             puts("");
70         }
71         for ( int i = 1; i <= n + 1; ++i ) {
72             for(auto it : r[i]) {
73                 cout << it << ' ';
74             }
75             puts("");
76         }
77     }
78     return 0;
79 }