(Codeforces) 786B. Legacy

http://codeforces.com/contest/786/problem/B

超酷的最短路徑題

要在上面建線段樹><

詳細看editorial吧

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)
#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

#define vpii vector<pii>

struct Dijkstra {
    static const int N = 2e6 +6;
    vpii G[N];
    int n,s;
    void init(int n,int s) {
        this->n = n;
        this->s = s;
        REP0(i,n+1) {
            G[i].clear();
        }
    }
    void add_edge(int from,int to,int cost) {
        G[from].PB({to,cost});
    }
    LL d[N];
    static const LL INF = 1e17 + 6;
    void solve() {
        REP0(i,n+1)
        {
            d[i] = INF;
        }
        d[s]=0;
        priority_queue<pLL,vector<pLL>,greater<pLL> > pq;
        pq.push({d[s],s});
        while (!pq.empty()) {
            pLL p= pq.top();
            pq.pop();
            if (d[p.S] != p.F) continue;
            for (pii pp:G[p.S]) {
                if (d[pp.F] > d[p.S] + pp.S) {
                    d[pp.F] = d[p.S] + pp.S;
                    pq.push({d[pp.F],pp.F});
                }
            }
        }
    }
} dijkstra;

const int N = 2e6 + 6;

int lc[N],rc[N];
int cnt;

void build1(int now,int L,int R) {
    if (L==R) {
        lc[now] = rc[now] = -1;
        dijkstra.add_edge(now,L,0);
        return;
    }
    int mid=(L+R)>>1;
    lc[now] = cnt++;
    rc[now] = cnt++;
    dijkstra.add_edge(now,lc[now],0);
    dijkstra.add_edge(now,rc[now],0);
    build1(lc[now],L,mid);
    build1(rc[now],mid+1,R);
}

void build2(int now,int L,int R,int par) {
    if (par != now) dijkstra.add_edge(now,par,0);
    if (L==R) {
        dijkstra.add_edge(L,now,0);
        lc[now] = rc[now] = -1;
        return;
    }
    int mid=(L+R)>>1;
    lc[now] = cnt++;
    rc[now] = cnt++;
    build2(lc[now],L,mid,now);
    build2(rc[now],mid+1,R,now);
    return;
}

void query1(int now,int L,int R,int l,int r,int v,int w) {
    if (L > r || l > R) return;
    else if (l<= L && R<=r) {
        dijkstra.add_edge(v,now,w);
        return;
    }
    int mid = (L+R)>>1;
    query1(lc[now],L,mid,l,r,v,w);
    query1(rc[now],mid+1,R,l,r,v,w);
}

void query2(int now,int L,int R,int l,int r,int v,int w) {
    if (L > r || l > R) return;
    else if (l<= L && R<=r) {
        dijkstra.add_edge(now,v,w);
        return;
    }
    int mid = (L+R)>>1;
    query2(lc[now],L,mid,l,r,v,w);
    query2(rc[now],mid+1,R,l,r,v,w);
}

int main () {
    srand(time(NULL));
    int n,q,s;
    Siii(n,q,s);
    dijkstra.init(N-1,s);
    cnt = n+1;
    int root1=cnt++;
    build1(root1,1,n);
    int root2=cnt++;
    build2(root2,1,n,root2);
    REP1(i,q)
    {
        int type;
        Si(type);
        if (type == 1) {
            int u,v,w;
            Siii(u,v,w);
            dijkstra.add_edge(u,v,w);
        }
        else if (type == 2) {
            int v,l,r,w;
            Siiii(v,l,r,w);
            query1(root1,1,n,l,r,v,w);
        }
        else if (type == 3) {
            int v,l,r,w;
            Siiii(v,l,r,w);
            query2(root2,1,n,l,r,v,w);
        }
    }
    dijkstra.solve();
    REP1(i,n) {
        LL val=dijkstra.d[i];
        if (i!=1) Pspace;
        if (val == dijkstra.INF) Pi1(-1)
        else PL1(val);
    }
    Pendl;
}

(Codeforces) 765E. Tree Folding

http://codeforces.com/problemset/problem/765/E

某種樹DP的感覺吧XD

先討論一直鍊(chain)的情況吧！

如果直鏈的節點數是奇數，那就代表他還可以再變成(n+1)/2 (從中間看，往兩邊折的感覺)，如果節點數是偶數，那就不能再折了，就輸出相對應的邊數(記得，不是點(vertex)數！)

那，來討論不是直鏈的情況吧

//待補

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

const int MAX_N = 2e5 + 6;

