USACO 2015 December Contest, Platinum Problem 3. Counting Haybales

http://www.usaco.org/index.php?page=viewproblem2&cpid=578

Tips: segment tree with lazy tag

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

#define int long long
typedef long long LL;
const int MAX_N = 2e5 + 6;
const LL INF = 1e17+6;

struct Node {
    Node* lc;
    Node* rc;
    LL val,sum,mn;
    LL tag;
    Node() {
        lc=rc=NULL;
        val=sum=tag=0;
        mn=INF;
    }
    void pull() {
        sum=lc->sum + rc->sum;
        mn = min(lc->mn,rc->mn);
    }
};

LL v[MAX_N];

Node* Build(int L,int R) {
    Node* node= new Node();
    if (L==R) {
        node->val = node->sum = node->mn = v[L];
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void push(Node* node,int L,int R) {
    if (L==R) {
        node->tag=0;
        return;
    }
    else if (node->tag != 0) {
        int mid=(L+R)>>1;
        node->lc->tag += node->tag;
        node->rc->tag += node->tag;
        node->lc->sum += (mid-L+1) * node->tag;
        node->rc->sum += (R-mid) * node->tag;
        node->lc->mn += node->tag;
        node->rc->mn += node->tag;
    }
    node->tag=0;
}

void modify(Node* node,int L,int R,int l,int r,int val) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->sum += (R-L+1)*val;
        node->mn += val;
        node->tag += val;
        return;
    }
    int mid=(L+R)>>1;
    push(node,L,R);
    modify(node->lc,L,mid,l,r,val);
    modify(node->rc,mid+1,R,l,r,val);
    node->pull();
    return;
}

LL query(Node* node,int L,int R,int l,int r,int type) {
    if (type==1) {
        if (l>R || L>r) return 0;
        else if (l<=L && R<=r) return node->sum;
        push(node,L,R);
        int mid=(L+R)>>1;
        return query(node->lc,L,mid,l,r,type) + query(node->rc,mid+1,R,l,r,type);
    }
    else {
        if (l>R || L>r) return INF;
        else if (l<=L && R<=r) return node->mn;
        push(node,L,R);
        int mid=(L+R)>>1;
        return min(query(node->lc,L,mid,l,r,type) ,query(node->rc,mid+1,R,l,r,type) );
    }
}

main () {
    if (fopen("haybales.in","r")) {
        freopen("haybales.in","r",stdin);
        freopen("haybales.out","w",stdout);
    }
    int n,q;
    while (scanf("%lld %lld",&n,&q) != EOF) {
        for (int x=1;n>=x;x++) {
            scanf("%lld",&v[x]);
        }
        Node* root = Build(1,n);
        for (int x=0;q>x;x++) {
            getchar();
            char t;
            int a,b,c;
            scanf("%c %lld %lld",&t,&a,&b);
            if (t=='P') scanf("%lld",&c);
            if (t=='M') {
                printf("%lld\n",query(root,1,n,a,b,2));
            }
            else if (t=='S') {
                printf("%lld\n",query(root,1,n,a,b,1));
            }
            else {
                modify(root,1,n,a,b,c);
            }
        }
    }
}

USACO 2015 December Contest, Platinum Problem 2. High Card Low Card (Platinum)

http://www.usaco.org/index.php?page=viewproblem2&cpid=577

Key : http://codeforces.com/contest/380/problem/C

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

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
#define F first
#define S second
#define MP make_pair
const int MAX_N = 1e5 + 6;

piii operator+(const piii &p1,const piii &p2) {
    int tmp=min(p1.second.S,p2.second.F );
    return MP(p1.first+p2.first+tmp,MP(p1.second.F + p2.second.F - tmp,p1.second.S + p2.second.S - tmp));
}

int v[MAX_N]; 
vector<int> r1,r2;

