2 条题解

  • 1
    @ 2026-10-14 9:01:09

    SOLUTION

    题意中赋值即为把某行赋值到某列上。

    首先特判全 00 无解,全 11 无需操作。

    要使某不全为 00 的列变成全 11,一定需要一个全 11 的行。

    于是显然有枚举 i∈[1,n]i \in [1,n] 作为那个全 11 的行,若其非全 11 则设法补全。发现补全第 ii 行需要第 ii 列有 11 存在,其操作次数为 n−∑j∈[1,n]ai,jn-\sum_{j \in [1,n]} a_{i,j},说人话就是这一行 00 的个数。

    有了一个全 11 的行,把整个方阵赋值成 11 的操作次数即为不全为 11 的列的个数,显然前一步不会影响这一步。

    交上去得了 9090 pts,这是为什么?

    HACK

    发现如果第 ii 列没有 11,那就把任意一个有 11 的行赋值过来,次数加一。存在这样的数据,使得一行补全的次数很少,却不直接存在能为其赋值的列。

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    int a[1010][1010];
    int cl[1010];
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n;
        int Fl=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char c;
                cin>>c;
                a[i][j]=c-'0';
                Fl|=a[i][j];
            }
        }
        if(!Fl){
            cout<<"-1\n";
            return 0;
        }
        int sc=0;
        for(int j=1;j<=n;j++){
            int fl=1;
            cl[j]=0;
            for(int i=1;i<=n;i++){
                fl&=a[i][j];
                cl[j]|=a[i][j];
            }
            sc+=1-fl;
        }
        int ans=114514;
        for(int i=1;i<=n;i++){
            int s=0;
            for(int j=1;j<=n;j++){
                s+=1-a[i][j];
            }
            if(s==0) ans=min(ans,sc);
            else if(cl[i]) ans=min(ans,sc+s);
            else ans=min(ans,sc+s+1);//加上本行即可 90->100
        }
        cout<<ans<<'\n';
        return 0;
    }
    

    信息

    ID
    898
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    44
    已通过
    8
    上传者