vector<int> edg[MAX_N];
vector<int> _[MAX_N];
int deg[MAX_N];
int sz[MAX_N];
bool visit[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int i=0;n>=i;i++) {
            edg[i].clear();
            _[i].clear();
        }
        memset(deg,0,sizeof(deg));
        for (int i=1;n>i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
            deg[a]++;
            deg[b]++;
        }
        memset(sz,0,sizeof(sz));
        memset(visit,0,sizeof(visit));
        queue<int> que;
        bool flag=0;
        for (int i=1;n>=i;i++) {
            if (deg[i]>2) flag=1;
            if (deg[i] == 1) {
                que.push(i);
                sz[i] = 1;
            }
        }
        if (!flag) {
            while (n%2==1 && n!=1) {
                n = (n+1)/2;
            }
            printf("%d\n",n-1);
            continue;
        }
        int cnt=0;
        bool okay=true;
        int root=-1;
        while (!que.empty()) {
            int t=que.front();
//            cout<<"t = "<<t<<endl;
            que.pop();
            visit[t]=1;
            sort(_[t].begin(),_[t].end());
            _[t].resize(unique(_[t].begin(),_[t].end()) - _[t].begin());
            cnt++;
            if (cnt==n) {
                root = t;
                break;
            }
            if (_[t].size() > 1) {
                okay = false;
                break;
            }
            if (_[t].size() > 0) {
                sz[t] = _[t][0] + 1;
            }
//            cout<<"hihi\n";
            for (auto i:edg[t]) {
                if (!visit[i]) {
                    _[i].push_back(sz[t]);
                    deg[i]--;
                    if (deg[i] == 1) {
                        que.push(i);
                    }
                }
            }
        }
        if (!okay) {
            puts("-1");
            continue;
        }
//        cout<<"root = "<<root<<endl;
        if (_[root].size() > 2) puts("-1");
        else {
            int ans= _[root][0]+1;
            if (_[root].size()>1) ans += _[root][1];
//            cout<<"ans = "<<ans<<endl;
            while (ans%2==1 && ans!=1) {
                ans = (ans+1)/2;
            }
            printf("%d\n",ans-1);
        }
    }
}

(Codeforces) 441D. Valera and Swaps

http://codeforces.com/problemset/problem/441/D

題目大意：給你一個permutation P，設f(P)代表把P變成1,2,3, ... , n-1, n的最小次數。現在指定要使得f(P) = q，請問最少要move多少次，請把過程輸出，並使用字典序最小的解！

先有一個permutation的感覺，假設在P這個全排列中第i個位置的值是p[i]，則我們如果把所有的i-->p[i]建圖，那我們會得到一些環(cycle)，那，把p變成1,2,3, ...... , n-1, n的最小次數就是n-cycle的數量！(可以簡單畫圖試試看喔！)。

知道這個結論之後，我們就可以分成兩種case：一種是f(P)太多(現在的cycle太少)，另外一種是f(P)太少(現在的cycle太多)

對於第二種case，我們要讓cycle變少，又要是字典序最小的話，可以很greedy的一直跟拿跟i=1不同的cycle中，i最小的跟1換，只要有交換的動作，不是會把兩個cycle merge再一起，就是會把一個cycle 給split成兩個cycle。這樣的複雜度是O(N)

對於第一種case：我們可以每找到一個在同一個cycle最小的兩個id後，把圖砍掉重建，這樣的複雜度是O(N^2)

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

typedef pair<int,int> pii;
const int MAX_N = 3e3 + 6;

int a[MAX_N];
bool visit[MAX_N];
vector<int> ala[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int i=0;n>=i;i++) {
            ala[i].clear();
        }
        for (int i=1;n>=i;i++) {
            int x;
            scanf("%d",&x);
            a[i]=x;
        }
        memset(visit,0,sizeof(visit));
        int _;
        scanf("%d",&_);
        int sz=0;
        for (int i=1;n>=i;i++) {
            if (!visit[i]) {
                sz++;
                int __=i;
                while (!visit[__]) {
                    visit[__]=1;
                    ala[sz].push_back(__);
                    __ = a[__];
                }
            }
        }
        if (n-sz == _) {
            puts("0");
            continue;
        }
        else if (n-sz >= _) {
            vector<pii> ans;
            //too much
            int need=(n-sz-_);
            printf("%d\n",(n-sz-_));
            while (need--) {
                pii alala=make_pair(n+1,n+1);
                int mn1=n+1,mnid=n+1;
                for (int i=1;sz>=i;i++) {
                    if (ala[i].size()!=1) {
                        int len=ala[i].size();
                        for (int j=0;len>j;j++) {
                            if (ala[i][j] < mn1) {
                                mn1=ala[i][j];
                                mnid=i;
                            }
                        }
                    }
                }
                int mn2=n+1;
                for (int i=1;sz>=i;i++) {
                    if (i!=mnid) continue;
                    if (ala[i].size()!=1) {
                        int len=ala[i].size();
                        for (int j=0;len>j;j++) {
                            if (ala[i][j] < mn2 && ala[i][j] != mn1) {
                                mn2=ala[i][j];
                                mnid=i;
                            }
                        }
                    }
                }
                alala = make_pair(mn1,mn2);
                printf("%d %d ",alala.first,alala.second);
                swap(a[alala.first],a[alala.second]);
                memset(visit,0,sizeof(visit));
                sz=0;
                for (int i=1;n>=i;i++) {
                    ala[i].clear();
                }
                for (int i=1;n>=i;i++) {
                    if (!visit[i]) {
                        sz++;
                        int __=i;
                        while (!visit[__]) {
                            visit[__]=1;
                            ala[sz].push_back(__);
                            __ = a[__];
                        }
                    }
                }
            }
            puts("");
        }
        else if (n-sz < _){
            vector<pii> ans;
            //too few
            int need = _-(n-sz);
            for (int i=2;sz>=i;i++) {
                ans.push_back(make_pair(ala[1][0],ala[i][0]));
            }
            sort(ans.begin(),ans.end());
            printf("%d\n",-(n-sz-_));
            for (auto i:ans) {
                printf("%d %d ",i.first,i.second);
                need--;
                if (!need) break;
            }
            puts("");
        }
    }
}

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