P15093 [UOI 2025 II Stage] Odd Rows Solution

Ptll · 2026-04-17 15:01:09 · 题解

题解

不难想到这是一个我为人人的 DP，我们定义 f_{i,j} 表示对于前 i 列能否做到其中有且仅有 j 行存在奇数个 1。

我们发现对于 f_{i,j} 它所能转移到的位置是一个区间，并且这个区间中只有奇数或者偶数能被修改，这提示我们可以拿一颗线段树来维护 f_{i+1,x}。

答案显然是所有的 f_{m,j} = 1 中 j 的最大值，这样你可以获得 50pts。

我们考虑答案的构造，我们需要知道当第 i 列构造完了有多少行包含奇数个 1，我们发现，对于这个是好维护的，倒着再模拟整个过程一次就可以了。

考虑记录第 i 列结束后有 g_i 个位置包含奇数个 1，那对于第 i 列，我们考虑它相较于第 i-1 列多出现了几个位置包含奇数个 1（记为 p）。

我们发现，对于剩下的值即 c_i - p 均匀的覆盖包含和不包含奇数个 1 的位置即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef int ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e6+5,mod=1e9+7,inf=2e9;
const ld eps=1e-6;
ll n,m,a[N],g[N];
bool vis[N];
struct Segtree {
    ll t[N<<1],lt[N<<1];
    // Segtree() {
    //     memset(lt,-1,sizeof(lt));
    // }
    inline void push_up (ll pos) {
        t[pos]=t[pos<<1]+t[pos<<1|1];
    }
    inline void push_down (ll pos,ll l,ll r) {
        if (lt[pos]==-1) {
            return ;
        }
        ll mid=(l+r)>>1;
        t[pos<<1]=lt[pos]*(mid-l+1);
        t[pos<<1|1]=lt[pos]*(r-mid);
        lt[pos<<1]=lt[pos];
        lt[pos<<1|1]=lt[pos];
        lt[pos]=-1;
    }
    void add (ll pos,ll l,ll r,ll L,ll R,bool val) {
        if (L<=l&&r<=R) {
            t[pos]=val*(r-l+1);
            lt[pos]=val;
            return ;
        }
        push_down(pos,l,r);
        ll mid=(l+r)>>1;
        if (L<=mid) {
            add(pos<<1,l,mid,L,R,val);
        }
        if (R>mid) {
            add(pos<<1|1,mid+1,r,L,R,val);
        }
        push_up(pos);
    }
    ll query (ll pos,ll l,ll r,ll L,ll R) {
        if (L<=l&&r<=R) {
            return t[pos];
        }
        push_down(pos,l,r);
        ll mid=(l+r)>>1,cnt=0;
        if (L<=mid) {
            cnt+=query(pos<<1,l,mid,L,R);
        }
        if (R>mid) {
            cnt+=query(pos<<1|1,mid+1,r,L,R);
        }
        return cnt;
    }
} tr[2][2];
inline void solve () {
    n=read(),m=read();
    for (ll i=1;i<=m;i++) {
        a[i]=read();
    }
    vector<vector<bool>> f(m+5,vector<bool>(n+5)),ans(n+5,vector<bool>(m+5));
    for (ll i=0;i<=m;i++) {
        for (ll j=0;j<=n;j++) {
            f[i][j]=ans[j][i]=0;
        }
    }
    ll ql=n>>1,pl=n-ql;
    tr[0][0].add(1,0,ql,0,0,1);
    for (ll i=0;i<m;i++) {
        tr[(i+1)&1][0].add(1,0,ql,0,ql,0);
        tr[(i+1)&1][1].add(1,0,pl,0,pl,0);
        for (ll j=0;j<=n;j++) {
            ll l=abs(j-a[i+1]),r;
            if (j+a[i+1]<=n) {
                r=j+a[i+1];
            }
            else {
                r=(n<<1)-(j+a[i+1]);
            }
            if (l>r) {
                continue;
            }
            ll kl=(j>>1);
            if (j&1) {
                kl++;
                if (tr[i&1][1].query(1,0,pl,kl,kl)) {
                    ll sl=(l>>1),sr=(r>>1);
                    if (l&1) {
                        sl++;
                        sr++;
                    }
                    f[i][j]=1;
                    tr[(i+1)&1][l&1].add(1,0,(l&1?pl:ql),sl,sr,1);
                }
            }
            else {
                if (tr[i&1][0].query(1,0,ql,kl,kl)) {
                    ll sl=(l>>1),sr=(r>>1);
                    if (l&1) {
                        sl++;
                        sr++;
                    }
                    f[i][j]=1;
                    tr[(i+1)&1][l&1].add(1,0,(l&1?pl:ql),sl,sr,1);
                }
            }
        }
    }
    ll mx=0;
    for (ll i=n;i>=0;i--) {
        ll kl=i>>1;
        if (i&1) {
            kl++;
        }
        if (tr[m&1][i&1].query(1,0,(i&1?pl:ql),kl,kl)) {
            mx=i;
            break;
        }
    }
    print(mx);
    puts("");
    for (ll i=m;i>=1;i--) {
        g[i]=mx;
        for (ll j=0;j<=n;j++) {
            ll l=abs(j-a[i]),r;
            if (j+a[i]<=n) {
                r=j+a[i];
            }
            else {
                r=(n<<1)-(j+a[i]);
            }
            if (!f[i-1][j]) {
                continue;
            }
            if (l>r) {
                swap(l,r);
            }
            if (l<=mx&&mx<=r&&(mx&1)==(l&1)) {
                mx=j;
                break;
            }
        }
    }
    ll lt=0;
    for (ll i=1;i<=m;i++) {
        ll num=g[i]-g[i-1];
        ll val,wl;
        wl=val=(a[i]-num)>>1;
        val+=num;
        for (ll j=1;j<=n;j++) {
            if (vis[j]) {
                if (wl) {
                    wl--;
                    vis[j]=0;
                    ans[j][i]=1;
                }
            }
            else {
                if (val) {
                    val--;
                    vis[j]=1;
                    ans[j][i]=1;
                }
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            print(ans[i][j]);
            putchar(' ');
        }
        puts("");
    }
}
int main () {
    // freopen("oddrows.in","r",stdin);
    // freopen("oddrows.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}
/*
*/