(Codefroces) 755F. PolandBall and Gifts [有限制數量背包、bitset]

http://codeforces.com/contest/755/problem/F

就是，有一個小小的知識：
遇到那種題型(就是類似第i個人要給禮物給p[i]，其中p[i]是1~n的全排列)的時候，可以把他想成圖論：把i-->p[i]建邊，之後就會形成很多環(cycle)，很多操作就可以根據上面的性質來做！

那，在這題中，如果有一個人忘記帶禮物，可以把它想像成拔掉一個點 + 那個點所延伸出去的邊。

求出最大值的部分，用greedy就好了，簡單來講，先看有多少可以一次破壞兩個(點 + 邊)，破壞完之後，在看有沒有一個的，如此greedy一番即可。

那，最小值呢？ (以下是editorial的作法)

簡單來講，能完整破壞掉一個環的，就盡量先破壞掉那個環，要不然就是盡量完整破壞掉一些環。

假設所有環的size都在一個v陣列，其中sigma(v) = n

那，求最小值的部分就可以化簡成：挑一些v構成v'，使得sigma(v') = k，如果有的話，答案就是k，沒有的話，就是k+1。

如果用純背包的做法的話，複雜度是O(n*n)，用bitset優化也只有到O(n*n/32)而已，會TLE。

優化的關鍵是：有一個性質是，sigma(v) = n。

於是，我們可以把數值分類，我們選一個T當作標準：若此數字比T還要大，我們就做純背包，稱這個狀況為case 1，其他狀況的話，就開一個cnt陣列，紀錄那個數字出現幾次。然後用有數量限制的背包的做法下去做，稱這個狀況為case 2。

case 1 的複雜度為：假設有W個這樣的數字，其中W最大只會有n/T，於是複雜度是O(W*n)，用bitset優化為O(W*n/32) = O(n*n/(T*32))

case 2 的複雜度為：O(n*T)。但是記得也要用bitset來優化呦。

綜合起來，複雜度為O(n*T + n^2/(T*32))，我們可以選擇T = 100。

Final AC版本：
http://codeforces.com/contest/755/submission/24086291

#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e6 + 6;
const int MAX_M = 106;
const int T = 100;

int a[MAX_N];
bool visit[MAX_N];
int val[MAX_N];
int cnt[MAX_M];
bitset<MAX_N> dp;
int dp2[2][MAX_N];
int dq[MAX_N];
int v[MAX_N];

int main () {
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
        }
        int sz=0;
        int id=1;
        for (int i=1;n>=i;i++) {
            if (!visit[i]) {
                int tmp=0;
                int j=i;
                while (!visit[j]) {
                    tmp++;
                    visit[j]=true;
                    j=a[j];
                }
                v[sz++] = tmp;
                if (tmp>T) val[id++]=tmp;
                else cnt[tmp]++;
            }
        }
        id--;
        dp[0]=1;
        for (int i=1;id>=i;i++) dp=(dp)|(dp<<val[i]);
        int _i=0;
        for (int i=1;T>=i;i++) {
            if (cnt[i] == 0) continue;
            memset(dq,-1,sizeof(dq));
            for (int j=0;n>=j;j++) {
                if (dp[j]) {
                    dq[j%i]=j;
                    continue;
                }
                else {
                    if (dq[j%i]!=-1&& j-dq[j%i]<=cnt[i]*i) {
                        dp[j]=1;
                    }
                }
            }
        }
        
        bool check=dp[k];

        int mx=0,mn=0;
        if (check) mn=k;
        else mn=min(n,k+1);
        int tmp=k;
        mx=0;
        //round 1 --> 2
        for (int x=0;sz>x;x++) {
            int can=v[x]/2;
            if (tmp <= can) {
                mx += 2*tmp;
                tmp=0;
                break;
            }
            else {
                v[x] -= can*2;
                mx += 2*can;
                tmp -= can;
            }
        }
        for(int x=0;sz>x;x++) {
            if (tmp==0) break;
            if (v[x]) {
                tmp--;
                mx++;
            }
        }
        printf("%d %d\n",mn,mx);
    }
}

