题目链接

C. Balance the Bits（构造）

题意：

t组测试，每次给你一个长度为n的01序列a。要求你给出两个只由 ( 和 )组成的等长字符串s1，s2，满足下列条件：

• 如果01序列中a[i] == 1，则s1[i]==s2[i],否则s1[i]!=s2[i]，即括号反向。
• 要求s1，s2中的括号是可以相互匹配的，如(())、(()())都是匹配的，但是)(、()))都是不匹配的。

要求你找到这样的一组字符串，如果不存在输出NO。

分析：

首先我们可以推得：0和1的个数都必须是偶数个，否则直接输出NO。接着向下思考，如果只看0，我们发现如果偶数个0可以用如下的方式进行构造：

000000
()()()
)()()(

这样的方式使得其中一行的括号是完全匹配的，另外一行的括号内部匹配，左右各有一个不匹配。那么只要左右存在一个1即可，如下构造：

10000001
(()()())
()()()()

这样就都满足要求了，如果0之间还交错着1的话，由于是偶数个，只要将1分成左右两半，左边的都为'(‘,右边的都为’)’即可，如下：

111111//如果只看0
((()))
101001011001//01交错举例
()(()(()))()
((()(()))())

按照上述构造一定是万无一失的，接下来的问题就是如果只有0或者最左端的0的左边没1，或者最右边的0右边没1能不能构造出来，这只要自己举几个例子就能证明，因为只有01两种情况，穷举一下就行，不做证明。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int id[maxn];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0')
                id[i] = x++;
            else
                id[i] = y++;
        }
        if (x % 2 == 0 && y % 2 == 0 && s[0] == '1' && s[n - 1] == '1') {
            puts("YES");
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') {
                    if (id[i] % 2 == 0)
                        cout << ')';
                    else
                        cout << '(';
                } else {
                    if (id[i] < y / 2)
                        cout << '(';
                    else
                        cout << ')';
                }
            }
            puts("");
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') {
                    if (id[i] % 2 == 0)
                        cout << '(';
                    else
                        cout << ')';
                } else {
                    if (id[i] < y / 2)
                        cout << '(';
                    else
                        cout << ')';
                }
            }
            puts("");
        } else
            puts("NO");
    }
    return 0;
}

D. 3-Coloring(构造)

题意：

交互题。先输入n，表示有一个n*n的棋盘，有1,2,3三种颜色。每次评测机告诉你一个颜色a，你可以用除了a以外的颜色去给棋盘染色，要求不能重复染色，并且相邻的格子颜色都不同，输出你选择的颜色和格子的坐标，进行n*n次，即将棋盘全部染色。坐标从1开始。

分析：

我们先规定1和2只能按下面的方式进行染色：

1212
2121
1212
2121

12121
21212
12121
21212
12121

即，假设坐标为i，j,那么(i+j)%2==1的染2，否则染1。

那么每次评测机给出的数字可能有：

• 给出1：可以选择颜色2或3
  • 如果2有空余位置，则在2的下一个位置染2。
  • 否则在染1的下一个位置染3。
• 给出2：可以选择颜色1或3。
  • 如果1有空余位置，则在1的下一个位置染1。
  • 否则在染2的下一个位置染3。
• 给出3：可以选择颜色1或2，若1剩余的多则染1，否则染2。

这样，全部的可能都安排妥当，再来看一下准确性：
首先，预处理的12交错染色的方式肯定是符合要求的，所以如果可以染1和2则按位置顺序染下来，但是实际可以染1和2的数量可能不同，就造成1可以染的所有位置都染上了，但是还要染1的情况，那么此时就在2空余的地方染3，由于1都染了，所以接下来染3也不会出现违背题意的情况（2满了的情况也类似）。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
vector<PII> vec[2];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            vec[(i+j)%2].push_back({i,j});
        }
    }
    int t = n*n;
    while(t--) {
        int op;
        cin >> op;
        if(op == 1) {
            if(vec[1].size()) {
                printf("2 %d %d\n",vec[1].back().first,vec[1].back().second);
                vec[1].pop_back();
            }else {
                printf("3 %d %d\n", vec[0].back().first, vec[0].back().second);
                vec[0].pop_back();
            }
        }
        else if(op == 2) {
            if(vec[0].size()) {
                printf("1 %d %d\n",vec[0].back().first,vec[0].back().second);
                vec[0].pop_back();
            }else {
                printf("3 %d %d\n", vec[1].back().first, vec[1].back().second);
                vec[1].pop_back();
            }
        }
        else {
            if(vec[0].size() < vec[1].size()) {
                printf("2 %d %d\n", vec[1].back().first, vec[1].back().second);
                vec[1].pop_back();
            }
            else {
                printf("1 %d %d\n", vec[0].back().first, vec[0].back().second);
                vec[0].pop_back();
            }
        }
    }
    return 0;
}