struct Node {
    Node *lc,*rc;
    piii val;
    piii val2;
    Node() {
        lc=rc=NULL;
        val2=val=MP(0,MP(0,0));
    }
    void pull() {
        val = lc->val + rc->val;
        val2= lc->val2+rc->val2;
    }
};

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        if (v[L]) node->val=MP(0,MP(0,1));
        else node->val=MP(0,MP(1,0));
        return node;
    }
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node,int L,int R,int pos,int val ) {
    if (L==R) {
        v[L]=val;
        if (v[L]) node->val2=MP(0,MP(0,1));
        else node->val2=MP(0,MP(1,0));
        node->val = MP(0,MP(0,0));
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return;
}

int main () {
    if (fopen("cardgame.in","r")) {
        freopen("cardgame.in","r",stdin);
        freopen("cardgame.out","w",stdout);
    }
    int n;
    while (scanf("%d",&n) != EOF) {
        r1.clear();
        r2.clear();
        memset(v,0,sizeof(v));
        for (int x=0;n>x;x++) {
            int i;
            scanf("%d",&i);
            v[i]=1;
            r1.push_back(i);
        }
        n*=2;
        for (int x=1;n>=x;x++) {
            if (v[x] == 0) {
                r2.push_back(x);
            }
        }
        Node* root = Build(1,n);
        int ans=root->val.first;
        int len=n/2;
//        cout<<"ans="<<ans<<endl;
        for (int x=len-1,y=0;x>=0;x--,y++) {
//            cout<<"x="<<x<<" ";
//            cout<<"r1 = "<<r1[x]<<" , r2="<<r2[y];
            modify(root,1,n,r1[x],0);
            modify(root,1,n,r2[y],1);
            ans = max(ans,root->val.first + root->val2.first);
//            cout<<" ans = "<<ans<<endl;
        }
        printf("%d\n",ans);
    }
}

USACO 2015 December Contest, Platinum Problem 1. Max Flow

http://www.usaco.org/index.php?page=viewproblem2&cpid=576

key : LCA

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

typedef pair<int,int> pii;
const int MAX_N = 5e4+6;
const int MAX_K = 1e5+6;
const int MAX_P = 21;

pii pip[MAX_K]; //pipe
int ans[MAX_N];
int depth[MAX_N];
int lca[MAX_P][MAX_N];
int _1[MAX_N],_2[MAX_N];
int st[MAX_N];
int binary[MAX_P];
bool visit[MAX_N];
vector<int> edg[MAX_N];

void dfs1(int id,int cur_depth) {
    depth[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (depth[tmp]==0) {
            lca[1][tmp]=id;
            dfs1(tmp,cur_depth+1);
        }
    }
}

int walk(int i,int to_depth) {
    int tmp=depth[i]-to_depth;
    if (tmp<0) return -1;
    int id=0;
    while (tmp>0) {
        binary[id++]=tmp%2;
        tmp/=2;
    }
    for (int x=id-1;x>=0;x--) {
        if (binary[x]==1) {
            i=lca[x+1][i];
        }
    }
    return i;
}

void get_lca(pii i) {
    int a=i.first;
    int b=i.second;
    st[a]++,st[b]++;
    int R=min(depth[a],depth[b])+1,L=0; //L is the answer
    while (R-L != 1) {
//        cout<<"R = "<<R<<" , L="<<L<<endl;
        int mid=(L+R)>>1;
        if (walk(a,mid) == walk(b,mid) && walk(a,mid)!=-1) L=mid;
        else R=mid;
    }
    int step=L;
//    cout<<"a = "<<a<<" , b="<<b<<" , step = "<<step<<" , to = "<<walk(a,step)<<endl;
    if (step==depth[a]) {
//        cout<<"in1\n";
        st[a]--;
        _2[a]++;
    }
    else if (step==depth[b]) {
//        cout<<"in2\n";
        st[b]--;
        _2[b]++;
    }
    else {
        _1[walk(a,step)]++;
    }
//    cout<<"a="<<a<<" , b="<<b<<" , meet = "<<walk(a,step)<<endl;
}

int dfs2(int id) {
    visit[id]=true;
    int ret=0;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) {
            ret += dfs2(tmp);
        }
    }
//    cout<<"id = "<<id<<" , st="<<st[id]<<" , _1="<<_1[id]<<" , _2="<<_2[id];
//    cout<<" ret = "<<ret;
    ans[id]=ret - _1[id] + st[id];
    ret = ret - _2[id] + st[id] - 2*_1[id];
//    cout<<" ans = "<<ans[id]<<endl;
    return ret;
}

int main () {
    if (fopen("maxflow.in","r")) {
        freopen("maxflow.in","r",stdin);
        freopen("maxflow.out","w",stdout);
    }
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            depth[x]=st[x]=_1[x]=_2[x]=0;
            visit[x]=false;
        }
        for (int x=0;n-1>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[j].push_back(i);
            edg[i].push_back(j);
        }
        for (int x=0;k>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            pip[x]=make_pair(i,j);
        }
        dfs1(1,1);
        lca[1][1]=1;
        for (int x=2;MAX_P>x;x++) {
            for (int y=1;n>=y;y++) {
                lca[x][y] = lca[x-1][lca[x-1][y]];
            }
        }
        for (int x=0;k>x;x++) {
            get_lca(pip[x]);
        }
        dfs2(1);
        int mx=-1;
        for (int x=1;n>=x;x++) {
//            cout<<"ans = "<<ans[x]<<endl;
            mx = max(mx,ans[x]);
        }
        printf("%d\n",mx);
    }
}

