题解：P15093 [UOI 2025 II Stage] Odd Rows

· · 题解

题意简述

给定 n\times m 的 0/1 矩阵，每列恰有 c_i 个 1，可自由排列每列元素，最大化含奇数个 1 的行数，并输出构造方案。

Solution

首先我们对于 c_i > \frac{n}{2} 的列，整体翻转该列，新 c_i' = n-c_i \le \frac{n}{2}。

翻转一列会使所有行的 1 的个数奇偶性反转，设翻转列数为 F，F 为偶数表明我们要求最大化奇数行；反之则表明要求最大化偶数行。

我们将列按翻转后的 c_i' 从大到小排序，依次处理，对于当前列，维护一个双向链表，存放该列尚未放 1 的行。

接下来考虑贪心：

  1. 遍历链表，如果遇到不满足条件的行则放置 1，更新奇偶性后从链表删除该行，重复直到所需 1 放完或链表中无不满足条件的行。
  2. 若无不满足条件的行但仍有剩余 1，则借用第一列的 1 创造不满足条件的行，找到行 y（第一列为 1）和行 x（第一列为 0），将 1 从 y 挪至 x，两行奇偶性反转，产生不满足条件的行，随后尝试在 x,y 上放当前列的 1，重复至放完。
  3. 若还有剩余，那肯定就满足不了了，随便放即可。

当我们处理完所有列后，将标记为翻转的列再次取反得到正确的构造。

由于每个 1 最多被挪动一次，所以时间复杂度 O(nm)。

Code

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    vector<int>c(m),order(m,0);
    vector<bool>f(m);//该列是否翻转 
    bool F=true;//表示需要统计的是最大奇数行还是最大偶数行 
    for(int i=0;i<m;i++){
        cin>>c[i];
        if(c[i]>n/2){
            c[i]=n-c[i];
            f[i]=true;
            F=!F; 
        }
    }
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int x,int y){return c[x]>c[y];});
    vector<vector<int>>ans(n,vector<int>(m,0));
    vector<bool>czf(n,false);
    for(int id=0;id<m;id++){
        int cur=order[id],ned=c[cur];
        if(!ned)continue;
        vector<int>pre(n),nxt(n);
        for(int i=0;i<n;i++){
            pre[i]=i-1,nxt[i]=i+1;
        }
        nxt[n-1]=-1;
        int l=0;
        auto del=[&](int x){
            if(pre[x]!=-1)nxt[pre[x]]=nxt[x];
            else l=nxt[x];
            if(nxt[x]!=-1)pre[nxt[x]]=pre[x];
        };
        int pos=l;
        while(ned&&pos!=-1){
            if(czf[pos]!=F){//有可以放的直接放 
                ned--;
                ans[pos][cur]=1;
                czf[pos]=!czf[pos];
                int npos=nxt[pos];
                del(pos);
                pos=npos;
            }
            else pos=nxt[pos];
        }
        if(ned){
            int j=order[0];
            stack<int>st;
            pos=l;
            while(ned&&pos!=-1){
                if(ans[pos][j]==1){
                    st.push(pos);
                    pos=nxt[pos];
                }
                else {
                    if(!st.empty()){
                        int x=pos,y=st.top();st.pop();
                        ans[y][j]=0;
                        czf[y]=!czf[y];
                        ans[x][j]=1;
                        czf[x]=!czf[x];
                        if(ned>0){//尝试在x行放当前列的1
                            ans[x][cur]=1;
                            czf[x]=!czf[x];
                            ned--;
                            int npos=nxt[x];
                            del(x);
                            pos=npos;
                        }
                        else pos=nxt[pos];
                        if(ned>0){//尝试在y行放当前列的1
                            ans[y][cur]=1;
                            czf[y]=!czf[y];
                            ned--;
                            del(y);
                        }
                    }
                    else pos=nxt[pos];
                }
            }
        }
        pos=l;//放完剩下的 
        while(ned&&pos!=-1){
            ans[pos][cur]=1;
            czf[pos]=!czf[pos];
            ned--;
            int npos=nxt[pos];
            del(pos);
            pos=npos;
        }
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(czf[i]==F)cnt++;
    }
    cout<<cnt<<'\n';
    for(int j=0;j<m;j++){//还原 
        if(f[j]){
            for(int i=0;i<n;i++){
                ans[i][j]^=1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<'\n';
    }
}