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

(Codeforces) 208E. Blood Cousins

會寫題目的原因：http://code-drills.com/   (Codeforces Problem Recommendations)

http://codeforces.com/contest/208/problem/E

http://codeforces.com/contest/208/submission/22940709

主要想法：

先建LCA，前序走訪整棵樹，記錄每個深度出現的點。

然後，對於每筆詢問，二分蒐網上p是否一樣(因為前面是用前序走訪)

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

const int MAX_N = 1e5 + 6;
const int MAX_P = 21;

vector<int> edg[MAX_N];
vector<int> d[MAX_N];
int lca[MAX_P][MAX_N];
int rhs[MAX_P][MAX_N];  //right highest son
int lhs[MAX_P][MAX_N];  //left highest son
int lc[MAX_N];
int rc[MAX_N];
int depth[MAX_N];
int ans[MAX_N];
int iden[MAX_N];

void dfs(int id,int cur_depth) {
    iden[id] = d[cur_depth].size();
    d[cur_depth].push_back(id);
    depth[id] = cur_depth;
    for (vector<int>::iterator iter=edg[id].begin();iter != edg[id].end();iter++) {
        int tmp = *iter;
        if (depth[tmp] == -1) {
            dfs(tmp,cur_depth+1);
        }
    }
}

int go(int s,int t) {
    int p[MAX_P];
    memset(p,0,sizeof(p));
    int id=0;
    while (t>0) {
        p[id++]=t%2;
        t/=2;
    }
    for (int i=0;id>i;i++) {
        //cout<<"S = "<<s<<endl;
        if (p[i]) {
            s = lca[i][s];
        }
    }
    return s;
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            d[x].clear();
        }
        lca[0][0]=0;
        memset(depth,-1,sizeof(depth));
        for (int x=1;n>=x;x++) {
            int i;
            scanf("%d",&i);
            lca[0][x]=i;
            edg[i].push_back(x);
        }
        dfs(0,0);
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                lca[i][j] = lca[i-1][lca[i-1][j]];
            }
        }
        int q;
        scanf("%d",&q);
        for (int qq=0;q>qq;qq++) {
            int v,p;
            scanf("%d %d",&v,&p);
            int ret=go(v,p);
            if (!ret) {
                ans[qq] = 0;
                continue;
            }
            int cnt=0;
            int cur=depth[v];
            //right side
            int L=iden[v],R=d[cur].size();
            while (R-L != 1) {
                int mid=(L+R)>>1;
                if (go(d[cur][mid],p) == ret) L=mid;
                else R=mid;
            }
            cnt += (L - iden[v]);
            //left side
            L=-1,R=iden[v];
            while (R-L != 1) {
                int mid=(L+R)>>1;
                if (go(d[cur][mid],p) == ret) R=mid;
                else L=mid;
            }
            cnt += (iden[v] - R);
            ans[qq] = cnt;
        }
        for (int x=0;q>x;x++) {
            if (x) printf(" ");
            printf("%d",ans[x]);
        }
        puts("");
    }
}

(UVA) 11506 - Angry Programmer [max flow = min cut]

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

max flow = min cut

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

struct Edge {
    int to,cap,rev;
};

const int MAX_N = 56;
const int MAX_M = 1106;
const int INF = 1e9 + 7;

Edge MP(int _to,int _cap,int _rev) {
    return (Edge){_to,_cap,_rev};
}

vector<Edge> edg[MAX_M];
int iter[MAX_M];
int level[MAX_M];

void add_edge(int from,int to,int cap) {
    edg[from].push_back(MP(to,cap,edg[to].size()));
    edg[to].push_back(MP(from,0,edg[from].size()-1));
}

