(Codeforces) 743D. Chloe and pleasant prizes

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

http://codeforces.com/contest/743/submission/23001469

Tips : DFS !!!

my complexity : O(N lg N)
best : O(N) --- just keep using mx only

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

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

struct Node {
    Node *lc,*rc;
    LL val;
    Node() {
        lc=rc=NULL;
        val = -INF;
    }
    void pull() {
        val = max(lc->val,rc->val);
    }
};

vector<int> edg[MAX_N];
LL a[MAX_N];
LL cnt[MAX_N];   //total value XDDD
bool visit[MAX_N];

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        node->val = cnt[L];
        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,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->pull();
    return;
}

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

struct P {
    int st,ed;
    vector<int> sn;
    int parent;
} p[MAX_N];

void dfs1(int id,int &number,int par) {
    visit[id]=true;
    p[id].parent=par;
    p[id].st=number;
    int hahaha=number;
    cnt[hahaha] = a[id];
    for (auto iter=edg[id].begin();iter!=edg[id].end();iter++) {
        int tmp=*iter;
        if (!visit[tmp]) {
            int hahahaha=number;
            p[id].sn.push_back(tmp);
            number++;
            dfs1(tmp,number,id);
            cnt[hahaha] += cnt[hahahaha+1];
        }
    }
    p[id].ed=number;
}

LL ans;
Node* root;
int n;

void dfs(int id) {
    //cout<<"id = "<<id<<" , st = "<<p[id].st<<endl;
    LL ret=cnt[p[id].st];
    //cout<<"Ret = "<<ret<<endl;
    LL q=max(query(root,1,n,1,p[id].st-1),query(root,1,n,p[id].ed+1,n));
    //cout<<"q = "<<q<<endl;
    if (q==-INF) ;
    else ans = max(ans,ret + q);
    modify(root,1,n,p[id].st,-INF);
    for (auto i=p[id].sn.begin();i!=p[id].sn.end();i++) {
        int tmp=*i;
        dfs(tmp);
    }
    modify(root,1,n,p[id].st,cnt[p[id].st]);
}

main () {
    while (scanf("%I64d",&n) != EOF) {
        root = NULL;
        for (int i=1;n>=i;i++) {
            cnt[i]=0;
            visit[i]=false;
            edg[i].clear();
            p[i].sn.clear();
            scanf("%I64d",&a[i]);
        }
        for (int i=1;n-1>=i;i++) {
            int a,b;
            scanf("%I64d %I64d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        int number=1;
        dfs1(1,number,1);
        //cout<<"innnn\n";
        root = Build(1,n);
        ans = -INF;
        dfs(1);
        if (ans == -INF) puts("Impossible");
        else printf("%I64d\n",ans);
    }
}

(UVA) 10263 - Railway

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

算是點到直線距離公式?!?

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps = 1e-9;
const double INF = 1e9 + 7;

double add(double a,double b) {
    if (abs(a+b) < eps * (abs(a) + abs(b))) return 0;
    else return a+b;
}

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {}
    void pp() {
        cout<<"Point ("<<x<<","<<y<<")"<<endl;
    }
};

P MP(double x,double y) {
    return P{x,y};
}

P operator+(const P &p1,const P &p2) {
    return MP(add(p1.x,p2.x),add(p1.y,p2.y));
}

P operator-(const P &p1,const P &p2) {
    return MP(add(p1.x,-p2.x),add(p1.y,-p2.y));
}

P operator*(const double d,const P &p) {
    return MP(d*p.x,d*p.y);
}

double dot(const P &p1,const P &p2) {
    return add(p1.x*p2.x,p1.y*p2.y);
}

double cross(const P &p1,const P &p2) {
    return add(p1.x*p2.y,-p1.y*p2.x);
}

P intersection(P p1,P p2,P q1,P q2) {
    return p1 + cross(q1-p1,q2-q1)/cross(p2-p1,q2-q1)*(p2-p1);
}

bool on_seg(P p1,P p2,P q) {
    return cross(q-p1,q-p2)==0 && dot(q-p1,q-p2) <= 0;
}

int main () {
    P p;
    while (scanf("%lf",&p.x) != EOF) {
        scanf("%lf",&p.y);
        int n;
        scanf("%d",&n);
        P a;
        if (n>=1) scanf("%lf%lf",&a.x,&a.y);
        P ans;
        double mn = INF;
        while (n--) {
            P b;
            scanf("%lf%lf",&b.x,&b.y);
            double ax=b.y-a.y;
            double by=a.x-b.x;
            double c=a.y*b.x-a.x*b.y;
            double ret=abs(ax*p.x+by*p.y+c)/sqrt(ax*ax+by*by); //the smallest distance
            P inter = intersection(a,b,p,p-MP(ax,by));
            if (on_seg(a,b,inter)) {
                if (ret<mn) {
                    mn=ret;
                    ans = inter;
                }
            }
            else {
                if (sqrt(dot(p-a,p-a)) < mn) {
                    mn = sqrt(dot(p-a,p-a));
                    ans = a;
                }
                if (sqrt(dot(p-b,p-b)) < mn) {
                    mn = sqrt(dot(p-b,p-b));
                    ans = b;
                }
            }
            a=b;
        }
        printf("%.4f\n%.4f\n",ans.x,ans.y);
    }
}

(UVA) 11525 - Permutation

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

可以認真的研究裡面的性質！

加油！

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

const int MAX_N = 5e4 +6;

struct Treap {
    Treap *lc,*rc;
    int key;
    int pri;
    int sz;
    Treap(int _key) : key(_key),lc(NULL),rc(NULL),pri(rand()),sz(1) {}
};

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

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

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

Treap* root;

void deleted(int val) {
    Treap *tl,*tr;
    split(root,val-1,tl,root);
    split(root,val,root,tr);
    root = merge(tl,tr);
}

int query(Treap* t,int cnt) {   //number cnt-th
    if (Sz(t->lc) + 1 == cnt) return t->key;
    else if (Sz(t->lc) + 1 > cnt) return query(t->lc,cnt);
    else return query(t->rc,cnt - 1 - Sz(t->lc));
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        root = NULL;
        for (int i=1;n>=i;i++) root = merge(root,new Treap(i));
        for (int i=1;n>=i;i++) {
            if (i!=1) printf(" ");
            int t;
            scanf("%d",&t);
            int ret=query(root,t+1);
            deleted(ret);
            printf("%d",ret);
        }
        puts("");
    }
}

