POJ.2186 Popular Cows

1.Problem
2186 -- Popular Cows (poj.org)

2.Idea
SCC+Topological Sort

3.Source

 const int N = 100005;  
 //////////////////////////////  
 int V;  
 vector<int> G[N];  
 vector<int> rG[N];  
 vector<int> vs;  
 bool used[N];  
 int cmp[N];  
 void add_edge(int from, int to)  
 {  
      G[from].push_back(to);  
      rG[to].push_back(from);  
 }  
 void dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           if (!used[G[v][i]]) dfs(G[v][i]);  
      }  
      vs.push_back(v);  
 }  
 void rdfs(int v, int k)  
 {  
      used[v] = true;  
      cmp[v] = k;  
      for (int i = 0; i < rG[v].size(); i++) {  
           if (!used[rG[v][i]]) rdfs(rG[v][i], k);  
      }  
 }  
 int scc()  
 {  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) dfs(v);  
      }  
      memset(used, 0, sizeof used);  
      int k = 0;  
      for (int i = vs.size() - 1; i >= 0; i--) {  
           if (!used[vs[i]]) rdfs(vs[i], k++);  
      }  
      return k;  
 }  
 int n, m;  
 int a[N], b[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &m);  
      REP(i, m) scanf("%d%d", &a[i], &b[i]);  
      V = n;  
      for (int i = 0; i < m; i++) {  
           add_edge(a[i] - 1, b[i] - 1);  
      }  
      int nn = scc();  
      int u = 0, num = 0;  
      for (int v = 0; v < V; v++) {  
           if (cmp[v] == nn - 1) {  
                u = v;  
                num++;  
           }  
      }  
      memset(used, 0, sizeof(used));  
      rdfs(u, 0);  
      for (int v = 0; v < V; v++) {  
           if (!used[v]) {  
                num = 0;  
                break;  
           }  
      }  
      printf("%d\n", num);  
 }  

POJ.1741 Tree

1.Problem
1741 -- Tree (poj.org)

2.Idea
Centroid Decomposition of Tree

3.Source

 struct edge {   
      int to, length;   
      edge(int x, int y) { to = x; length = y; }  
 };  
 int n, k;  
 vector<edge> G[10004];  
 bool centroid[10004];  
 int subtree_size[10004];  
 int ans;  
 void init(int n) {  
      REP(i, n) G[i].clear();  
 }  
 void add_edge(int a, int b, int c) {  
      G[a].push_back(edge( b, c ));  
      G[b].push_back(edge( a, c ));  
 }  
 int compute_subtree(int v, int p)  
 {  
      int c = 1;  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           c += compute_subtree(G[v][i].to, v);  
      }  
      subtree_size[v] = c;  
      return c;  
 }  
 pair<int, int> search_centroid(int v, int p, int t)  
 {  
      pair<int, int> res = make_pair(INT_MAX, -1);  
      int s = 1, m = 0;  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           res = min(res, search_centroid(w, v, t));  
           m = max(m, subtree_size[w]);  
           s += subtree_size[w];  
      }  
      m = max(m, t - s);  
      res = min(res, make_pair(m, v));  
      return res;  
 }  
 void enumarate_paths(int v, int p, int d, vector<int> &ds)  
 {  
      ds.push_back(d);  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           enumarate_paths(w, v, d + G[v][i].length, ds);  
      }  
 }  
 int count_pairs(vector<int> &ds)  
 {  
      int res = 0;  
      sort(ds.begin(), ds.end());  
      int j = ds.size();  
      for (int i = 0; i < ds.size(); i++) {  
           while (j > 0 && ds[i] + ds[j - 1] > k) --j;  
           res += j - (j > i ? 1 : 0);  
      }  
      return res / 2;  
 }  
 void solve_subproblem(int v)  
 {  
      compute_subtree(v, -1);  
      int s = search_centroid(v, -1, subtree_size[v]).second;  
      centroid[s] = true;  
      for (int i = 0; i < G[s].size(); i++) {  
           if (centroid[G[s][i].to]) continue;  
           solve_subproblem(G[s][i].to);  
      }  
      vector<int> ds;  
      ds.push_back(0);  
      for (int i = 0; i < G[s].size(); i++) {  
           if (centroid[G[s][i].to]) continue;  
           vector<int> tds;  
           enumarate_paths(G[s][i].to, s, G[s][i].length, tds);  
           ans -= count_pairs(tds);  
           ds.insert(ds.end(), tds.begin(), tds.end());  
      }  
      ans += count_pairs(ds);  
      centroid[s] = false;  
 }  
 void solve()  
 {  
      while (scanf("%d %d", &n, &k), n) {  
           init(n);  
           REP(i, n - 1) {  
                int u, w, l;  
                scanf("%d %d %d", &u, &w, &l);  
                u--; w--;  
                add_edge(u, w, l);  
           }  
           ans = 0;  
           solve_subproblem(0);  
           printf("%d\n", ans);  
      }  
 }  

