USACO 2013 November Contest, Silver Problem 3. Pogo-Cow

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

Main idea : DP

note that Bessie can jump to the positive infinite or negative infinite

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

typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 1006;
const LL INF = 1e17 + 6;
const int oo = 1e9 + 7;

LL dp[MAX_N][MAX_N];
LL mx[MAX_N][MAX_N];
pii a[MAX_N];

LL dis(LL i,LL j) {
 if (i<1) return INF;
 return a[j].first - a[i].first;
}

int main () {
 if (fopen("pogocow.in","r")) {
     freopen("pogocow.in","r",stdin);
     freopen("pogocow.out","w",stdout);
    }
 int n;
 while (scanf("%d",&n) != EOF) {
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
         scanf("%d %d",&i,&j);
         a[x] = make_pair(i,j);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
     LL ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
        //above is 順時針
        //下面��逆時針
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
//         scanf("%d %d",&i,&j);
         a[x] = make_pair(-a[x].first+oo,a[x].second);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
//     ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
     printf("%lld\n",ans);
    }
}

USACO 2013 November Contest, Silver Problem 1. Farmer John has no Large Brown Cow

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

Tips : binary Search

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

typedef long long LL;
const int MAX_N = 106;
const int MAX_K = 26;

struct P {
 int n;
 int id;
 string a[MAX_K];
} p[MAX_N],ans;

bool operator<(const P &p1,const P &p2) {
// assert(p1.n == p2.n);
 int n=p1.n;
 for(int x=0;n>x;x++) {
     if (p1.a[x] < p2.a[x]) return true;
     else if (p1.a[x] > p2.a[x]) return false;
    }
 return false;
}

vector<string> mp[MAX_N];

int main () {
 if (fopen("nocow.in","r")) {
     freopen("nocow.in","r",stdin);
     freopen("nocow.out","w",stdout);
    }
 int n,k;
 while (scanf("%d %d",&n,&k) != EOF) {
     string s;
     int m;
     getchar();
     for (int x=0;n>x;x++) {
         getline(cin,s);
         int sz=s.size();
         string i="";
         int cnt=0;
         for (int y=19;sz-4>y;y++) {
             if (s[y] == ' ') {
//                 cout<<"get "<<i<<endl;
                 mp[cnt].push_back(i);
                 p[x].a[cnt++]=i;
                 i="";
                }
             else {
                 i+= " ";
                 i[i.size()-1]=s[y];
                }
            }
         p[x].n=cnt;
         m=cnt;
        }
     LL tot=1;
     string INF = " ";
     INF[0] = 'z'+1;
     for (int x=0;m>x;x++) {
         mp[x].push_back("A");
         mp[x].push_back(INF);
         sort(mp[x].begin(),mp[x].end());
         mp[x].resize(unique(mp[x].begin(),mp[x].end()) - mp[x].begin());
         tot *= (mp[x].size() - 2);
//         for (int y=1;mp[x].size()-2>=y;y++) cout<<mp[x][y]<<' ';
//         cout<<endl;
        }
     sort(p,p+n);
     p[n].a[0] = "}";
     p[n].id = n+1;
     for (int x=0;n>x;x++) {
         p[x].id = x+1;
        }
     ans.n=m;
     for (int x=0;m>x;x++) {
         ans.a[x] = INF;
        }
     LL ss=0;
     for (int x=0;m>x;x++) {

         tot/=(mp[x].size()-2);
//         cout<<"tot = "<<tot<<endl;
//         cout<<"ss = "<<ss<<endl;
         int L=0,R=mp[x].size()-1;
         while (R-L!=1) {
             int mid=(L+R)>>1;
             ans.a[x] = mp[x][mid];
//             cout<<"mid = "<<mid<<endl;
             P tmp=*lower_bound(p,p+n,ans);
             int delta=1;
             if (!(tmp<ans) && ! (ans<tmp) ) delta = 0;
//             cout<<"val = "<<ss + (mid)*tot - (tmp).id + delta<<endl;
             if (ss + (mid)*tot - (tmp).id + delta>= k) R=mid;
             else L=mid;
            }
         ss += (R-1)*tot;
         ans.a[x] = mp[x][R];
        }
     for (int x=0;m>x;x++) {
         if (x!=0) cout<<' ';
         cout<<ans.a[x];
        }
     cout<<endl;
    }
}

USACO 2014 US Open, Silver Problem 2. Dueling GPSs

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

第一次用dijkstrea

(待補詳解)

//first time to ude dijistra
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <queue>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

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

vector<pii> edg[MAX_N];
int a[MAX_M],b[MAX_M],p[MAX_M],q[MAX_M],r[MAX_M];
int d[MAX_N];

#define int long long

