题解 | 牛客周赛 Round 135

A. Add Three

每次只能加 $3$ ，所以最后是不超过 $n$ 的一个 $3$ 的倍数。

void solve(){
    int n;cin>>n;
    cout<<n/3*3<<endl;
}

B. Maximize The Count

条件 $p_{i+1}-p_i = a_{p_{i+1}}-a_{p_i}$ 等价于选出来的位置满足 $a[p]-p$ 都相同。于是把每个位置的 $a[i]-i$ 统计频次，出现次数最多的那组就是最长答案。

void solve(){
    int n;cin>>n;
    vi cnt(2*n+5);
    int ans=0;
    for(int i=1;i<=n;++i){
        int x;cin>>x;
        int v=x-i+n;
        ++cnt[v];
        ans=max(ans,cnt[v]);
    }
    cout<<ans<<endl;
}

C. Permutation Swapping

当 $n\ge4$ 时，不相邻交换已经足够“灵活”，任意排列都能还原成升序，所以一定是 YES。剩下就是特判： $n=1$ 一定行， $n=2$ 只有本来有序才行， $n=3$ 只有中间位置必须已经是 $2$ 才行。

void solve(){
    int n;cin>>n;
    vi p(n+1);
    for(int i=1;i<=n;++i)cin>>p[i];
    if(n==1){
        cout<<"YES"<<endl;
        return;
    }
    if(n==2){
        cout<<(p[1]==1&&p[2]==2?"YES":"NO")<<endl;
        return;
    }
    if(n==3){
        cout<<(p[2]==2?"YES":"NO")<<endl;
        return;
    }
    cout<<"YES"<<endl;
}

D. Two Options

设最终都变成 $x$ ，至少要做 $\sum_{i=1}^n \max(0,x-a_i)$ 次（每次最多让一个位置 +1）。取 $x=\left\lceil\frac{\sum a_i}{n}\right\rceil$ 时这个值最小，所以答案是 $\sum_{i=1}^n \max\!\left(0,\left\lceil\frac{\sum a_i}{n}\right\rceil-a_i\right)$ 。

void solve(){
    int n;cin>>n;
    vll a(n);
    ll s=0;
    for(int i=0;i<n;++i){
        cin>>a[i];
        s+=a[i];
    }
    ll x=s/n;
    if(s>0&&s%n)x++;
    ll ans=0;
    for(int i=0;i<n;++i){
        if(a[i]<x)ans+=x-a[i];
    }
    cout<<ans<<endl;
}

E. Not Equal

这是线性 DP：设每个位置最终值为 $x$ ，代价是改到 $x$ 的花费，且只要求和前一个位置不同。每个点只需要枚举 $a[i]-2$ 到 $a[i]+2$ 这 $5$ 个候选值，做“当前位置候选 $×$ 上一位置候选”的最小转移即可。

void solve(){
    int n;cin>>n;
    vll a(n),b(n),c(n);
    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=0;i<n;++i)cin>>b[i];
    for(int i=0;i<n;++i)cin>>c[i];
     
    vvll p(n);
    for(int i=0;i<n;++i){
        for(ll x=max(1LL,a[i]-2);x<=a[i]+2;++x)p[i].push_back(x);
    }
     
    auto cost=[&](int i,ll x)->ll{
        if(x>=a[i])return (x-a[i])*b[i];
        return (a[i]-x)*c[i];
    };
     
    vll f(p[0].size());
    for(int i=0;i<(int)p[0].size();++i)f[i]=cost(0,p[0][i]);
     
    for(int i=1;i<n;++i){
        vll g(p[i].size(),LINF);
        for(int j=0;j<(int)p[i].size();++j){
            ll w=cost(i,p[i][j]);
            for(int k=0;k<(int)p[i-1].size();++k){
                if(p[i][j]!=p[i-1][k]){
                    g[j]=min(g[j],f[k]+w);
                }
            }
        }
        f.swap(g);
    }
    cout<<*min_element(all(f))<<endl;
}

F. Alone

按“每个格子作为孤立点的贡献”来算总和，最后只有两类会贡献：一种是预设黑点里本身行列计数都为 $1$ 的点，另一种是“空行 × 空列”形成的点。两类分别乘上其余自由格子的 $2$ 的幂方案数，相加取模就是答案。

ll qpow(ll a,ll b,ll mod=MOD){
    ll res=1;
    a%=mod;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void solve(){
    ll n,m;int k;cin>>n>>m>>k;
    vpii p(k);
    unordered_map<int,int> rc,cc;
    rc.reserve(k*2+10);
    cc.reserve(k*2+10);
    for(int i=0;i<k;++i){
        int x,y;
        cin>>x>>y;
        p[i]={x,y};
        ++rc[x];
        ++cc[y];
    }
    ll a=0;
    for(auto &e:p){
        if(rc[e.fi]==1&&cc[e.se]==1)++a;
    }
    ll zr=n-(ll)rc.size();
    ll zc=m-(ll)cc.size();
    ll b=zr*zc;
    ll f=n*m-k;
    ll ans=0;
    if(a){
        ll e=f-n-m+2;
        ans=(ans+a%MOD2*qpow(2,e,MOD2))%MOD2;
    }
    if(b){
        ll e=f-n-m+1;
        ans=(ans+b%MOD2*qpow(2,e,MOD2))%MOD2;
    }
    cout<<ans<<endl;
}