Codeforces 1138B（列方程枚举）

佚名 6年前 (2019-04-12) 随笔 902人围观抢沙发百度已收录

构造模拟要分情况讨论感觉不是够本质，然后官解是因为只有四个量所以可以根据限制条件列两个方程，再枚举一下解就可以了。

const int maxn = 5000 + 5;
int n, c[maxn], a[maxn];
vector<int> zero, two, cl, ac, ans1, ans2;

int main() {
    cin >> n;
    getchar();
    rep(i, 1, n) {
        char ch = getchar();
        c[i] = ch - '0';
    }
    getchar();
    rep(i, 1, n) {
        char ch = getchar();
        a[i] = ch - '0';
    }
    rep(i, 1, n) {
        if (c[i] && a[i])   two.push_back(i);
        else if (c[i])  cl.push_back(i);
        else if (a[i])  ac.push_back(i);
        else    zero.push_back(i);
    }
    
    for (int a = 0; a <= zero.size(); a++) {
        int d = a - n / 2 + ac.size() + two.size();
        if (d < 0 || d > two.size() || a + d > n / 2)   continue;
        int tmp = n / 2 - a - d;
        for (int c = 0; c <= cl.size(); c++) {
            if (tmp - c <= ac.size()) {
                for (int i = 0; i < a; i++) cout << zero[i] << " ";
                for (int i = 0; i < tmp - c; i++)   cout << ac[i] << " ";
                for (int i = 0; i < c; i++) cout << cl[i] << " ";
                for (int i = 0; i < d; i++) cout << two[i] << " ";
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}