题解：CF755F PolandBall and Gifts

· · 题解

一个人能收到礼物的条件是：他带了礼物，有人给他带了礼物。

建图 i \to p_i 代表 i 能给 p_i 提供礼物。不难发现原图是多个环。

第二问很好做，不给一个人提供礼物会造成 2 的贡献（i 和 p_i 不能收到礼物）。特别地，长度为奇数的环可以消耗 1 而得到 1 的贡献，这个最后判掉即可。

第一问，在对一个环操作时，第一次操作贡献为 2；第 2\sim len-1 次操作，贡献为 1；第 len 次操作，代价为 0。

由此可见，要用当前的 k 更多的去凑完整的环，问题变为 o_i \in \{0,1\},\sum o_i \times len_i 是否可以凑得 k，典型的多重背包问题，拿二进制拆分和 bitset 优化即可。

代码实现使用了 tarjan 求环。

#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define db double
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f,mod=1e9+7;
const long long INFL=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void chkmax(int &x,int y){x=(x<y)?y:x;}
void chkmin(int &x,int y){x=(x>y)?y:x;}

const int N=1e6+10;
int n,K,a[N];
vint G[N];
int idx,dfn[N],low[N],scc_cnt,scc[N],sz[N],ins[N],stk[N],tp;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    stk[++tp]=u,ins[u]=1;
    for(int v:G[u]){
        if(!dfn[v]){
            tarjan(v);chkmin(low[u],low[v]);
        }
        else if(ins[v]) chkmin(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int x;
        ++scc_cnt;
        do{
            x=stk[tp--];
            ins[x]=0;
            scc[x]=scc_cnt;
            sz[scc_cnt]++;
        }while(x!=u);
    }
}
int ans1,ans2;
int solve2(){
    int x=K,res=0;
    rep(i,1,scc_cnt){
        if(x-sz[i]/2>0){
            x-=sz[i]/2,res+=floor(sz[i]/2.0)*2;
        }
        else{
            res+=x*2;return res;
        }
    }
    rep(i,1,scc_cnt){
        if(sz[i]&1){
            --x,res+=1;
            if(!x) return res;
        }
    }
    return res;
}

int solve1(){
    umap<int,int> cnt;
    bitset<N> f;
    rep(i,1,scc_cnt){
        ++cnt[sz[i]];
    }
    vint x;
    x.reserve(cnt.size());
    for(auto [v,c]:cnt){
        int k=1;
        while(c){
            if(c<=k){
                x.push_back(v*c);break;
            }
            x.push_back(v*k);
            c-=k;k*=2;
        }
    }
    f[0]=1;
    for(auto v:x){
        f|=(f<<v);
    }
    return f[K]?K:K+1;
}
int main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n>>K;
    rep(i,1,n) a[i]=read(),G[i].push_back(a[i]);
    rep(i,1,n) if(!dfn[i]) tarjan(i);
    ans1=solve1(),ans2=solve2();
    cout<<ans1<<" "<<ans2<<endl;
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}