题解归档 - cf2226C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226C
• 本地来源：problems/cf2226C/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/C
• 原始标题：cf2226C - Mental Monumental (Easy Version)

思路

cf2226C - Mental Monumental (Easy Version)

pattern: residue reachability + matching.

claim: a single value x can become residue r after choosing some modulus b>=1 iff either x==r (choose b>x) or x>=2r+1 (choose b=x-r>r). If r<x<=2r, then x-r<=r, so no divisor b of x-r can be greater than r.

To test mex at least k, targets 0..k-1 must be assigned to distinct elements. Reserve one exact occurrence for every target value that already appears. All remaining copies have capacity floor((x-1)/2), meaning they can fill any missing target r<=capacity. Greedily fill missing targets in increasing order with the smallest available capacity that works.

check: binary search k; stress against exhaustive matching on small arrays.

代码

来源：problems/cf2226C/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct BIT{
    int n;
    vector<int> bit;
    void init(int n_){
        n=n_;
        bit.assign(n+1,0);
    }
    void add(int idx,int val){
        for(;idx<=n;idx+=idx&-idx) bit[idx]+=val;
    }
    int sum(int idx) const{
        int res=0;
        for(;idx>0;idx-=idx&-idx) res+=bit[idx];
        return res;
    }
    int kth(int k) const{
        int x=0;
        int pw=1;
        while((pw<<1)<=n) pw<<=1;
        for(int d=pw;d;d>>=1){
            int y=x+d;
            if(y<=n&&bit[y]<k){
                x=y;
                k-=bit[y];
            }
        }
        return x+1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n,mx=0;
        cin>>n;
        vector<int>a(n);
        for(int &x:a){
            cin>>x;
            mx=max(mx,x);
        }
        int lim=max(mx,n)+5;
        vector<int>cnt(lim+1,0),seen;
        for(int x:a){
            if(cnt[x]==0) seen.push_back(x);
            cnt[x]++;
        }
        BIT bit;
        auto can=[&](int k)->bool{
            bit.init(lim+1);
            for(int x:seen){
                int spare=cnt[x];
                if(x<k) spare--;
                if(spare<=0||x==0) continue;
                int cap=(x-1)/2;
                bit.add(cap+1,spare);
            }
            int total=bit.sum(lim+1);
            for(int r=0;r<k;r++){
                if(r<=lim&&cnt[r]>0) continue;
                int before=bit.sum(r);
                if(total-before<=0) return false;
                int pos=bit.kth(before+1);
                bit.add(pos,-1);
                total--;
            }
            return true;
        };
        int lo=0,hi=n+1;
        while(lo+1<hi){
            int mid=(lo+hi)/2;
            if(can(mid)) lo=mid;
            else hi=mid;
        }
        cout<<lo<<"\n";
    }
    return 0;
}