POJ.3260 The Fewest Coins

1.Problem
3260 -- The Fewest Coins (poj.org)

2.Idea
Knapsack problem. Reference

3.Source

 #include <cstdio>  
 #include <cstring>  
 const int maxn = 101, maxt = 10001, maxv = 121, INF = 0x3f3f3f3f;  
 int n, t, lim, v[maxn], c[maxn], que[maxt + maxv * maxv][2], l, r, f[maxt + maxv * maxv], g[maxv * maxv], ans;  
 int main()  
 {  
      scanf("%d%d", &n, &t);  
      for(int i = 0; i < n; ++i)  
      {  
           scanf("%d", v + i);  
           if(lim < v[i])  
                lim = v[i];  
      }  
      for(int i = 0; i < n; ++i)  
           scanf("%d", c + i);  
      lim *= lim;  
      t += lim;  
      memset(f, 0x3f, sizeof f);  
      memset(g, 0x3f, sizeof g);  
      f[0] = g[0] = 0;  
      for(int i = 0; i < n; ++i)  
           for(int a = 0; a < v[i]; ++a)  
           {  
                l = r = 0;  
                for(int j = 0; j * v[i] + a <= t; ++j)  
                {  
                     int tmp = f[j * v[i] + a] - j;  
                     while(l < r && que[r - 1][1] >= tmp)  
                          --r;  
                     que[r][0] = j;  
                     que[r++][1] = tmp;  
                     f[j * v[i] + a] = que[l][1] + j;  
                     if(que[l][0] == j - c[i])  
                          ++l;  
                }  
           }  
      for(int i = 0; i < n; ++i)  
           for(int j = v[i]; j <= lim; ++j)  
                if(g[j] > g[j - v[i]] + 1)  
                     g[j] = g[j - v[i]] + 1;  
      t -= lim;  
      ans = INF;  
      for(int i = 0; i <= lim; ++i)  
           if(ans > f[t + i] + g[i])  
                ans = f[t + i] + g[i];  
      if(ans != INF)  
           printf("%d\n", ans);  
      else  
           puts("-1");  
      return 0;  
 }  

POJ.2823 Sliding Window

1.Problem
2823 -- Sliding Window (poj.org)

2.Idea
Using Deque

3.Source

 const int N = 1000006;  
 //////////////////////////////  
 int n, k;  
 int a[N];  
 int mn[N], mx[N];  
 int deq[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &k);  
      REP(i, n) scanf("%d", &a[i]);  
      //MIN values  
      int s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] >= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mn[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mn[i], i == n - k ? '\n' : ' ');  
      }  
      //MAX Values  
      s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] <= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mx[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mx[i], i == n - k ? '\n' : ' ');  
      }  
 }  

POJ.3709 K-Anonymous Sequence

1.Problem
3709 -- K-Anonymous Sequence (poj.org)

2.Idea
Deque

3.Source

 int n, k;  
 Int a[N];  
 Int dp[N], S[N];  
 int deq[N];  
 Int f(int j, int x)  
 {  
      return -a[j] * x + dp[j] - S[j] + a[j] * j;  
 }  
 bool check(int f1, int f2, int f3)  
 {  
      Int a1 = -a[f1], b1 = dp[f1] - S[f1] + a[f1] * f1;  
      Int a2 = -a[f2], b2 = dp[f2] - S[f2] + a[f2] * f2;  
      Int a3 = -a[f3], b3 = dp[f3] - S[f3] + a[f3] * f3;  
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);  
 }  
 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           scanf("%d%d", &n, &k);  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &a[i]);  
           }  
           for (int i = 0; i < n; i++) {  
                S[i + 1] = S[i] + a[i];  
           }  
           int s = 0, t = 1;  
           deq[0] = 0;  
           dp[0] = 0;  
           for (int i = k; i <= n; i++) {  
                if (i - k >= k) {  
                     while (s + 1 < t && check(deq[t - 2], deq[t - 1], i - k)) t--;  
                     deq[t++] = i - k;  
                }  
                while (s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) s++;  
                dp[i] = S[i] + f(deq[s], i);  
           }  
           printf("%lld\n", dp[n]);  
      }  
 }  

