CF1674F

DDF_ · 2025-10-02 11:17:51 · 题解

不给样例解释是这题最大的恶意。

题面

一个矩阵包含 "*" 和 "."。每次修改一个位置的状态，将其取反（"*" 变成 "."，"." 变成 "*"），问将所有 "*" 排到左侧的最小代价（类似你在桌面上自动排列图标）。

有 q 次修改，对于每个修改都要求最小代价。

题解

统计 "*" 的数目，可以直接求出目标状态。

贪心去想，与目标状态匹配的 "*" 留着不动，不匹配的移动过去是最小代价。

然后可以提前预处理出初始状态下与目标状态不匹配的 "*" 个数。

接着，对于每次修改，可以发现它会影响 "*" 的数目 cnt，取反一个点 cnt 要么 +1 要么 -1。

分讨。

• 如果 cnt 要 -1（也就是 "*" 变成 "."），那如果修改前目标状态的最后一个 "*" 与原状态匹配，那么 cnt \larr cnt-1 后这个点就在目标状态外了，答案 +1；如果修改的点在目标状态外，则答案 -1。注意会有修改目标状态最后一个 "*" 的位置的情况。
• 如果 cnt 要 +1（也就是 "." 变成 "*"），那如果修改前目标状态第一个 "." 与原状态不匹配，那么此时原状态的这个 "*" 就在目标状态内了，答案 -1；如果修改的点目标状态外，则答案 +1。注意会有修改目标状态第一个 "." 的位置的情况。

此题结。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int q,n,m;
int cnt,ans;
char a[1005][1005];
inline int calx(int cnt) {
    if(cnt%n==0) return n;
    return cnt%n;
}
inline int caly(int cnt) {
    return (cnt+n-1)/n;
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) {
        cin>>(a[i]+1);
        for(int j=1;j<=m;j++) if(a[i][j]=='*') cnt++;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if((a[i][j]=='*')&&(j>caly(cnt)||(j==caly(cnt)&&i>calx(cnt)))) ans++;
        }
    }
    while(q--) {
        int x,y;
        scanf("%d%d",&x,&y);
        if(a[x][y]=='*') {
            a[x][y]='.';
            if(a[calx(cnt)][caly(cnt)]=='*') ans++;
            if((y>caly(cnt))||(y==caly(cnt)&&x>calx(cnt))) ans--;
            cnt--;
        }
        else {
            cnt++;
            if(a[calx(cnt)][caly(cnt)]=='*') ans--;
            if((y>caly(cnt))||(y==caly(cnt)&&x>calx(cnt))) ans++;
            a[x][y]='*';
        }
        printf("%d\n",ans);
    }
    return 0;
}