526互联

Pinely Round 2 (Div. 1 + Div. 2)

发布时间 2023-08-31 18:45:11作者: north_h

Pinely Round 2 (Div. 1 + Div. 2) - Codeforces

A Channel

题意：总共有\(n\)个人，最开始有\(a\)个人在线上，再给你\(q\)次消息，每次消息\(+\)表示上线,\(-\)表示下线，每次上线都会读报，如果一定能够保证\(n\)个人都度过报输出\(YES\)，如果一定不能够保证\(n\)个人都度过报输出\(NO\)，剩下情况输出\(MAYBE\)

思路：只要同时在线的人数大于等于\(n\)就输出\(YES\)，如果\(+\)的数量加上原来在线的人数都不大于等于\(n\)，就输出\(NO\)，否则输出\(MAYBE\)

void solve() {
    int n, a, q;
    cin >> n >> a >> q;
    string s;
    cin >> s;
    int x = a, y = 0;
    int ans = x;
    for(auto i : s) {
        if(i == '+') {
            y++;
            x++;
            ans = max(ans, x);
        } else x--;
    }
    if(ans >= n)cout << "YES" << endl;
    else if(a + y < n)cout << "NO" << endl;
    else cout << "MAYBE" << endl;

}

B Split Sort

题意：给一个\(n\)的排列，问最少通过几次一下操作，将这个排列还原为升序的，操作：选择一些 \(x\) (\(2 \le x \le n\))，创建一个新的排列组合，首先，写下 \(p\) 中所有小于 \(x\) 的元素，但不改变它们的顺序；第二，写下 \(p\) 中大于或等于 \(x\) 的所有元素，但不改变它们的顺序，用新创建的排列替换 \(p\)。

思路：通过找规律可以发现，\(6,5,4,3,2,1的还原步骤：选6->5,4,3,2,1,6，选5->4,3,2,1,5,6\), \(选4->3,2,1,4,5,6，选3-2,1,3,4,5,6,选2->1,2,3,4,5,6\)需要5步，也就是说只要在给的排列中较大那个数的位置在较小那个数的为值的后面，就不用操作，二我们最多只会操作\(n-1\)次，所以当我们遇见上面的情况的时候，就将操作次数减一即可

void solve() {
    int n;
    cin >> n;
    map<int, int> ump;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        ump[x] = i;
    }
    int ans = n - 1;
    // for(auto [x, y] : ump) {
    //     cout << x << ' ' << y << endl;
    // }
    for(int i = n; i > 1; i--) {
        if(ump[i] > ump[i - 1])ans--;
    }
    cout << ans << endl;
}

C MEX Repetition

题意：给你一个数组 \(a_1,a_2,\ldots,a_n\)，它是由 \(0\) 到 \(n\) 之间个成对的不同整数组成的。请考虑以下操作：依次将 \(a_i\) 替换为 \(\operatorname{MEX}(a_1, a_2, \ldots,a_n)\),问经过\(k\)次这样操作的数组变成什么样，输出操作后的数组

思路：找规律可以发现，经过\(n+1\)操作数组又变回原来的样子，所以这是一个以\(n+1\)为周期的循环，而且发现每次操作的是指就是把最后一个数字删除，在数组的首加上 \(\operatorname{MEX}(a_1, a_2, \ldots,a_n)\)，其实这个值就是上一次被删了的数，所以总的复杂度是\(O(n)\)，我直接就用\(vector\)做的，也可以用双端队列

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto &i : a)cin >> i;
    int ans = 0;
    vector<int> b = a;
    sort(ALL(b));
    for(auto i : b) {
        ans += (i == ans);
    }//求最开始时候的MEX
    reverse(ALL(a));
    int cnt = k % (n + 1);
    for(int i = 0; i < cnt; i++) {
        a.push_back(ans);
        ans = a[i];
    }
    reverse(ALL(a));
    for(int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
}

D Two-Colored Dominoes

题意：给一个由\(.\)\(L\)\(R\)\(U\)\(D\)组成的二维数组，问你能否把它在出\(.\)的地方图上白色或黑色，使得每一行并且每一列的白色和黑色相等，如果不行输出\(-1\)

思路：我们发现，横着的多米诺骨牌，对每一行的白色和黑色数量关系没有影响，竖着的多米诺骨牌，对每一列的白色和黑色数量关系没有影响，所以，对于每一行我们只考虑竖着的（也就是\(U\)\(D\)），对于每一列我们只考虑横着的（也就是\(L\)\(R\)）

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    vector<vector<char>> b(n, vector<char>(m, '.'));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        int res = 0;
        vector<int> ans;
        for(int j = 0; j < m; j++) {
            if(a[i][j] == 'U' ) {
                res++;
                ans.push_back(j);
            }
        }
        if(res % 2 != 0) {
            cout << -1 << endl;
            return ;
        }
        for(int j = 0; j < ans.size() / 2; j++)b[i][ans[j]] = 'B', b[i + 1][ans[j]] = 'W';
        for(int j = ans.size() / 2; j < ans.size(); j++)b[i][ans[j]] = 'W', b[i + 1][ans[j]] = 'B';
    }
    for(int j = 0; j < m; j++) {
        int res = 0;
        vector<int> ans;
        for(int i = 0; i < n; i++) {
            if(a[i][j] == 'L') {
                res++;
                ans.push_back(i);
            }
        }
        if(res % 2 != 0) {
            cout << -1 << endl;
            return ;
        }
        for(int i = 0; i < ans.size() / 2; i++)b[ans[i]][j] = 'B', b[ans[i]][j + 1] = 'W';
        for(int i = ans.size() / 2; i < ans.size(); i++)b[ans[i]][j] = 'W', b[ans[i]][j + 1] = 'B';
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << b[i][j];
        }
        cout << endl;
    }
}