POJ.2082 Terrible Sets

1.Problem
2082 -- Terrible Sets (poj.org)

2.Idea
Description is terrible but it was just simple max rectangle in histogram problem.

3.Source

 int n;  
 int h[N];  
 int st[N], L[N], R[N], sum[N];  
 int maxRec() {  
      //L   
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R   
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (sum[R[i]] - sum[L[i]]));  
      }  
      return res;  
 }  
 void solve()  
 {  
      while (cin >> n) {  
           if (n < 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &sum[i + 1], &h[i]);  
           }  
           for (int i = 0; i < n; i++)   
                sum[i + 1] += sum[i];  
           printf("%d\n", maxRec());  
      }  
 }  

POJ.3250 Bad Hair Day

1.Problem
3250 -- Bad Hair Day (poj.org)

2.Idea
Use monoton stack

3.Source

 int n;  
 Int h[80200];  
 void solve()  
 {       
      int n; cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &h[i]);  
      }  
      h[n] = MOD;  
      Int ans = 0;  
      stack<int> st;//monoton stack  
      for (int i = 0; i <= n; i++) {  
           if (st.empty() || h[st.top()] > h[i])  
                st.push(i);  
           else {  
                while (!st.empty() && h[st.top()] <= h[i]) {  
                     int tmp = st.top(); st.pop();  
                     ans += (Int)(i - tmp - 1);  
                }  
                st.push(i);  
           }  
      }  
      printf("%lld\n", ans);  
 }  

POJ.3494 Largest Submatrix of All 1’s

1.Problem
3494 -- Largest Submatrix of All 1’s (poj.org)

2.Idea
Apply the max rectangle in histogram problem.

3.Source

 int m, n;  
 int h[2200];  
 int st[2200], L[2200], R[2200];  
 int maxRec() {  
      //L  
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R  
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (R[i] - L[i]));  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (cin >> m >> n) {  
           memset(h, 0, sizeof h);  
           int ans = 0;  
           for (int i = 0; i < n; i++) {  
                for (int j = 0; j < m; j++) {  
                     int t; scanf("%d", &t);  
                     h[j] = t ? h[j] + 1 : 0;  
                }  
                ans = max(ans, maxRec());  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.2559 Largest Rectangle in a Histogram

1.Problem
2559 -- Largest Rectangle in a Histogram (poj.org)

2.Idea
Using stack

3.Source

 int n;  
 int h[N];  
 int L[N], R[N], st[N];  
 void solve()  
 {       
      while (scanf("%d", &n), n) {  
           REP(i, n) scanf("%d", &h[i]);  
           //L  
           int t = 0;  
           for (int i = 0; i < n; i++) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
                st[t++] = i;  
           }  
           //R  
           t = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                R[i] = (t == 0 ? n : st[t - 1]);  
                st[t++] = i;  
           }  
           long long res = 0;  
           for (int i = 0; i < n; i++) {  
                res = max(res, (long long)h[i] * (R[i] - L[i]));  
           }  
           printf("%lld\n", res);  
      }  
 }  

POJ.3729 Facer’s string