TLE版本(裡面有用有限制數量的背包)
http://codeforces.com/contest/755/submission/24084759

#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e6 + 6;
const int MAX_M = 106;
const int T = 100;

int a[MAX_N];
bool visit[MAX_N];
int val[MAX_N];
int cnt[MAX_M];
bitset<MAX_N> dp;
int dp2[2][MAX_N];
deque<pii> dq[MAX_M];

int dfs(int id) {
    visit[id]=true;
    if (!visit[a[id]]) return 1+dfs(a[id]);
    else return 1;
}

int main () {
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
        }
        memset(visit,0,sizeof(visit));
        vector<int> cycle;
        int id=1;
        for (int i=1;n>=i;i++) {
            if (!visit[i]) {
                int tmp=dfs(i);
                cycle.push_back(tmp);
                if (tmp>T) val[id++]=tmp;
                else cnt[tmp]++;
            }
        }
        id--;
        dp.reset();
        dp[0]=1;
        for (int i=1;id>=i;i++) dp=(dp)|(dp<<val[i]);
        
        for (int i=1;T>=i;i++) {
            if (cnt[i]==0) {
                for (int j=1;n>=j;j++) {
                    dp2[i%2][j] = dp2[(i-1)%2][j];
                }
                continue;
            }
            else if (cnt[i]==1) {
                for (int j=1;n>=j;j++) {
                    if (j<i) dp2[i%2][j] = dp2[(i-1)%2][j];
                    else dp2[i%2][j] = max(dp2[(i-1)%2][j],dp2[(i-1)%2][j-i]+i);
                }
                continue;
            }
            //memset(dq,0,sizeof(dq));
            for (int x=0;i>=x;x++) {
                dq[x].clear();
            }
            for (int j=0;n>=j;j++) {
                if (j<i) {
                    dp2[i%2][j] = dp2[(i-1)%2][j];
                    dq[j%i].push_back(make_pair(dp2[(i-1)%2][j],j/i));
                }
                else {
                    while (dq[j%i].size() && j/i - dq[j%i][0].second > cnt[i]) {
                        dq[j%i].pop_front();
                    }
                    while (dq[j%i].size() && dq[j%i][dq[j%i].size()-1].first+i*(j/i-dq[j%i][dq[j%i].size()-1].second) <= dp2[(i-1)%2][j]) {
                        dq[j%i].pop_back();
                    }
                    dq[j%i].push_back(make_pair(dp2[(i-1)%2][j],j/i));
                    dp2[i%2][j] = dq[j%i][0].first + i*(j/i-dq[j%i][0].second);
                }
            }
//            cout<<"i = "<<i<<" , cnt = "<<cnt[i]<<" : ";
//            for (int x=1;n>=x;x++) {
//                cout<<dp2[i%2][x]<<" ";
//            }
//            cout<<endl<<endl;
        }
        
        bool check=false;
        for (int i=0;k>=i;i++) {
            if (dp[i] && dp2[T%2][k-i]==k-i) {
                check=true;
                break;
            }
        }
        
        
        vector<int> v=cycle;
        int sz=v.size();
        int mx=0,mn=0;
        if (check) mn=k;
        else mn=min(n,k+1);
        int tmp=k;
        mx=0;
        tmp=k;
        v=cycle;
        //round 1 --> 2
        for (int x=0;sz>x;x++) {
            int can=v[x]/2;
            if (tmp <= can) {
                mx += 2*tmp;
                tmp=0;
                break;
            }
            else {
                v[x] -= can*2;
                mx += 2*can;
                tmp -= can;
            }
        }
        for(int x=0;sz>x;x++) {
            if (tmp==0) break;
            if (v[x]) {
                tmp--;
                mx++;
            }
        }
        printf("%d %d\n",mn,mx);
    }
}