【题目链接】:http://codeforces.com/contest/755/problem/F

【题意】



n个人;

计划是每个人都拿一个礼物来送给一个除了自己之外的人;

且如果一个人没有送出礼物,那么它和它送礼物的对象都得不到礼物;

但是已经知道有k个人会忘记带礼物来;

问最少有几个人收不到礼物,最多有多少个人收不到礼物

【题解】



①

对于最多的情况;

最后会形成多个环;

每个环隔一个人选一个人忘记带礼物;这样一个长度为len的环只要len/2个人没带礼物就能够整个环的人都收不到礼物了;

然后如果len为奇数就放在最后再处理;因为那些多余的一个人必须得用1个名额来补充;所以先放在最后;因为你当前一个名额能够抵消两个人,肯定优先抵消两个人;

②

对于最少的情况;

就是k个名额刚好分配每个环的人数;

如果不是刚好;

则会多出一个人即k+1

那么问题就转换成一个背包问题了;

把每个环的长度看成一个物品,同种长度的环可能有多个

->多重背包;

问能不能刚好体积为k;

这里用到了多重背包的二进制优化;

然后还用到了bitset的技巧;

即把增加容量和

二进制的左移操作对应;

很厉害。。



【Number Of WA】



3



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) cin >> x

#define pri(x) cout << x

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e6+1000;

int n,k,a[N],b[N],num,cnt,ans1,ans2,w[N];

bool vis[N];

bitset<N> f;

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false);

    rei(n),rei(k);

    rep1(i,1,n)

        rei(a[i]);

    rep1(i,1,n)

        if (!vis[i])

        {

            num++,cnt = 0;

            int j = i;

            while (!vis[j])

            {

                vis[j] = true;

                cnt++;

                j = a[j];

            }

            b[num] = cnt;

        }

    n = num;

    sort(b+1,b+1+n);

    int rest = k,t = 0;

    rep1(i,1,n)

    {

        if (b[i]/2<=rest)

        {

            rest-=b[i]/2;

            ans2+=b[i]/2*2;

        }

        else

        {

            ans2+=rest*2;rest = 0;

            break;

        }

        if (b[i]&1) t++;

    }

    ans2+=min(rest,t);

    num = 0;

    rep1(i,1,n)

    {

        int j = i;

        while (j+1<=n && b[j+1]==b[i]) j++;

        int t = 1,len = j-i+1;

        while (len>=t)

        {

            w[++num] = t*b[i];

            len-=t;

            t<<=1;

        }

        if (len)

            w[++num] = len*b[i];

        i = j;

    }

    n = num;

    f[0] = 1;

    rep1(i,1,n)

        f|=f<<(w[i]);

    ans1 = k+1;

    if (f[k])

        ans1 = k;

    pri(ans1<<' '<<ans2<<endl);

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}