1.Problem
3729 -- Facer’s string (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3.Source Code

 const int MAXN = 50010;  
 int n, N, M, k, K;  
 int Rank[MAXN * 2];  
 int tmp[MAXN * 2];  
 int sa[MAXN * 2];  
 int lcp[MAXN * 2];  
 int s[MAXN * 2];  
 bool compare_sa(const int& i, const int& j) {  
      if (Rank[i] != Rank[j])return Rank[i] < Rank[j];  
      else {  
           int ri = i + k <= n ? Rank[i + k] : -1;  
           int rj = j + k <= n ? Rank[j + k] : -1;  
           return ri < rj;  
      }  
 }  
 void construct_sa(const int *S, int *sa) {  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp(const int *S, int *sa, int *lcp) {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)Rank[sa[i]] = i;  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)h--;  
           for (; j + h < n&&i + h < n; h++) {  
                if (S[j + h] != S[i + h])break;  
           }  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 long long calc(int K) {  
      int A = 0, B = 0;  
      long long res = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                if (B > 0)res += A;  
                A = 0; B = 0;  
           }  
           if (sa[i + 1] < N)A++;  
           if (sa[i + 1] > N) B++;  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (scanf("%d%d%d\n", &N, &M, &K) != EOF) {  
           for (int i = 0; i < N; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           s[N] = '$';  
           for (int i = N + 1; i < N + M + 1; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           n = N + M + 1;  
           s[n] = 0;  
           construct_sa(s, sa);  
           construct_lcp(s, sa, lcp);  
           printf("%lld\n", calc(K) - calc(K+1));  
      }  
 }  

POJ.3415 Common Substrings

1.Problem
3415 -- Common Substrings (poj.org)

2.Idea
Suffix Array
Monotonic Stack

3.Source

 const int MAX_L = 100000 + 1;  
 const int MAX_N = 2 * MAX_L + 1;  
 std::string S;  
 int n, k;  
 int sa[MAX_N + 1], lcp[MAX_N + 1];   
 int Rank[MAX_N + 1], tmp[MAX_N + 1];  
 bool compare_sa(const int i, const int j)  
 {  
      if (Rank[i] != Rank[j])  
      {  
           return Rank[i] < Rank[j];  
      }  
      return (i + k <= n ? Rank[i + k] : -1) < (j + k <= n ? Rank[j + k] : -1);  
 }  
 void construct_sa()  
 {  
      for (int i = 0; i <= n; i++)  
      {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k <<= 1)  
      {  
           std::sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++)  
           {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++)  
           {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp()  
 {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)  
      {  
           Rank[sa[i]] = i;  
      }  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++)  
      {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)  
           {  
                h--;  
           }  
           for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 int Stack[MAX_N][2];  
 long long contribution, top;  
 using namespace std;  
 long long calc(int K, int l1, bool is_s1)  
 {  
      long long ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                top = contribution = 0;  
           }  
           else {  
                int size = 0;  
                if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1)) {  
                     ++size;  
                     contribution += lcp[i] - K + 1;  
                }  
                while (top > 0 && lcp[i] <= Stack[top - 1][0]) {  
                     --top;  
                     contribution -= Stack[top][1] * (Stack[top][0] - lcp[i]);  
                     size += Stack[top][1];  
                }  
                if (size) {  
                     Stack[top][0] = lcp[i];  
                     Stack[top][1] = size;  
                     ++top;  
                }  
                if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) {  
                     ans += contribution;  
                }  
           }  
      }  
      return ans;  
 }  
 void solve()  
 {  
      int k;  
      while (scanf("%d", &k), k) {  
           string s1, s2;  
           cin >> s1 >> s2;  
           int l1 = s1.length();  
           int l2 = s2.length();  
           S = s1 + "$" + s2;  
           n = l1 + l2 + 1;  
           construct_sa();  
           construct_lcp();  
           printf("%lld\n", calc(k, l1, true) + calc(k, l1, false));  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 bool compare_sa(int i, int j) {  
      if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];  
      int ri = (i + k <= n) ? Rank[i + k] : -1;  
      int rj = (j + k <= n) ? Rank[j + k] : -1;  
      return ri < rj;  
 }  
 void createSA(const string& s, int* sa) {  
      n = s.size();  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? s[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) Rank[i] = tmp[i];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const string& s, int* sa) {  
           n = s.size();  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3581 Sequence

1.Problem
http://poj.org/problem?id=3581

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3690 Constellations

1.Problem
http://poj.org/problem?id=3690

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ. 3691 DNA repair

1.Problem
http://poj.org/problem?id=3691

2.Idea
Here

3.Source

 const int MAXK = 1000;  
 const int MAXLEN = 1010;  
 const string AGCT = "AGCT";  
 int nextState[MAXK][4];  
 bool ng[MAXK];  
 int dp[MAXLEN][MAXK];  
 int solve(const vector<string>& ngWords, const string& init) {  
      vector<string> pfx;  
      int n = ngWords.size();  
      // 状態の列挙  
      for (int i = 0; i < n; i++) {  
           string s = ngWords[i];  
           for (int j = 0; j <= (int)s.size(); j++) {  
                pfx.push_back(s.substr(0, j));  
           }  
      }  
      sort(pfx.begin(), pfx.end());  
      pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());  
      int K = pfx.size();  
      // 状態の遷移  
      for (int i = 0; i < K; i++) {  
           for (int j = 0; j < 4; j++) {  
                string s = pfx[i] + AGCT.substr(j, 1);  
                while (1) {  
                     int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();  
                     if (nk < K && pfx[nk] == s) {  
                          nextState[i][j] = nk;  
                          break;  
                     }  
                     s = s.substr(1);  
                }  
           }  
      }  
      // 状態がngかどうか  
      for (int i = 0; i < K; i++) {  
           ng[i] = false;  
           int sl = pfx[i].size();  
           for (int j = 0; j < n; j++) {  
                int wl = ngWords[j].size();  
                if (sl < wl) continue;  
                if (pfx[i].substr(sl - wl) == ngWords[j]) {  
                     ng[i] = true;  
                     break;  
                }  
           }  
      }  
      // dp  
      int length = init.size();  
      for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) {  
           dp[i][k] = INF;  
      }  
      dp[0][0] = 0;  
      for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) {  
           if (dp[l][k] == INF) continue;  
           if (ng[k]) continue;  
           for (int j = 0; j < 4; j++) {  
                int plus = (init[l] == AGCT[j]) ? 0 : 1;  
                int ns = nextState[k][j];  
                if (ng[ns]) continue;  
                dp[l + 1][ns] = min(dp[l][k] + plus, dp[l + 1][ns]);  
           }  
      }  
      int ans = INF;  
      for (int k = 0; k < K; k++) {  
           if (ng[k]) continue;  
           ans = min(ans, dp[length][k]);  
      }  
      if (ans == INF) ans = -1;  
      return ans;  
 }  
 int main() {  
      cin.tie(0);  
      ios::sync_with_stdio(false);  
      int T = 0;  
      int n;  
      while (cin >> n) {  
           if (n == 0) break;  
           T++;  
           vector<string> ngWords;  
           for (int i = 0; i < n; i++) {  
                string s;  
                cin >> s;  
                ngWords.push_back(s);  
           }  
           string init;  
           cin >> init;  
           printf("Case %d: %d\n", T, solve(ngWords, init));  
      }  
      return 0;  
 }  

