题解：CF1674F Desktop Rearrangement

Legend_Beaver · 2024-03-30 21:41:18 · 题解

CF1674F

模拟好题

我们可以用预处理的方法出在初始状况下共有多少个 1(cn t)，以及有多少个 1(count) 处于不需要操作的范围内，则最终答案为 cnt−count，由此所有询问可以通过 O(1) 的时间复杂度解决。

主要考虑两个问题：

#include <bits/stdc++.h> //万能头
using namespace std;

char op;
int n, m, q, cnt;
int t[1001][1001];

signed main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> op;
            if (op == '.')
                t[i][j] = 0;
            else
                t[i][j] = 1, cnt++;
        }
    }
    int a = cnt / n;
    int b = cnt % n;
    if (b == 0 && a != 0) {
        a--;
        b = n;
    }
    a++;
    int count = 0;
    for (int j = 1; j < a; j++)
        for (int i = 1; i <= n; i++)
            if (t[i][j])
                count++;
    for (int i = 1; i <= b; i++)
        if (t[i][a])
            count++;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        if (t[x][y]) { //删除操作
            cnt--;
            if (t[b][a])
                count--;
            t[x][y] = 0;
            b--;
            if (b == 0) {
                b = n;
                a--;
            }
            if (y < a || (y == a && x <= b))
                count--;
        } else { //增加操作
            cnt++;
            b++;
            if (b == n + 1) {
                b = 1;
                a++;
            }
            if (t[b][a])
                count++;
            t[x][y] = 1;
            if (y < a || (y == a && x <= b))
                count++;
        }
        cout << cnt - count << endl;
    }
    return 0;
}//完美结束