USACO 2016 January Contest, Platinum Problem 1. Fort Moo

http://www.usaco.org/index.php?page=viewproblem2&cpid=600

Tip : try to O(n^4) --> O(n^3 lg n)

O (n^3 lg n)

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

const int MAX_N = 206;
const int INF = 1e9 + 7;

struct Treap {
    Treap *lc,*rc;
    int val;
    int pri;
    int key;
    int mx;
    Treap(int _key,int _val) {
        key = _key;
        mx = val = _val;
        lc=rc=NULL;
        pri=rand();
    }
};

int Mx(Treap *t) {
    return t?t->mx:-INF;
}

int Val(Treap* t) {
    return t?t->val:-INF;
}

void pull(Treap* t) {
    t->mx = max(max(Mx(t->lc),Mx(t->rc)),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,int k,Treap* &a,Treap* &b) {
//    cout<<"in1\n";
    if (!t) a=b=NULL;
    else if (t->key <= k) {
//        cout<<"in\n";
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
//        cout<<"success pull\n";
    }
    else {
//        cout<<"what\n";
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

Treap* root;

void Build(int n) {
//    cout<<"n="<<n<<endl;
    root = NULL;
    for (int i=1;n>=i;i++) {
        root = merge(root,new Treap(i,-INF));
    }
}

void modify(int pos,int val) {
//    cout<<"pos = "<<pos<<endl;
    Treap *tl,*tr;
    split(root,pos-1,tl,root);
//    cout<<"Ready\n";
    split(root,pos,root,tr);
    root->val = root->mx = val;
    root = merge(merge(tl,root),tr);
//    cout<<"root->val = "<<root->val<<endl;
}

int query1(Treap* t,int lim) {
//    cout<<"t->ley = "<<t->key<<endl;
//    cout<<"t->val = "<<t->val<<endl;
    int l=Mx(t->lc);
    int m=t->val;
    int r=Mx(t->rc);
    if (r>=lim) return query1(t->rc,lim);
    else if (m>=lim) return t->key;
    else if (l>=lim) return query1(t->lc,lim);
    return t->key;
}

int query(int L,int R,int lim) {
//    cout<<"L="<<L<<" , R="<<R<<" , lim="<<lim<<endl;
    if (L>R) return -INF;
    Treap *tl,*tr;
    split(root,L-1,tl,root);
    split(root,R,root,tr);
//    cout<<"root->mx = "<<root->mx<<endl;
    int ret=-INF;
    if (root->mx >= lim) {
        ret = query1(root,lim);
    }
    root = merge(merge(tl,root),tr);
    return ret;
}

int mp[MAX_N][MAX_N];
char c[MAX_N];
int dp1[MAX_N][MAX_N]; //down
int dp2[MAX_N][MAX_N]; //right

int main () {
    srand(time(NULL));
    if (fopen("fortmoo.in","r")) {
        freopen("fortmoo.in","r",stdin);
        freopen("fortmoo.out","w",stdout);
    }
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        getchar();
        for (int i=1;n>=i;i++) {
            scanf("%s",c);
            for (int j=1;m>=j;j++) {
                mp[i][j] = (c[j-1]=='.'?1:0);
                if(mp[i][j]==0) {
                    dp1[i][j] = dp2[i][j] = -1;
                }
            }
        }
        for (int i=n;i>=1;i--) {
            for (int j=m;j>=1;j--) {
                if (i==n && mp[i][j]==1) {
                    dp1[i][j]=0;
                }
                if (j==m && mp[i][j]==1) {
                    dp2[i][j]=0;
                }
                if (mp[i][j]==1) {
                    if (i!=n)dp1[i][j] = dp1[i+1][j]+1;
                    if (j!=m)dp2[i][j] = dp2[i][j+1]+1;
                }
            }
        }
        Build(m);
        int ans=-1;
        for (int i=1;n>=i;i++) {
            for (int j=1;m>=j;j++) {
//                cout<<"i="<<i<<" , j="<<j<<endl;
                if (mp[i][j] == -1) continue;
                if (root->val == -INF) {
                    int k=j;
                    while (k<=m && mp[i][k]==1) {
//                        cout<<"k="<<k<<", dp = "<<dp1[i][k]<<endl;
                        modify(k,dp1[i][k]);
                        k++;
//                        cout<<"k="<<k<<endl;
                    }
                }
//                cout<<"on\n";
                modify(j,-INF);
                for (int k=i;n>=k && mp[k][j]==1;k++) {
//                    cout<<"k= "<<k<<endl;
//                    cout<<"Dp 2 = "<<dp2[k][j]<<endl;
                    int ret=-INF;
                    if (j+1<=m) ret=query(j+1,j+dp2[k][j],k-i);
//                    cout<<"ret = "<<ret<<endl;
                    if (ret == -INF) {
                        ret=j;
                    }
                    ret = (ret-j+1) * (k-i+1);
                    if (ret>ans) ans=ret;
                }
            }
        }
        printf("%d\n",ans);
    }
}

(POJ) 1741.Tree [樹分治]

http://poj.org/problem?id=1741

題目大意：給一個有權重的樹，找出所有的pair(u,v)，使得在樹上u到v的最短路徑<=k。

這題主要是用到樹分治的技巧，在這之前要知道  樹重心  怎麼求。

樹分治的技巧在於：找到一個點，求出各個子樹的解之後，在合併起來。

那用樹重心的意義是說，這樣遞迴深度只有lgN層，整體複雜度就可以是O( N lgN ~~~)

那，這題，所有的解答可以分成三種case (1)在某個子樹T裡面 (2)在兩個不同的子樹 (3)一個子樹到樹重心

對於(1)，繼續遞迴下去求解即可

對於(2)、(3)，掃過這棵樹，把邊sort之後，認真維護一下

詳細可以看code喔~~~

練習題：Codeforces 715C. Digit Tree

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

typedef pair<int,int> pii;
const int MAX_N = 1e4 + 3;
const int INF = 1e9+7;

vector<pii> edg[MAX_N]; //to & weight
int tree[MAX_N];
pii node[MAX_N];  //sum & max
bool visit[MAX_N];
pii path[MAX_N];
pii p[MAX_N];
int cnt[MAX_N];

int dfs1(int id,int& tr) {
    tree[tr++]=id;
    visit[id]=true;
    int ret=1;
    int mx=0;
    for (vector<pii>::iterator i=edg[id].begin();i!=edg[id].end();i++) {
        pii tmp=*i;
        if (visit[tmp.first] == false) {
            int temp = dfs1(tmp.first,tr);
            ret += temp;
            mx = max(mx,temp);
        }
    }
    node[id]=make_pair(ret,mx);
    return ret;
}

int get_cen(int id) {
    int tr=0;
    dfs1(id,tr);
    int sz=tr;
    int ret_mx=sz;
    int ret=-1;
    for (int i=0;tr>i;i++) {
        int tmp=tree[i];
        int mx = max(node[tmp].second,sz - node[tmp].first);
        if (ret_mx > mx) {
            ret = tmp;
            ret_mx=mx;
        }
        visit[tmp]=false;
    }
    return ret;
}

void dfs2(int id,int p,int t,int &tr) {
    tree[tr++]=id;
    visit[id]=true;
    path[id]=make_pair(p,t);
    for (vector<pii>::iterator i=edg[id].begin();i!=edg[id].end();i++) {
        pii tmp=*i;
        if (visit[tmp.first] == false) {
            dfs2(tmp.first,p+tmp.second,t,tr);
        }
    }
}

int solve(int root,int k) {
    int ret=0;
    int cen = get_cen(root);
    visit[cen]=true;
    //case 1 --- all in subtree
    for (vector<pii>::iterator iter=edg[cen].begin();iter!=edg[cen].end();iter++) {
        pii tmp=*iter;
        if (visit[tmp.first]==false) ret += solve(tmp.first,k);
    }
    //case 2---cen & 3---two other subtree
    //case 2
    path[cen]=make_pair(0,0);
    int tree_id=0;
    int pid=0;
    for (vector<pii>::iterator iter=edg[cen].begin();iter!=edg[cen].end();iter++) {
        pii tmp=*iter;
        int tr=0;
        cnt[tree_id]=0;
        if (visit[tmp.first]==false) dfs2(tmp.first,tmp.second,tree_id,tr);
        for (int i=0;tr>i;i++) {
            int temp=tree[i];
            visit[temp]=false;
            if (path[temp].first <= k) {
                ret++;
                p[pid++] = (path[temp]);
                cnt[tree_id]++;
            } 
        }
        tree_id++;
    }
    //case 3
    sort(p,p+pid);
    int tmpans=0;
    int len=pid;
    int j=len-1;
    for (int i=0;len>i;i++) {
        while (j>=0 && p[j].first+p[i].first>k) {
            cnt[p[j].second]--;
            j--;
        }
        if (j<0) break;
        tmpans += (j+1-cnt[p[i].second]);
    }
    ret += tmpans/2;
    visit[cen]=false;
    return ret;
}

int main() {
//    freopen("input.txt","r",stdin);
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        if (!n && !k) return 0;
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            visit[x]=false;
        }
        for (int x=0;n-1>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            edg[i].push_back(make_pair(j,k));
            edg[j].push_back(make_pair(i,k));
        }
        printf("%d\n",solve(1,k));
    }
}