POJ.3537 Crosses and Crosses

1.Problem
http://poj.org/problem?id=3537

2.Idea
Calc grundy

3.Source

 int dp[2001];  
 int grundy(int n) {  
      if (n <= 0) return 0;  
      if (~dp[n]) return dp[n];  
      vector<int> vis(1 << 11);  
      for (int i = 1; i <= n; ++i) {  
           vis[grundy(i - 1 - 2) ^ grundy(n - i - 2)] = 1;  
      }  
      for (int i = 0; ; ++i) {  
           if (!vis[i]) return dp[n] = i;  
      }  
 }  
 void solve()  
 {  
      std::memset(dp, 0xff, sizeof(dp));  
      int n;  
      cin >> n;  
      cout << (grundy(n) ? 1 : 2) << endl;  
 }  

POJ.2975 Nim

1.Problem
http://poj.org/problem?id=2975

2.Idea
Calculate Nim.

3.Source

 int n;  
 int a[1100];  
 void solve()  
 {  
      while (scanf("%d", &n)) {  
           if (n == 0) break;  
           int x = 0;  
           REP(i, n) {  
                scanf("%d", &a[i]);  
                x ^= a[i];  
           }  
           int ans = 0;  
           if (x > 0) {  
                REP(i, n) {  
                     int tmp = x ^ a[i];  
                     if (tmp <= a[i]) ans++;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.1704 Georgia and Bob

 1.Problem
http://poj.org/problem?id=1704

2.Idea
Using Nim

3.Source

 int n;  
 int p[N];  
 void solve()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> n;  
           REP(i, n) cin >> p[i];  
           if (n % 2) p[n++] = 0;  
           sort(p, p + n);  
           int x = 0;  
           for (int i = 0; i + 1 < n; i += 2) {  
                x ^= (p[i + 1] - p[i] - 1);  
           }  
           if (x == 0) cout << "Bob will win" << endl;  
           else cout << "Georgia will win" << endl;  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2311 Cutting Game

 1.Problem

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

2.Idea

Using Grundy number

3.Source

 int W, H;  
 int mem[220][220];  
 int grundy(int w, int h)  
 {  
      if (mem[w][h] != -1) return mem[w][h];  
      set<int> s;  
      for (int i = 2; w - i >= 2; i++) {  
           s.insert(grundy(i, h) ^ grundy(w - i, h));  
      }  
      for (int i = 2; h - i >= 2; i++) {  
           s.insert(grundy(w, i) ^ grundy(w, h - i));  
      }  
      int res = 0;  
      while (s.count(res)) res++;  
      return mem[w][h] = res;  
 }  
 void solve()  
 {  
      memset(mem, -1, sizeof mem);  
      while (scanf("%i%i", &W, &H) > 0) {  
           if (grundy(W, H) != 0) puts("WIN");  
           else puts("LOSE");  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }