题解：CF755F PolandBall and Gifts

· · 题解

CF755F PolandBall and Gifts 题解

\text{Description}

有 n 人要互相送礼物，用全排列 p 表示：第 i 个人要把礼物送给第 p_i 个人（p_i\ne i）。

有 k 个人会忘记带礼物，但是我们不知道这些人是谁。一个人能收到礼物，当且仅当她带了礼物，并且应该送给她礼物的人也带了礼物。

给定 p,k，对于所有 k 个人没带礼物的情况，求最少、最多有多少人不能收到礼物。

\text{Solution}

需要用到的算法：

  1. 图上找环。

  2. 贪心。

  3. 多重背包。

模拟一下样例，容易想到：送礼物，就是连边。

仔细观察，我们发现图不一定联通，会形成一个个环。

接着，我们来考虑：最多有多少人不能收到礼物。

Part 1：最大值

我们发现：一个人忘带礼物，会导致他自己和他想送的那个人都得不到礼物，即一个人会影响两个人。

也就是说，我们想让最多人不能收到礼物，那就是让影响别人的人尽量不被影响。

在图上说，就是对一条线段的两端点染色后，希望被染色的点不被二次染色。

也就是说，我们现在有了贪心策略：

第一次循环，尽量染尽可能多的点。具体的，在奇环里，留下一个点不染色，因为要染上它，就会导致另一个点二次染色。

如果循环后，还可以继续染，那就找到之前留下的奇环落单的，染上它。

至于怎么判断还能不能染，看文末代码，这里不好叙述。

Part 2：最小值

我们继续贪心。

在最大值里，我们是想要让一条染色边尽可能染上未被染色的点。

所以，在这里，一条染色边尽可能染上被染色的点。

具体的，每条染色边，都从已染色的点开始，尽可能拓展到另一个被染色的点，形成一个环。

也就是说，每个染色点，要引出 2 条染色边。更进一步的，我们希望所有染色边，构成几个完整的环。

换句话说，我们想知道对于已定的环，能否找到几个环，使这几个环点的个数和等于 k。

如果存在，最小值就为 k；否则，会构成几个环与一条链，最小值为 k+1。

那这就是很典的背包了：知道一个数列，问能否保留其中一些数，使它们的和为 k。

这里采用 01 背包加 bitset 优化，例题：P1776 宝物筛选。

\text{Code} 
#include<bits/stdc++.h>
using namespace std;

#define N 1000005
int n,k,p[N];           // 同原文 
vector<int>v;           // 存储每个环的点数 
bitset<N>vis;           // 是否走过 

static inline int solvemax(int k){
    int ans=0;
    for(auto it:v){
        int w=it>>1;
        ans+=min(w,k)<<1,k-=min(w,k);
        if(!k) return ans;
    }
    for(auto it:v){
        if(it&1){           // 是奇环 
            --k,++ans;
            if(!k) return ans;
        }
    }return ans;
}

int c[N]; 
bitset<N>dp;
static inline int solvemin(int k){
    dp[0]=1;
    for(int i=1;i<=n;++i){      // 01 背包 二进制优化 
        if(c[i]){
            for(int j=1;j<=c[i];j<<=1){
                dp|=dp<<(i*j);
                c[i]-=j;
            }
            if(c[i]) dp|=dp<<(i*c[i]);
        }
        if(dp[k]) return k;
    }
    if(dp[k]) return k;
    return k+1;
}

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i){
        p[i]=read();
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            int d=1,u=p[i];
            while(u!=i) ++d,vis[u]=1,u=p[u];
            vis[i]=1,v.push_back(d),++c[d];         // 找环，环的点数存入 v 中 
        }
    }   //for(auto&it:v) cout<<it<<' ';

    cout<<solvemin(k)<<" "<<solvemax(k);
    return 0;
}