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

(UVA) 12538 - Version Controlled IDE [可持久化treap]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=441&problem=3983

Persistent Treap !!!

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

const int MAX_N = 1e5 + 6;
const int MAX_M = 1e6 + 6;
const int MAX_P = 3e7;

int myRnd() {
    return 10000*(rand()%10000) + (rand()%10000);
}

struct Treap {
    static Treap mem[MAX_P];
    Treap *lc,*rc;
    char c;
    int sz;
    Treap(){}
    Treap(char _c) : lc(NULL),rc(NULL),sz(1),c(_c){}
} Treap::mem[MAX_P], *ptr=Treap::mem ;

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    Treap* ret;
    if (myRnd() % (Sz(a) + Sz(b)) < Sz(a)) {
        ret = new (ptr++) Treap(*a);
        ret->rc = merge(a->rc,b);
    }
    else {
        ret = new(ptr++) Treap(*b);
        ret->lc=merge(a,b->lc);
    }
    pull(ret);
    return ret;
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (Sz(t->lc) + 1 <= k) {
        a = new(ptr++) Treap(*t);
        split(t->rc,k-Sz(t->lc)-1,a->rc,b);
        pull(a);
    }
    else {
        b=new(ptr++) Treap(*t);
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

int d;
char buf[MAX_M];
Treap* ver[MAX_N];

void print(Treap* t) {
    if (!t) return;
    print(t->lc);
    if (t->c == 'c') d++;
    printf("%c",t->c);
    print(t->rc);
    return;
}

int main () {
    srand(time(NULL));
    int n;
    while (scanf("%d",&n) != EOF) {
        ptr = Treap::mem;
        d=0;
        int v_cnt=0;
        ver[0] = NULL;
        for (int i=1;n>=i;i++) {
            Treap *tl,*tmid,*tr;
            int type;
            scanf("%d",&type);
            if (type==1) {
                v_cnt++;
                ver[v_cnt] = ver[v_cnt-1];
                int p;
                scanf("%d %s",&p,buf);
                p-=d;
//                cout<<"p = "<<p<<endl;
                split(ver[v_cnt],p,tl,tr);
                for (int j=0;buf[j];j++) {
//                    cout<<"buf["<<j<<"] = "<<buf[j]<<endl;
                    tl = merge(tl,new(ptr++)Treap(buf[j]));
                }
                ver[v_cnt] = merge(tl,tr);
//                print(ver[v_cnt]);puts("");
            }
            else if (type==2) {
                v_cnt++;
                ver[v_cnt] = ver[v_cnt-1];
                int p,c;
                scanf("%d %d",&p,&c);
                p-=d;
                c-=d;
                split(ver[v_cnt],p-1,tl,tr);
                split(tr,c,tmid,tr);
                ver[v_cnt] = merge(tl,tr);
            }
            else {
                int v,p,c;
                scanf("%d %d %d",&v,&p,&c);
                v-=d,p-=d,c-=d;
                split(ver[v],p-1,tl,tr);
                split(tr,c,tmid,tr);
                print(tmid);
                puts("");
            }
        }
    }
}

(SPOJ) GSS3 - Can you answer these queries III

http://www.spoj.com/problems/GSS3/

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

typedef long long LL;
const LL INF = 1e15 + 6;

struct Treap {
    Treap *lc,*rc;
    LL val;
    LL key;
    LL lmax,rmax,midmax,sum;
    int pri;
    Treap(LL _key,LL _val) {
        lc=rc=NULL;
        pri = rand();
        lmax=rmax=midmax=sum=val=_val;
        key = _key;
    }
};

LL Lmax(Treap* t) {
    return t?t->lmax:-INF;
}

LL Rmax(Treap* t) {
    return t?t->rmax:-INF;
}

LL Midmax(Treap* t) {
    return t?t->midmax:-INF;
}

LL Sum(Treap* t) {
    return t?t->sum:0;
}

void pull(Treap* t) {
    t->sum = Sum(t->lc) + Sum(t->rc) + t->val;
    t->lmax = max(max(Lmax(t->lc),Sum(t->lc)+t->val),Sum(t->lc)+t->val+Lmax(t->rc));
    t->rmax = max(max(Rmax(t->rc),Sum(t->rc)+t->val),Sum(t->rc)+t->val+Rmax(t->lc));
    t->midmax = max(max(max(Midmax(t->lc),Midmax(t->rc)),t->val),max(max(Rmax(t->lc)+t->val,Lmax(t->rc)+t->val),Lmax(t->rc)+Rmax(t->lc)+t->val));
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,LL k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (t->key <= k) {
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

const int MAX_N = 5e4 + 6;

LL a[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        Treap* root;
        root=NULL;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            root = merge(root,new Treap(i,a[i]));
        }
        int m;
        scanf("%d",&m);
        while (m--) {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if (a==0) {
                Treap *tl,*tr;
                split(root,b-1,tl,root);
                split(root,b,root,tr);
                root = merge(merge(tl,new Treap(b,c)),tr);
            }
            else {
                Treap *tl,*tr;
                split(root,b-1,tl,root);
                split(root,c,root,tr);
                printf("%lld\n",root->midmax);
                root=merge(merge(tl,root),tr);
            }
        }
    }
}

(IOICamp_Judge) 91.列印機問題 [1D/1D Convex DP優化，1D/1D Monge Condition]

https://judge.ioicamp.org/problems/91

因為怕題目之後不見，做個備份：

列印機問題

Time Limit: 1s

Description

你正在修機器學習的課程，因為作業太困難了，所以你決定把題目印下來慢慢研究。

現在有一台計費方式很奇怪的列印機，當你送出一份要列印的文件時，列印機會對文件中的每一頁算出列印該頁所需的成本，令該份文件每一頁的列印成本總和為 x，列印這份文件所需的價錢就是 x3+K（K 為給定的常數）。

為了省錢，你決定把整份作業拆成好幾份文件列印，但是列印完還要自己重新排列很麻煩，因此你決定每次送出去列印的文件都必須是在原始作業檔案中頁數連續的一段，例如第 2 頁到第 5頁。

整份作業總共有 N 頁，並順利算出每一頁的列印成本。現在你要經過數次如上的列印，確保自己拿到作業中每一頁的紙本（同一頁可以被列印多次），請問你所需花費的錢最少為多少？

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。

每筆測試資料包含兩行，其中的第一行為兩個正整數 N,K，表示機器學習作業的頁數以及列印機計價方式中的常數 K。第二行包含 N 個整數，依序代表作業中第 1 頁列印成本、第 2頁列印成本、第 3 頁列印成本………第 N 頁列印成本。

• 1≤T≤100
• 1≤N≤105
• 1≤K≤1012
• 0≤每一頁的列印成本 ≤10
• 所有測試資料中的 N 加總不超過 106

Output Format

對於每筆測試資料，請輸出一行一個整數，代表用最佳方式列印所需花費的最少金額。

Sample Input

2
3 5
2 4 1
5 514
3 8 2 0 1

Sample Output

88
2108

Hint

在第一筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、只包含第 3$3$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (23+5)+(43+5)+(13+5)=88

在第二筆範例測試資料中，最佳方法是分別送出只包含第 1 頁的文件、只包含第 2 頁的文件、包含第 3$3$ 頁到第 5$5$ 頁的文件，共 3$3$ 份文件去列印，於是總花費的金額會是 (33+514)+(83+514)+((2+0+1)3+514)=2108

這題主要是用Convex 1D/1D DP優化

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

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef long long LL;
const int MAX_N = 1e5 + 6;

LL a[MAX_N],s[MAX_N],k;
LL dp[MAX_N];

LL f(LL i,LL j) {
    return dp[i]+ ( k+(s[j]-s[i])*(s[j]-s[i])*(s[j]-s[i]) );
}

struct Seg {
    LL i,l,r;
};

Seg MP(int _i,int _l,int _r) {
    return (Seg){_i,_l,_r};
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d %lld",&n,&k);
        memset(s,0,sizeof(s));
        int m=1;
        for (int i=1;n>=i;i++) {
            scanf("%lld",&a[i]);
            if (a[i] == 0) {
                continue;
            }
            s[m] = s[m-1]+a[i];
            m++;
        }
        m--;
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        deque<Seg> dq;
        dq.push_back(MP(0,1,m));
        for (int j=1;m>=j;j++) {
            while (dq.size()) {
                Seg tmp=dq.back();
                if (f(tmp.i,tmp.l) > f(j-1,tmp.l)) dq.pop_back();
                else break;
            }
            if (dq.size()) {
                Seg tmp=dq.back();
                int L=tmp.l,R=tmp.r+1;
                while (R-L>1) {
                    int mid=(L+R)>>1;
                    if (f(tmp.i,mid) > f(j-1,mid)) R=mid;
                    else L=mid;
                }
                dq.pop_back();
                dq.push_back(MP(tmp.i,tmp.l,L));
                if (L!=m) dq.push_back(MP(j-1,L+1,m));
                dp[j] = f(dq[0].i,j);
                if (dq[0].r==j) dq.pop_front();
                else {
                    Seg temp=dq.front();
                    dq.pop_front();
                    Seg ret=MP(temp.i,temp.l+1,temp.r);
                    dq.push_front(ret);
                }
            }
            else {
                dq.push_back(MP(j-1,j+1,n));
                dp[j] = f(j-1,j);
            }
        }
        if (m!=0)printf("%lld\n",dp[m]);
        else printf("%lld\n",k);
    }
}