void bfs(int s) {
    memset(level,-1,sizeof(level));
    level[s]=0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int t=que.front();
        //cout<<"t = "<<t<<" , length = "<<edg[t].size()<<endl;
        que.pop();
        int len=edg[t].size();
        for (int i=0;len>i;i++) {
            Edge e=edg[t][i];
            //cout<<"e.to = "<<e.to<<" , e.cap = "<<e.cap<<endl;
            if (level[e.to] < 0 &&e.cap>0) {
                //cout<<"in "<<e.to<<endl;
                level[e.to] = level[t] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v,int t,int f) {
    if (v==t) return f;
    int len=edg[v].size();
    for (int &i=iter[v];len>i;i++) {
        Edge &e = edg[v][i];
        if (level[e.to] > level[v] && e.cap > 0) {
            int d=dfs(e.to,t,min(e.cap,f));
            if (d>0) {
                e.cap -= d;
                edg[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow=0;
    while (true) {
        bfs(s);
        if (level[t] == -1) break;
        //cout<<"hello, world\n";
        memset(iter,0,sizeof(iter));
        int f;
        while ((f=dfs(s,t,INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

int main () {
    int m,w;
    while (scanf("%d %d",&m,&w) != EOF) {
        if (!m && !w) break;
        for (int x=0;MAX_M>x;x++) {
            edg[x].clear();
        }
        for (int i=2;m-1>=i;i++) {
            int a,b;
            scanf("%d %d",&a,&b);
            add_edge(a,a+m,b);
            add_edge(a+m,a,b);
        }
        for (int x=0;w>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            if (i>j) swap(i,j);
            if (i==1 && j==m) {
                add_edge(i,j,k);
            }
            else if (i == 1) {
                add_edge(i,j+m,k);
            }
            else if (j==m) {
                add_edge(i,j,k);
            }
            else {
                add_edge(i,j+m,k);
                add_edge(j,i+m,k);
            }
        }
        printf("%d\n",Dinic(1,m));
    }
}

N lg N 最長回文子字串

用hash，枚舉端點，用二分搜。

放個最長回文的題目：http://acm.cs.nthu.edu.tw/problem/10378/

(話說在zerojudge 的 d978 好像要用 O(N) 耶！ )

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

typedef long long LL;
const int MAX_N = 1e6 + 6;
const int MAX_P = 31;
const LL mod = 1e9 + 7;

char s[MAX_N];
char c[MAX_N];
LL pow[MAX_N];
LL pre[MAX_N];
LL suf[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",s);
        c[0]=' ';
        c[1]='*';
        int len=2;
        for (int i=0;s[i] != '\0';i++) {
            c[len++] = s[i];
            if (s[i+1] != '\0') c[len++] = '*';
        }
        c[len++]='*';
        c[len+1]='\0';
        pow[0] = 1;
        len--;
        for (int i=1;len>=i;i++) {
            pow[i] = pow[i-1] * MAX_P;
            pow[i] %= mod;
            pre[i] = ( pre[i-1] + (c[i] * pow[i])%mod ) %mod;
        }
        suf[len+1] = 0;
        for (int i=len;i>=1;i--) {
            suf[i] = ( suf[i+1] + (c[i] * pow[len-i + 1])%mod) % mod;
        }
        //cout<<"c = "<<c<<endl;
        int ans=0;
        for (int i=2;len>i;i++) {
            //i is the middle point
            //cout<<"i-1 = "<<i-1<<" , len - i = "<<len - i<<" i = "<<i<<endl;
            int L=0,R=min(i-1,len-i)+1;  //L is okay
            if (R == 0) {
                continue;
            }
            while (R-L != 1) {
                int mid=(L+R)>>1;
                LL r = (pre[i+mid]-pre[i-1]+mod)%mod;
                LL l = (suf[i-mid]-suf[i+1]+mod)%mod;
                //cout<<"i = "<<i<<" , r = "<<r<<" , l = "<<l<<" , mid = "<<mid<<endl;
                if (len/2+1 == i) ;
                else if (i < len/2+1) r = r*pow[2*(len/2+1-i)]%mod;
                else if (i > len/2+1) l = l*pow[2*(i-len/2-1)]%mod;
                //cout<<"mid = "<<mid<<" , l = "<<l<<" , r = "<<r<<endl;
                if (l==r) L=mid;
                else R=mid;
            }
            //cout<<"i = "<<i<<" , L = "<<L<<endl;
            if (i%2==1) ans = max(ans,L);
            else ans = max(ans,L);
        }
        printf("%d\n",ans);
    }
}

(UVA) 11576 - Scrolling Sign

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

applicant of KMP

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

const int MAX_N = 106;

int f[MAX_N];

void build(string s) {
    int len=s.size();
    int pos=-1;
    f[0]=-1;
    for (int i=1;len>i;i++) {
        while (pos != -1 && s[pos+1] != s[i]) {
            pos = f[pos];
        }
        if (s[pos+1] == s[i]) pos++;
        f[i] = pos;
    }
}

int match(string a,string b) {
    int lena=a.size(),lenb=b.size();
    int mx=-1;
    int pos=-1;
    for (int i=0;lena > i;i++) {
        while (pos != -1 && a[i] != b[pos+1]) {
            pos = f[pos];
        }
        if (a[i] == b[pos+1]) pos++;
        if (i==lena-1) return pos;
        if (pos == lenb - 1) {
            mx = pos;
            pos = f[pos];
        }
        else {
            mx = max(mx,pos);
        }
    }
    return mx;
}

string s[MAX_N];

int main () {
    int T;
    cin >> T;
    while (T--) {
        int a,b;
        cin >> a >> b;
        int ans=0;
        for (int x=0;b>x;x++) {
            cin >> s[x];
            ans += s[x].size();
            if (x==0) continue;
            build(s[x]);
            //cout <<"match = "<<match(s[x-1],s[x])<<endl;
            ans -= match(s[x-1],s[x]);
            ans -= 1;
        }
        printf("%d\n",ans);
    }
}

(UVA) 455 - Periodic Strings

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

one problem similar to the last one!

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

const int MAX_N = 86;

int f[MAX_N];

void build(string s) {
    int len=s.size();
    int pos=-1;
    f[0] = -1;
    for (int i=1;len > i;i++) {
        while (pos != -1 && s[pos+1] != s[i]) {
            pos = f[pos];
        }
        if (s[pos+1] == s[i]) pos++;
        f[i] = pos;
    }
}

int main () {
    int T;
    cin >> T;
    int cases=0;
    while (T--) {
        if (cases) puts("");
        ++cases;
        string s;
        cin >> s;
        build(s);
        int len=s.size();
        if (len % (len - f[len-1] - 1) == 0) printf("%d\n",len - f[len-1] - 1);
        else printf("%d\n",len);
    }
}

(UVA) 10298 - Power Strings [string matching, KMP]

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

Tips : KMP + features XD

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

const int MAX_N = 1e6 + 6;

int fail[MAX_N];

void build(string b) {
    int len=b.size();
    int pos;
    pos = fail[0] = -1;
    for (int i=1;len > i;i++) {
        while (pos != -1 && b[pos + 1] != b[i]) {
            pos = fail[pos];
        }
        if (b[pos+1] == b[i]) pos++;
        fail[i] = pos;
    }
}

int match(string a,string b) {
    int lena=a.size(),lenb=b.size();
    int pos=-1;
    int cnt=0;
    for (int i=0;i<lena;i++) {
        while (pos != -1 && b[pos+1] != a[i]) {
            pos = fail[pos];
        }
        if (b[pos + 1] == a[i]) pos++;
        if (pos == lenb - 1) {
            cnt++;
            pos = fail[pos];
        }
    }
    return cnt;
}

int main () {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string s;
    while (getline(cin,s)) {
        //cout<<s<<"*\n";
        if (s==".") break;
        build(s);
        int k=s.size() - fail[s.size()-1] - 1;
        //for (int x=0;s.size()>x;x++) cout<<fail[x]<<' ';
        //cout<<endl;
        //cout<<"sz = "<<s.size()<<" , fail = "<<fail[s.size()-1]<<endl;
        if (s.size() % k ==0) printf("%d\n",s.size()/k);
        else puts("1");
    }
}

(Codeforces) 631D. Messenger [string matching, hashing]

http://codeforces.com/contest/631/problem/D

http://codeforces.com/contest/631/submission/22918964

從這題學到了一件事情：hash要認真寫！！！

一定要考慮到進制的問題，也要一直記得要mod！！！

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

#define int long long
typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 2e5 + 6;
const int MAX_P = 5;
const int MAX_M = 31;
const LL mod[MAX_P] = { 999727999, 996626699 , 1500450271,932474239,987848789 } ;

LL pow(LL a,LL n,LL mod) {
    //cout<<"a = "<<a<<" , n = "<<n<<endl;
 if (n==0) return 1;
 else if (n==1) return a;
 LL ret=pow(a,n/2,mod);
 ret *= ret;
 ret %= mod;
 if (n%2==1) ret *= a;
 return ret%mod;
}

LL ff(LL i) {
    return i*i-i+1;
}

LL f(LL c,LL t,int i,LL m) {
 return ((c*c*ff(c)+t)%mod[i])*pow(MAX_M,m,mod[i])%mod[i];
}

pii a[MAX_N];
LL pre[MAX_P][MAX_N];
pii q[MAX_N];

main () {
 int n,m;
 while (scanf("%I64d %I64d",&n,&m) != EOF) {
  int id=1;
  a[0]=make_pair(0,0);
  for (int x=1;n>=x;x++) {
   int l;
   char c;
   scanf("%I64d-%c",&l,&c);
   if (c==a[id-1].first) {
    a[id-1].second += l;
   }
   else {
    a[id++] = make_pair(c,l);
   }
  }
  int sz=0;
  for (int x=1;m>=x;x++) {
   int l;
   char c;
   scanf("%I64d-%c",&l,&c);
   if (sz == 0) {
    q[sz++] = make_pair(c,l);
   }
   else if (c==q[sz-1].first) {
    q[sz-1].second += l;
   }
   else {
    q[sz++] = make_pair(c,l);
   }
  }
  //cout<<"sz = "<<sz<<" , id = "<<id<<endl;
  if (sz == 1) {
   LL ans=0;
   for (int i=1;id>i;i++) {
    if (a[i].first==q[0].first&&a[i].second>=q[0].second) {
     ans += (a[i].second - q[0].second + 1);
    }
   }
   printf("%I64d\n",ans);
  }
  else {
            //build prefix
            for (int i=1;id>i;i++) {
                for (int j=0;MAX_P>j;j++) {
                    //if (!j) cout<<"hash["<<j<<"]["<<i<<"] = "<<LL(f(a[i].first,a[i].second,j,i) )<<endl;
                    pre[j][i] = pre[j][i-1] + f(a[i].first,a[i].second,j,i);
                    pre[j][i] %= mod[j];
                }
                //cout<<"i = "<<i<<" , pre = "<<pre[0][i]<<endl;
            }
            //get ans
            LL ans[MAX_P];
            for (int x=0;MAX_P>x;x++) {
                ans[x] = 0;
            }
            for (int i=1;sz-1>i;i++) {
                for (int j=0;MAX_P>j;j++) {
                    //if (!j) cout<<"hash[0]["<<i<<"] = "<<f(q[i].first,q[i].second,j,i)*31%mod[j]<<endl;
                    ans[j] += f(q[i].first,q[i].second,j,i);
                    ans[j] %= mod[j];
                }
            }
            LL cnt=0;
            //get all the segments
            //segment i-1 ~ i
            for (int i=2;id>i;i++) {
                if (i-1 + sz - 1 >= id) break;
                //okay range
                #define S second
                #define F first
                //cout<<"i = "<<i<<" , sz = "<<sz<<" ans = "<<ans<<" , pre = "<<pre[i+sz-3] - pre[i-1]<<endl;
                if (q[0].F==a[i-1].F&&q[0].S<=a[i-1].S&&q[sz-1].F==a[i+sz-2].F&&q[sz-1].S<=a[i+sz-2].S) {
                    bool check=true;
                    for (int j=0;MAX_P>j;j++) {
                        if ((pre[j][i+sz-3]-pre[j][i-1]+mod[j])%mod[j]!=(ans[j]*pow(MAX_M,i-1,mod[j]))%mod[j]) check=false;
                    }
                    /*if (!check) {
                        cout<<"i = "<<i<<endl;
                        cout<<"pre = "<<(pre[0][i+sz-3]-pre[0][i-1]+mod[0])%mod[0]<<endl;
                        cout<<"ans = "<<(ans[0]*pow(MAX_P,i-1,mod[0]))%mod[0]<<endl;
                    }*/
                    cnt += check;
                }
            }
            printf("%I64d\n",cnt);
  }
 }
}