main () {
    if (fopen("gpsduel.in","r")) {
        freopen("gpsduel.in","r",stdin);
        freopen("gpsduel.out","w",stdout);
    }
//    freopen("5.in","r",stdin);
    int n,m;
    while (scanf("%lld %lld",&n,&m) != EOF) {
        for (int x=0;n>=x;x++) {
            edg[x].clear();
        }
        for (int x=1;m>=x;x++) {
            scanf("%lld %lld %lld %lld",&a[x],&b[x],&p[x],&q[x]);
            a[m+x]=b[x];
            b[m+x]=a[x];
            p[m+x]=p[x];
            q[m+x]=q[x];
            edg[a[x]].push_back(make_pair(b[x],x));
            edg[b[x]].push_back(make_pair(a[x],m+x));
            r[x] = 2;
            r[m+x] = 2;
        }
        //decide route P
        priority_queue<piii,vector<piii>,greater<piii> > pq;
        fill(d,d+MAX_N,INF);
        d[n]=0;
        pq.push(MP(0,MP(n,2*m+1)));  //value,to,from(the id)
        while (!pq.empty()) {
            piii tmp=pq.top();
            pq.pop();
            int t=tmp.S.F;
            if (d[t] < tmp.first) continue;
            else if (d[t] == tmp.first) {
                if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--;
                if (tmp.second.S!=2*m+1) continue;
            }
            else if (d[t] > tmp.first) {
                if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--;
                d[t]=tmp.first;
            }
            for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                pii tmp=*i;
                int x=tmp.first,y=tmp.second;
                if (y<=m) continue;
                if (d[x] >= d[t] + p[y]) {
                    pq.push(MP(d[t] + p[y],MP(x,y)));
                }
            }
        }
//        for (int x=1;2*m>=x;x++) cout<<"r["<<x<<"] = "<<r[x]<<endl;
        //decide route Q
        fill(d,d+MAX_N,INF);
        d[n]=0;
        pq.push(MP(0,MP(n,2*m+1)));  //value,to,from(the id)
        while (!pq.empty()) {
            piii tmp=pq.top();
            pq.pop();
            int t=tmp.S.F;
            if (d[t] < tmp.first) continue;
            else if (d[t] == tmp.first) {
                if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--;
                if (tmp.second.S!=2*m+1) continue;
            }
            else if (d[t] > tmp.first) {
                if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--;
                d[t]=tmp.first;
            }
            for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                pii tmp=*i;
                int x=tmp.first,y=tmp.second;
                if (y<=m) continue;
                if (d[x] >= d[t] + q[y]) {
                    pq.push(MP(d[t] + q[y],MP(x,y)));
                }
            }
        }
//        for (int x=1;2*m>=x;x++) {
//            if (r[x] < 0)cout<<"r["<<x<<"] = "<<r[x]<<endl;
//            assert(0<=r[x]);
//        }
        //count the answer now
        fill(d,d+MAX_N,INF);
        d[1]=0;
        pq.push(MP(0,MP(1,2*m+1)));  //value,to,from(the id)
        while (!pq.empty()) {
            assert(pq.size() <= m);
            piii tmp=pq.top();
            pq.pop();
            int t=tmp.S.F;
//            cout<<"t = "<<t<<endl;
            if (d[t] <= tmp.first && t!=1) continue;
            if (d[t] > tmp.first) {
                d[t] = tmp.first;
            }
            for (auto i=edg[t].begin();i!=edg[t].end();i++) {
                pii tmp=*i;
                int x=tmp.first,y=tmp.second;
                if (y>m) continue;
                if (d[x] > d[t] + r[y]) {
                    pq.push(MP(d[t] + r[y],MP(x,y)));
                }
            }
        }
        printf("%lld\n",d[n]);
    }
}

USACO 2014 US Open, Silver Problem 1. Fair Photography

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

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

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

pii a[MAX_N];
int pre[MAX_N];
int mx[2*MAX_N];

int main () {
    if (fopen("fairphoto.in","r")) {
        freopen("fairphoto.in","r",stdin);
        freopen("fairphoto.out","w",stdout);
    }
    int n;
    while (scanf("%d",&n) != EOF) {
        memset(pre,0,sizeof(pre));
        fill(mx,mx+2*MAX_N,-INF);
        for (int x=1;n>=x;x++) {
            int i;
            char c;
            scanf("%d %c",&i,&c);
            a[x] = make_pair(i,c=='W'?1:-1);
        }
        sort(a+1,a+n+1);
        for (int x=1;n>=x;x++) {
            pre[x] = pre[x-1] + a[x].second;
            mx[pre[x]+MAX_N] = x;
        }
        for (int x=2*MAX_N-2;x>=0;x--) {
            mx[x] = max(mx[x],mx[x+1]);
        }
        int ans=-INF;
        for (int x=1;n>=x;x++) {
            int s = -a[x].second + pre[x];
            if (x==1) s=-a[x].second;
            s += MAX_N;
            int t=mx[s];
//            cout<<"x = "<<x<<" , s= "<<s<<" , t ="<<t<<endl;
            if (t==-INF) continue;
            if ((t-x)%2==0) t--;
            ans = max(ans,a[t].first-a[x].first);
        }
        printf("%d\n",ans);
    }
}

