Codeforces Round 712 (Div. 1) - B. 3-Coloring

Solost

2023 年 04 月 20 日

473 次浏览

暂无评论

1238字数

题目题解

## 题目

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F20%2Fimage.png)

## 题目链接

[链接](https://codeforces.com/contest/1503/problem/B)

## 题目大意

题目意思是给你一个你n * n的棋盘，你有三种棋子，每次给你一种棋子，你不能放这种棋子这次，放的棋子相邻不相同，问你怎么放，每次输出放的棋子种类和位置

## 题解

刚开始的想法是直接暴力找，然后超时，然后用vector存起来每次没有使用过的位置，在判断相邻的有没有相同的棋子，然后超空间。最后看了别人的题解。思路是把间隔的格子位置分别存起来》也就是`i + j & 1`这就是间隔的格子，就跟国际象棋一样的格子。假设白的格子是a,黑的是b,给你一个棋子，如果是本次不让放1棋子，我们就往b放2棋子，反之往a放1棋子，如果有一种格子放完了，例如说白色格子用完了，那我们就往黑色格子放2，3。黑色格子用完了就放1，3，然后就可以达到相邻不相同的目的。因为总有一种格子全部是1或者全部是2，剩下没用完的就是2，3，或者1，3，所以可以达到目的。

上代码：

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 110;

pii a[N * N], b[N * N];

void solve()
{
    int n;
    cin >> n;
    int l1 = 0, l2 = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i + j & 1) {
                a[++l1] = { i, j };
            } else {
                b[++l2] = { i, j };
            }
        }
    }
    int x;
    for (int i = 1; i <= n * n; i++) {
        cin >> x;
        if(!l1){
            cout << (x == 2 ? 3 : 2) << " " << b[l2].x << " " << b[l2].y << endl;
            l2--;
            continue;
        }
        if(!l2){
            cout << (x == 1 ? 3 : 1) << " " << a[l1].x << " " << a[l1].y << endl;
            l1--;
            continue;
        }
        if(x == 1){
            cout << 2 << " " << b[l2].x << " " << b[l2].y << endl;
            l2--;
        }
        else{
            cout << 1 << " " << a[l1].x << " " << a[l1].y << endl;
            l1--;
        }
    }
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 20 日