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 2015 December Contest, Gold Problem 2. Fruit Feast

每個方法可以表現成x*A+y*B + (z*A + u*B)/2

那麼，就可以輕鬆過了XDDD

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_T = 5000002;

int dp[MAX_T];

int main () {

freopen("feast.in","r",stdin);

freopen("feast.out","w",stdout);

int T,a,b;

while (scanf("%d %d %d",&T,&a,&b) != EOF) {

memset(dp,0,sizeof(dp));

for (int x=a;T>=x;x+=a) dp[x]=x;

for (int x=b;T>=x;x+=b) dp[x]=x; 

for (int x=1;T>=x;x++) {

if (dp[x]==x && x+b<=T) dp[x+b]=x+b;

}

// puts("hi");

int ans=-1;

for (int x=1;T>=x;x++) {

// cout << "dp["<<x<<"]="<<dp[x]<<endl;

if (dp[x]==x) {

int t1=dp[x];

if (ans<t1) ans=t1;

int t2=dp[x] + (a/2);

if (ans<t2 && t2<=T) ans=t2;

t1=dp[x] + (b/2);

if (ans<t1 && t1<=T) ans=t1;

t2=dp[x] + (a+b)/2;

if (ans<t2 && t2<=T && a+b<=T) ans=t2;

}

// cout<<ans<<endl;

} 

printf("%d\n",ans);

}

}

USACO 2015 January Contest, Gold Problem 2. Moovie Mooving [位元dp]

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

我當初看的時候，也不知道題目再做什麼

再想想，就發現好像是bitmask的dp!!!

於是，就開了dp[1<<MAX_N][MAX_N]陣列，紀錄1<<MAX_N最後是MAX_N最長可以延伸到哪裡。

但是，不幸的很，TLE了！！

後來想想，後面那個維度根本用不到！！！(之前做bitmask有用到所以就不小心在腦海中留下不好印象XDD)

於是，就AC了

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

const int MAX_N = 21;
vector <int> C[MAX_N];
int t[MAX_N];
int dp[(1<<MAX_N)];
int n,l;

int count_bit(int x) {
    int ret=0;
    while (x>0) {
        if (x!=(x/2)+(x/2)) ret++;
        x/=2;
    }
    return ret;
}

int get_dp(int i,int j) {   //i-->which n , j-->dp_val
//    cout << "get " << i << " and " << j << endl;
    int tmp=j;
    int id=lower_bound(C[i].begin(),C[i].end(),tmp) - C[i].begin();
    
    if (C[i][id]!=j) id--;
//    cout<<"("<<j<<" vs "<<C[i][id]<<")";
    if (C[i][id]==-1) return 0;
//    puts("still alive ");
    return max(C[i][id]+t[i] , j);
}

int main () {
    if (fopen("movie.in","r")) {
        freopen("movie.in","r",stdin);
        freopen("movie.out","w",stdout);
    }
    
    int k,qq;
    while (scanf("%d %d",&n,&l) != EOF) {
        for (int x=0;n>x;x++) {
            scanf("%d %d",&t[x],&k);
            C[x].clear();
            C[x].push_back(-1);
            for (int y=0;k>y;y++) {
                scanf("%d",&qq);
                C[x].push_back(qq);
            }
        }
        memset(dp,0,sizeof(dp));
        //bitmask DP
        for (int i=0;n>i;i++) {
            dp[(1<<i)]=get_dp(i,0);
        }
        
        for (int x=1;(1<<n)>=x;x++) {
            int tmp=x;
            int i=0;
            
            for (int j=0;n>j;j++) {
                if (((1<<j)|x)!=x)dp[((1<<j)|x)]=max(dp[((1<<j)|x)],get_dp(j,dp[x]));
            }
                
    
//            cout<<"x="<<x<<" : "<<count_bit(x)<<endl;
        }
        int ans=19343;
        for (int x=0;(1<<n)>=x;x++) {
//            cout << "x = " <<x << " : ";
            for (int y=0;1>y;y++) {
                if (dp[x]>=l && count_bit(x)<ans) ans=count_bit(x);
//                cout<<dp[x][y] << ' ';
            }
//            cout << endl;
        }
        printf("%d\n",(ans==19343?-1:ans));
    }
}