(UVA) 10805 - Cockroach Escape Networks

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

主要的想法是說：先做一次all-pair shortest path，得知每個點與每個點的距離，之後對於每個點，抓離這兩個點最遠距離加起來的最小值，理論上就是答案。

但是，試試看這筆測資：

6 5
0 1
0 2
0 3
3 4
3 5

答案應該是3，不是4！

怎麼會這樣？

原來，在 "邊的中間" 的點，也有可能是選項喔！

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

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

int dp[MAX_N][MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    for (int qq=1;T>=qq;qq++) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;MAX_N>x;x++) {
            for (int y=1;MAX_N>y;y++) {
                dp[x][y] = INF;
                if (x==y) dp[x][y] = 0;
            }
        }
        int id=n+1;
        for (int x=1;m>=x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            i++;
            j++;
            dp[i][id] = dp[id][i] = 1;
            dp[j][id] = dp[id][j] = 1;
            id++;
        }
        int tmpn=n;
        n = id-1;
        for (int k=1;n>=k;k++) {
            for (int i=1;n>=i;i++) {
                for (int j=1;n>=j;j++) {
                    dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
//                    cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
                }
            }
        }
        int ans = INF;
        for (int i=1;n>=i;i++) {
            sort(dp[i]+1,dp[i]+tmpn+1);
            ans = min(ans , dp[i][tmpn]+dp[i][tmpn-1]);
        }
        printf("Case #%d:\n",qq);
        printf("%d\n",ans/2);
        puts("");
    }
}

(Zj) b903: 高中組-第九題：超級電池

http://zerojudge.tw/ShowProblem?problemid=b903

我首殺耶，開心XD

74% 解法：dp[i][j]代表選前i個超級石和前j個鑰石所得最大的能力值是多少，然後用類似LCS的更新手法，O(n^2)

100% 解法：先把K個配對按照 "超級石" 的大小排序，之後開一個dp陣列，dp[i]代表說，如果最後用了第i個 "鑰石" ， 所能獲得最大的點數是多少。那更新dp陣列的轉移方程就是(假設現在超級石編號為a，鑰石編號為b，能力值為c)dp[b] = max(dp[1~b-1] + c,dp[b])，那，我們可以用segment tree來維護dp陣列，這樣複雜度就可以壓到O(n lg n)

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

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

struct Node {
    Node* lc;
    Node* rc;
    LL val;
    Node() {
        lc=rc=NULL;
        val = 0;
    }
};

LL pull(LL lc,LL rc) {
    return max(lc,rc);
}

Node* Build(int L,int R) {
    Node* node =new Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int pos,LL val) {
    if (L==R) {
        node->val = val;
        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->val = pull(node->lc->val,node->rc->val);
    return;
}

LL query(Node* node,int L,int R,int l,int r) {
    if (L>r || l>R) return 0;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return pull(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

piii ipt[MAX_N];

int main () {
    int n,m,k;
    while (scanf("%d %d %d",&n,&m,&k) != EOF) {
        for (int x=1;k>=x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            ipt[x] = make_pair(make_pair(i,-j),k);
        }
        sort(ipt+1,ipt+k+1);
        Node* root = Build(1,m);
        for (int x=1;k>=x;x++) {
            int i=ipt[x].first.first,j=-ipt[x].first.second,k=ipt[x].second;
            LL t=query(root,1,m,1,j-1);
            modify(root,1,m,j,max(query(root,1,m,j,j),t+k));
        }
        printf("%lld\n",root->val);
    }
}

(Zj) b692: 第五題：棕櫚儀式

http://zerojudge.tw/ShowProblem?problemid=b692

仔細想想後，可以發現說，這題可以簡化成：有n個數字，你可以掛正負號，但是至少有一個正的 & 一個負的，然後最後使 sum 最大。

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

typedef long long LL;
const int MAX_N = 1e6 + 6;

LL a[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=1;n>=x;x++) {
            scanf("%lld",&a[x]);
        }
        sort(a+1,a+n+1);
        if (n==1) printf("%lld\n",a[1]);
        else {
            long long ans = 0;
            ans = a[n] - a[1];
            for (int x=2;n-1>=x;x++) {
                if (a[x] > 0) ans += a[x];
                else ans -= a[x];
            }
            printf("%lld\n",ans);
        }
    }
}