(UVA) 1231 - ACORN

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

Tips : DP

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

const int MAX_N = 2006;

int dp[MAX_N][MAX_N];
int mx[MAX_N];
int cnt[MAX_N][MAX_N];

int main () {
    int T;
    while (scanf("%d",&T) != EOF) {
        if (T == 0) break;
        while (T--) {
            int n,m,f;
            scanf("%d %d %d",&n,&m,&f);
            memset(cnt,0,sizeof(cnt));
            memset(dp,0,sizeof(dp));
            memset(mx,0,sizeof(mx));
            for (int x=1;n>=x;x++) {
                int k;
                scanf("%d",&k);
                while (k--) {
                    int i;
                    scanf("%d",&i);
                    cnt[x][i]++;
                }
            }
            for (int j=1;m>=j;j++) {
                for (int i=1;n>=i;i++) {
                    if (j-f > 0) dp[i][j] = cnt[i][j] + max(mx[j-f],dp[i][j-1]);
                    else dp[i][j] = cnt[i][j] + dp[i][j-1];
                    //cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
                    mx[j] = max(mx[j],dp[i][j]);
                }
            }
            int ans=-1;
            for (int i=1;n>=i;i++) {
                ans = max(ans,dp[i][m]);
            }
            printf("%d\n",ans);
        }
    }
}

(UVA) 11262 - Weird Fence

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

Tips : binary search + bipartite graph matching

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

const int MAX_N = 106;

int n,k;
int x[MAX_N],y[MAX_N],type[MAX_N];
vector<int> edg[MAX_N];
int match[MAX_N];
int used[MAX_N];

bool dfs(int id) {
    used[id] = true;
    int len=edg[id].size();
    for (int i=0;len>i;i++) {
        int u=edg[id][i];
        int w=match[u];
        if (w < 0 || !used[w] && dfs(w)) {
            match[id] = u;
            match[u] = id;
            return true;
        }
    }
    return false;
}

int matching() {
    int ret=0;
    memset(match,-1,sizeof(match));
    for (int i=1;n>=i;i++) {
        if (match[i] < 0) {
            memset(used,0,sizeof(used));
            if (dfs(i)) {
                ret++;
            }
        }
    }
    return ret;
}

bool check(int id) {
    for (int i=0;n>=i;i++) {
        edg[i].clear();
    }
    for (int i=1;n>=i;i++) {
        for (int j=i+1;n>=j;j++) {
            if (type[i]+type[j]==0 && (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= id*id) {
                edg[i].push_back(j);
                edg[j].push_back(i);
            }
        }
    }
    int ret=matching();
    return ret>=k;
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d %d",&n,&k);
        int cnt=0;
        for (int i=1;n>=i;i++) {
            char s[10];
            scanf("%d %d %s",&x[i],&y[i],s);
            if (!strcmp(s,"blue")) type[i] = 1;
            else type[i]=-1,cnt++;
        }
        if (min(cnt,n-cnt) < k) {
            puts("Impossible");
            continue;
        }
        int L=0,R=10006;
        while (R-L!=1) {
            int mid=(L+R)>>1;
            if (check(mid)) R=mid;
            else L=mid;
        }
        printf("%d\n",R);
    }
}

