(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);
    }
}

(Codeforces) 313E. Ilya and Two Numbers

http://codeforces.com/contest/313/problem/E

((待補題解

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;

const int MAX_N = 1e5 + 6;

int cnt1[MAX_N];
int cnt2[2*MAX_N];
int ans[MAX_N];

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        memset(cnt1,0,sizeof(cnt1));
        memset(cnt2,0,sizeof(cnt2));
        memset(ans,0,sizeof(ans));
        for (int i=1;n>=i;i++) {
            int t;
            scanf("%d",&t);
            cnt1[t]++;
        }
        for (int i=1;n>=i;i++) {
            int t;
            scanf("%d",&t);
            cnt2[m-t-1]++;
        }
        for (int i=0;m>i;i++) {
            //cout<<"cnt1["<<i<<"] = "<<cnt1[i]<<" , ~~~2 = "<<cnt2[i]<<endl;
            int tmp=min(cnt1[i],cnt2[i]);
            //cout<<"tmp = "<<tmp<<endl;
            ans[m-1]+= tmp;
            cnt1[i] -= tmp;
            cnt2[i] -= tmp;
            //cout<<"ans[m-1] = "<<ans[m-1]<<endl;
        }
        priority_queue<int> pq;
        for (int i=0;m>i;i++) {
            for (int j=0;cnt1[i]>j;j++) {
                pq.push(i);
            }
            while (cnt2[i]>0 && !pq.empty()) {
                cnt2[i]--;
                int t=pq.top();
                //cout<<"i = "<<i<<" , t = "<<t<<endl;
                pq.pop();
                ans[abs((m-i-1+t)%m)]++;
            }
        }
        for (int i=0;m>i;i++) {
            cnt2[m+i]=cnt2[i];
        }
        for (int i=m;2*m>i;i++) {
            while (cnt2[i]>0 && !pq.empty()) {
                cnt2[i]--;
                int t=pq.top();
                //cout<<"ii = "<<i<<" , t = "<<t<<endl;
                pq.pop();
                ans[abs((2*m-i+t-m-1))]++;
            }
        }
        bool check=false;
        for (int i=m-1;i>=0;i--) {
            while (ans[i]--) {
                if (check) printf(" ");
                check=true;
                printf("%d",i);
            }
        }
        puts("");
    }
}

(Codeforces) 313D. Ilya and Roads

http://codeforces.com/contest/313/problem/D

最近好久沒po題解了XD

這題算是一題DP題。

現在假設我們知道建造L, L+1, L+2, ...... , R-1, R的費用，我就姑且叫做w[i][j]好了(到達不到的話就設成INF)，那，我們就可以列出一個簡單的dp式子： (dp[i][j]代表我選擇了i的東西，最後一個是j)

dp[i][j] = min( min(dp[i-k][1 ~ j-k]) + w[j-k+1][j] ) ，然後呢，我們可以把裡面第二個min用陣列的方法去優化。

那，我們要怎麼知道w[i][j]呢?

可以想像的是說，如果w[i-1][j]比w[i][j]小，那我們就要把w[i][j]設定成w[i+1][j]，這個就是第一個for迴圈的部分。

第二個for迴圈的意思是說：當今天某一段可以由兩個比較小的段組合起來時，就可以用那個。

#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long LL;
const int MAX_N = 306;
const LL INF = 1e17 + 6;

LL w[MAX_N][MAX_N];
LL dp[MAX_N][MAX_N]; //times,last -->best //have last
LL mn[MAX_N][MAX_N];

int main () {
    int n,m,K;
    while (scanf("%d %d %d",&n,&m,&K) != EOF) {
        for (int x=0;n+1>=x;x++) {
            for (int y=0;n+1>=y;y++) {
                w[x][y] = INF;
                dp[x][y]= INF;
                mn[x][y]= INF;
                if (x==0) mn[x][y]=dp[x][y] = 0;
            }
        }
        for (int x=0;m>x;x++) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            w[a][b] = min(w[a][b],LL(c));
        }
        for (int i=n-1;i>=0;i--) {
            //i means lenght
            for (int j=1;n>=j+i;j++) {
                w[j][j+i] = min(min(w[j][j+i+1],w[j-1][j+i]),w[j][j+i] );
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=i+1;n>=j;j++) {
                for (int k=i;j>k;k++) {
                    w[i][j] = min(w[i][j],w[i][k] + w[k+1][j]);
                }
            }
        }
//        for (int i=1;n>=i;i++) {
//            for (int j=i;n>=j;j++) {
//                cout<<"w["<<i<<"]["<<j<<"] = "<<w[i][j]<<endl;
//            }
//        }
        LL ans=INF;
        for (int i=1;n>=i;i++) {
            for (int j=i;n>=j;j++) {
                for (int k=1;n>=k;k++) {
                    if (i-k<0) break;
                    dp[i][j] = min(dp[i][j],mn[i-k][j-k] + w[j-k+1][j]);
                    if (i>=K) ans=min(ans,dp[i][j]);
                }
                mn[i][j] = min(mn[i][j-1],dp[i][j]);
            }
        }
        if (ans<INF) printf("%I64d\n",ans);
        else puts("-1");
    }
}

(IOICamp_2016) 30. 序列分割問題

題目備份：

這是一題DP斜率優化的題目！

可以想想看喔！

(題解日後補上)

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAX_K = 106;
const int MAX_N = 1e4 + 6;
const LL INF= 1e17 + 6;

LL dp[MAX_K][MAX_N];
LL pre[MAX_N],s[MAX_N]; //s-->prefix sum, pre--weight prefix sum

int id;

LL f(int i) {
    return pre[i];
}

LL g(int j) {
    return dp[id][j] - pre[j] + s[j]*j;
}

LL h(int j) {
    return -j;
}

LL t(int i) {
    return s[i];
}

struct Line {
    LL m,b;
    LL val(LL x) {
        return m*x+b;
    }
};

Line MP(LL _m,LL _b) {
    return (Line){_m,_b};
}

bool check(Line l1,Line l2,Line l3) {
    return (l2.b-l1.b)*(l1.m-l3.m) <= (l1.m-l2.m)*(l3.b-l1.b);
}

LL a[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,K;
        scanf("%d %d",&n,&K);
        s[0] = pre[0] = 0;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            s[i] = s[i-1] + a[i];
            pre[i] = pre[i-1] + i*a[i];
        }
        for (int i=1;n>=i;i++) {
            dp[1][i] = pre[i];
        }
        for (int k=2;K>=k;k++) {
            deque<Line> dq;
            id = k-1;
            dq.push_back(MP(h(k-1),g(k-1)));
            for (int i=k;n>=i;i++) {
                //cout<<"sz = "<<dq.size()<<endl;
                while (dq.size()>1&&dq[0].val(t(i)) > dq[1].val(t(i))) dq.pop_front();
                dp[k][i] = f(i) + dq[0].val(t(i));
                Line newline=MP(h(i),g(i));
                while (dq.size()>1 && check(dq[dq.size()-1],dq[dq.size()-2],newline)) dq.pop_back();
                dq.push_back(newline);
                //cout<<"dp["<<k<<"]["<<i<<"] = "<<dp[k][i]<<endl;
            }
        }
        for (int i=1;K>=i;i++) {
            if (i!=1) printf(" ");
            printf("%lld",dp[i][n]);
        }
        puts("");
    }
}