(Codeforces) 665E. Beautiful Subarrays

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

http://codeforces.com/contest/665/submission/22943013

感覺上，好像看到XOR，就要想到trie的樣子(上次有一題Div.2的pD也是一樣)

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

const int MAX_N = 1e6 + 6;

struct Node {
    Node *lc;
    Node *rc;
    int cnt;
    Node() {
        lc=rc=NULL;
        cnt=0;
    }
};

int Cnt(Node* t) {
    return t?t->cnt:0;
}

void pull(Node* node) {
    node->cnt = Cnt(node->lc) + Cnt(node->rc);
}

int pre[MAX_N];
int a[MAX_N];
int pow2[32];

void add(Node* node,int k,int id) {   //remember to start from 31
    //cout<<"k = "<<k<<" , id = "<<id<<endl;
    if (k==0) {
        node->cnt++;
        return;
    }
    else {
        if (id >= pow2[k-1]) {
            //digit 1
            if (!node->rc) node->rc= new Node();
            add(node->rc,k-1,id-pow2[k-1]);
        }
        else {
            //digit 0
            if (!node->lc) node->lc = new Node();
            add(node->lc,k-1,id);
        }
        pull(node);
    }
}

int query(Node* node,int k,int id,int depth) {  //depth from 31
    //cout<<"k = "<<k<<" , id = "<<id<<", depth = "<<depth<<endl;
    if (!node) return 0;
    else if (depth == 0) return node->cnt;
    int digitk,digitid;
    if (k >= pow2[depth-1]) digitk=1;
    else digitk=0;
    if (id >= pow2[depth-1]) digitid=1;
    else digitid=0;
    if (digitk==1 && digitid == 1) {
        return query(node->lc,k-pow2[depth-1],id-pow2[depth-1],depth-1);
    }
    else if (digitk == 1 && digitid == 0) {
        return query(node->rc,k-pow2[depth-1],id,depth-1);
    }
    else if (digitk == 0 &&digitid == 1) {
        return Cnt(node->lc) + query(node->rc,k,id-pow2[depth-1],depth-1);
    }
    else {
        return Cnt(node->rc) + query(node->lc,k,id,depth-1);
    }
}

int main () {
    pow2[0]=1;
    for (int i=1;32>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF) {
        Node *root = new Node();
        pre[0]=0;
        for (int x=1;n>=x;x++) {
            scanf("%d",&a[x]);
            pre[x] = pre[x-1] ^ a[x];
        }
        add(root,31,0);
        long long ans=0;
        for (int i=1;n>=i;i++) {
            ans += query(root,k,pre[i],31);
            //cout<<"\n\nans = "<<ans<<"\n\n";
            add(root,31,pre[i]);
        }
        printf("%I64d\n",ans);
    }
}

(UVA) 1172 - The Bridges of Kolsberg

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

Tips : LCS + DP

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

typedef pair<int,int> pii;
const int MAX_N = 1006;

pii dp[MAX_N][MAX_N];
map<string,int> mp;
int a[MAX_N],b[MAX_N],c[MAX_N],d[MAX_N];

pii operator+(const pii &p1,const pii &p2) {
    return make_pair(p1.first+p2.first,p1.second+p2.second);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        mp.clear();
        int id=1;
        for (int x=1;n>=x;x++) {
            string s,t;
            int v;
            cin >>s >>t >> v;
            int ret=mp[t];
            if (!ret) {
                ret = mp[t] = id++;
            }
            a[x] = ret;
            b[x] = v;
        }
        int m;
        scanf("%d",&m);
        for (int x=1;m>=x;x++) {
            string s,t;
            int v;
            cin >>s >>t >> v;
            int ret=mp[t];
            if (!ret) {
                ret = mp[t] = id++;
            }
            c[x] = ret;
            d[x] = v;
        }
        for (int i=0;n>=i;i++) {
            for (int j=0;m>=j;j++) {
                dp[i][j] = make_pair(0,0);
            }
        }
        for (int i=1;n>=i;i++) {
            for (int j=1;m>=j;j++) {
                pii mx = max(dp[i-1][j],dp[i][j-1]);
                pii ret = make_pair(0,0);
                if (a[i] == c[j]) {
                    ret = make_pair(b[i]+d[j],-1) + dp[i-1][j-1];
                }
                dp[i][j] = max(mx,ret);
            }
        }
        printf("%d %d\n",dp[n][m].first,-dp[n][m].second);
    }
}