POJ.2135 Farm Tour

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

2.Idea
Min cost flow

3.Source

 #define MAX_V 1005  
 #define INF 1000000000  
 struct edge{ int to, cap, cost, rev_index; };  
 int V;  
 vector<edge> G[MAX_V];  
 int dist[MAX_V];  
 int prevv[MAX_V], preve[MAX_V];  
 void add_edge(int from, int to, int cap, int cost){  
  G[from].push_back((edge){to, cap, cost, G[to].size()});  
  G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});  
 }  
 int min_cost_flow(int s, int t, int f){  
  int res = 0;  
  while(f > 0){  
   fill(dist, dist + V, INF);  
   dist[s] = 0;  
   bool update = true;  
   while(update){  
    update = false;  
    for(int v = 0; v < V; v++){  
     if(dist[v] == INF) continue;  
     for(int i = 0; i < G[v].size(); i++){  
      edge &e = G[v][i];  
      if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){  
       dist[e.to] = dist[v] + e.cost;  
       prevv[e.to] = v;  
       preve[e.to] = i;  
       update = true;  
      }  
     }  
    }  
   }  
   if(dist[t] == INF){  
    return -1;  
   }  
   int d = f;  
   for(int v = t; v != s; v = prevv[v]){  
    d = min(d, G[prevv[v]][preve[v]].cap);  
   }  
   f -= d;  
   res += d * dist[t];  
   for(int v = t; v != s; v = prevv[v]){  
    edge &e = G[prevv[v]][preve[v]];  
    e.cap -= d;  
    G[v][e.rev_index].cap += d;  
   }  
  }  
  return res;  
 }  
 int main(){  
  int N, M;  
  scanf("%d %d", &N, &M);  
  V = N;  
  while(M--){  
   int a, b, c;  
   scanf("%d %d %d", &a, &b, &c);  
   add_edge(a - 1, b - 1, 1, c);  
   add_edge(b - 1, a - 1, 1, c);  
  }  
  printf("%d\n", min_cost_flow(0, N - 1, 2));  
 }  

POJ.3469 Dual Core CPU

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

2.Idea
Max Flow

3.Source

 #define MAX_V 20004  
 struct edge { int to, cap, rev; };  
 vector<edge> G[MAX_V];  
 int level[MAX_V];  
 int iter[MAX_V];  
 #define MAX_N 20004  
 #define MAX_M 200005  
 int N, M;  
 int A[MAX_N], B[MAX_N];  
 int a[MAX_M], b[MAX_M], w[MAX_M];  
 void add_edge(int from, int to, int cap)  
 {  
      edge e1, e2;  
      e1.to = to;  
      e1.cap = cap;  
      e1.rev = G[to].size();  
      G[from].push_back(e1);  
      e2.to = from;  
      e2.cap = 0;  
      e2.rev = G[from].size() - 1;  
      G[to].push_back(e2);  
 }  
 void bfs(int s)  
 {  
      memset(level, -1, sizeof level);  
      queue<int> que;  
      level[s] = 0;  
      que.push(s);  
      while (!que.empty()) {  
           int v = que.front(); que.pop();  
           for (int i = 0; i < G[v].size(); i++) {  
                edge &e = G[v][i];  
                if (e.cap > 0 && level[e.to] < 0) {  
                     level[e.to] = level[v] + 1;  
                     que.push(e.to);  
                }  
           }  
      }  
 }  
 int dfs(int v, int t, int f)   
 {  
      if (v == t) return f;  
      for (int &i = iter[v]; i < G[v].size(); i++) {  
           edge &e = G[v][i];  
           if (e.cap > 0 && level[v] < level[e.to]) {  
                int d = dfs(e.to, t, min(f, e.cap));  
                if (d > 0) {  
                     e.cap -= d;  
                     G[e.to][e.rev].cap += d;  
                     return d;  
                }  
           }  
      }  
      return 0;  
 }  
 //Dinic  
 int max_flow(int s, int t)  
 {  
      int flow = 0;  
      for (;;) {  
           bfs(s);  
           if (level[t] < 0) return flow;  
           memset(iter, 0, sizeof iter);  
           int f;  
           while ((f = dfs(s, t, INF)) > 0) {  
                flow += f;  
           }  
      }  
 }  
 void solve()  
 {  
      int s = N, t = s + 1;  
      for (int i = 0; i < N; i++) {  
           add_edge(i, t, A[i]);  
           add_edge(s, i, B[i]);  
      }  
      for (int i = 0; i < M; i++) {  
           add_edge(a[i] - 1, b[i] - 1, w[i]);  
           add_edge(b[i] - 1, a[i] - 1, w[i]);  
      }  
      printf("%d\n", max_flow(s, t));  
 }  
 int main() {  
      scanf("%d%d", &N, &M);  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d", &A[i], &B[i]);  
      }  
      for (int i = 0; i < M; i++) {  
           scanf("%d%d%d", &a[i], &b[i], &w[i]);  
      }  
      solve();  
      return 0;  
 }  

POJ.3291 Dining

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

2.Idea
Max Flow

3.Source

 #define MAX_V 500  
 int N, F, D;  
 struct edge { int to, cap, rev; };  
 vector<edge> G[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int from, int to, int cap)  
 {  
      edge e1, e2;  
      e1.to = to;  
      e1.cap = cap;  
      e1.rev = G[to].size();  
      G[from].push_back(e1);  
      e2.to = from;  
      e2.cap = 0;  
      e2.rev = G[from].size() - 1;  
      G[to].push_back(e2);  
 }  
 int dfs(int v, int t, int f)   
 {  
      if (v == t) return f;  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           edge &e = G[v][i];  
           if (!used[e.to] && e.cap > 0) {  
                int d = dfs(e.to, t, min(f, e.cap));  
                if (d > 0) {  
                     e.cap -= d;  
                     G[e.to][e.rev].cap += d;  
                     return d;  
                }  
           }  
      }  
      return 0;  
 }

//Ford-Fulkersen  
 int max_flow(int s, int t)  
 {  
      int flow = 0;  
      for (;;) {  
           memset(used, 0, sizeof used);  
           int f = dfs(s, t, INF);  
           if (f == 0) {  
                return flow;  
           }  
           flow += f;  
      }  
 }  
 int main() {  
      int N, F, D;  
      scanf("%d %d %d", &N, &F, &D);  
      for (int i = 0; i < F; i++) {  
           add_edge(0, 1 + i, 1);  
      }  
      for (int i = 0; i < N; i++) {  
           int Fi, Di;  
           scanf("%d %d", &Fi, &Di);  
           while (Fi--) {  
                int f;  
                scanf("%d", &f);  
                add_edge(1 + (f - 1), 1 + F + i, 1);  
           }  
           add_edge(1 + F + i, 1 + F + N + i, 1);  
           while (Di--) {  
                int d;  
                scanf("%d", &d);  
                add_edge(1 + F + N + i, 1 + F + N + N + (d - 1), 1);  
           }  
      }  
      for (int i = 0; i < D; i++) {  
           add_edge(1 + F + N + N + i, 1 + F + N + N + D, 1);  
      }  
      printf("%d\n", max_flow(0, 1 + F + N + N + D));  
 }  

POJ.1486 Sorting Slides

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N;  
 struct Rec {  
      int xmin, xmax, ymin, ymax;  
 } Recs[50004];  
 struct Point {  
      int x, y;  
 } Points[50004];  
 bool itIncludes(int i, int j)  
 {  
      if (  Recs[i].xmin < Points[j].x && Recs[i].xmax > Points[j].x  
           && Recs[i].ymin < Points[j].y && Recs[i].ymax > Points[j].y)   
           return true;  
      else   
           return false;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int i = 0; i < N; i++) {  
           bool update = false;  
           for (int v = 0; v < V; v++) {  
                if (!used[v] && match[v] < 0) {  
                     int cnt = 0;  
                     int u = -1;  
                     for (int j = 0; j < G[v].size(); j++) {  
                          int f = G[v][j];  
                          if (!used[f]) {  
                               u = f;  
                               cnt++;  
                          }  
                     }  
                     if (cnt == 1) {  
                          update = true;  
                          match[v] = u;  
                          match[u] = v;  
                          used[v] = true;  
                          used[u] = true;  
                          res++;  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d%d%d", &Recs[i].xmin, &Recs[i].xmax, &Recs[i].ymin, &Recs[i].ymax);  
      }  
      for (int i = 0; i < N; i++) {  
           scanf("%d%d", &Points[i].x, &Points[i].y);  
      }  
      V = 2 * N;  
      for (int i = 0; i < N; i++)  
           for (int j = 0; j < N; j++) {  
                if (itIncludes(i, j)) {  
                     add_edge(i, N + j);  
                }  
           }  
      if (bipartite_matching() > 0) {  
           for (int i = 0; i < N; i++) {  
                if (match[i] > 0) {  
                     printf("(%c,%d) ", 'A' + i, match[i] - N + 1);  
                }  
           }  
           printf("\n");  
      }  
      else {  
           printf("none\n");  
      }  
 }  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d", &N)>0) {  
           if (N == 0) break;  
           printf("Heap %d\n", t);  
           solve();  
           printf("\n");  
           t++;  
      }  
      return 0;  
 }  

POJ.2724 Purifying Machine

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 2222  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 int N, M;  
 vector<string> vs;  
 bool isConnected(int i, int j)  
 {  
      int cnt = 0;  
      for (int k = 0; k < N; k++) {  
           if (vs[i][k] != vs[j][k]) cnt++;  
      }  
      return cnt == 1;  
 }  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      vs.clear();  
      for (int i = 0; i < M; i++) {  
           string s, t;  
           cin >> s;  
           t = s;  
           int j = 0;  
           for (j = 0; j < N; j++) {  
                if (s[j] == '*') break;  
           }  
           if (j < N) {  
                s[j] = '1';  
                t[j] = '0';  
                vs.push_back(s);  
                vs.push_back(t);  
           }  
           else {  
                vs.push_back(s);  
           }  
      }  
      sort(vs.begin(), vs.end());  
      vs.erase(unique(vs.begin(), vs.end()), vs.end());  
      V = vs.size();  
      for (int i = 0; i < V; i++)  
           for (int j = i + 1; j < V; j++) {  
                if (isConnected(i, j)) {  
                     add_edge(i, j);  
                }  
           }  
      printf("%d\n", V - bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &M)>0) {  
           if (N + M == 0) break;  
           solve();  
      }  
      return 0;  
 }  

CodeForces.1326D2 Prefix-Suffix Palindrome (Hard version)

1.Problem
https://codeforces.com/contest/1326/problem/D2

2.Idea
KMP algorithm

3.Source

 string s;  
 int n;  
 //kmp algorithm: returns len of the longest pre==suf   
 int longest_palindrome_prefix(const string s)  
 {  
      string kmprev = s;  
      reverse(kmprev.begin(), kmprev.end());  
      string kmp = s + "#" + kmprev;  
      vector<int> lps(kmp.size(), 0);  
      for (int i = 1; i < (int)lps.size(); ++i)  
      {  
           int prev_idx = lps[i - 1];  
           while (prev_idx > 0 && kmp[i] != kmp[prev_idx])  
           {  
                prev_idx = lps[prev_idx - 1];  
           }  
           lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);  
      }  
      return lps[lps.size() - 1];  
 }  
 int32_t main()  
 {  
      int t;  
      cin >> t;  
      while(t--)  
      {  
           cin >> s;  
           n = s.length();  
           int ln = 0;  
           for (int i = 0, j = n - 1; i < j; ++i, --j)  
                if (s[i] == s[j])  
                     ln++;  
                else  
                     break;  
           int rem = n - 2 * ln;  
           string ans;  
           if (ln)     ans = s.substr(0, ln);  
           if (rem > 0)  
           {  
                string st = s.substr(ln, rem);  
                int pre = longest_palindrome_prefix(st);  
                reverse(st.begin(), st.end());  
                int suf = longest_palindrome_prefix(st);  
                if (pre > suf) {  
                     reverse(st.begin(), st.end());  
                     ans += st.substr(0, pre);  
                }  
                else {  
                     ans += st.substr(0, suf);  
                }  
           }  
           if (ln) ans += s.substr(n - ln, ln);  
           std::cout << ans << '\n';  
      }  
      return 0;  
 }  

POJ.3692 Kindergarten

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

2.Idea
Reverse the graph and take Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 bool g[500][500];  
 int GV, B, M;  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve(int t)  
 {  
      V = GV + B;  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < 500; i++)  
           for (int j = 0; j < 500; j++)  
                g[i][j] = 1;  
      for (int i = 0; i < M; i++) {  
           int k, t;  
           scanf("%d%d", &t, &k);  
           t = t - 1;  
           k = GV + k - 1;  
           g[t][k] = g[k][t] = 0;  
      }  
      for (int i = 0; i < GV; i++) {  
           for (int j = GV; j < V; j++) {  
                if (g[i][j]) add_edge(i, j);  
           }  
      }  
      printf("Case %d: %d\n", t, GV + B - bipartite_matching());  
 }  
 int main()  
 {  
      int t = 1;  
      while (scanf("%d%d%d", &GV, &B, &M)>0) {  
           if (GV == 0) break;  
           solve(t);  
           t++;  
      }  
      return 0;  
 }  

POJ.1466 Girls and Boys

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < V; i++) {  
           int k, t;  
           scanf("%d: (%d)", &t, &k);  
           for (int j = 0; j < k; j++) {  
                scanf("%d", &t);  
                add_edge(i, t);  
           }  
      }  
      printf("%d\n", V - bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d", &V)>0) {  
           if (V == 0) break;  
           solve();  
      }  
      return 0;  
 }  

POJ.1274 The Perfect Stall

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V, N, M;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      V = N * 2;  
      for (int i = 0; i <= V; i++) G[i].clear();  
      memset(used, 0, sizeof used);  
      for (int i = 0; i < N; i++) {  
           int k, t;  
           scanf("%d", &k);  
           for (int j = 0; j < k; j++) {  
                scanf("%d", &t);  
                add_edge(i, N + t - 1);  
           }  
      }  
      printf("%d\n", bipartite_matching());  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &M)>0) {  
           solve();  
      }  
      return 0;  
 }  

POJ.3057 Evacuation

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

2.Idea
Bipartite Matching

3.Source

 struct P { int x, y; };  
 int dx[] = {0, 1, 0, -1};  
 int dy[] = {1, 0, -1, 0};  
 int X, Y;  
 char field[MAX_X][MAX_Y];  
 int dist[MAX_X][MAX_Y][MAX_X][MAX_Y];  
 vector<P> ds, ps;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v){  
  G[u].push_back(v);  
  G[v].push_back(u);  
 }  
 bool dfs(int v){  
  used[v] = true;  
  for(int i = 0; i < G[v].size(); i++){  
   int u = G[v][i];  
   int u_pair = match[u];  
   if(u_pair < 0 || !used[u_pair] && dfs(u_pair)){  
    match[v] = u;  
    match[u] = v;  
    return true;  
   }  
  }  
  return false;  
 }  
 void bfs(P door, int d[MAX_X][MAX_Y]){  
  queue<P> q;  
  d[door.x][door.y] = 0;  
  q.push(door);  
  while(!q.empty()){  
   P p = q.front(); q.pop();  
   for(int i = 0; i < 4; i++){  
    int nx = p.x + dx[i], ny = p.y + dy[i];  
    if(field[nx][ny] == '.' && d[nx][ny] < 0){  
     d[nx][ny] = d[p.x][p.y] + 1;  
     q.push((P){nx, ny});  
    }  
   }  
  }  
 }  
 void solve(){  
  int max_t = X * Y;  
  ds.clear(); ps.clear();  
  memset(dist, -1, sizeof(dist));  
  for(int i = 0; i < MAX_V; i++){  
   G[i].clear();  
  }  
  for(int x = 0; x < MAX_X; x++){  
   for(int y = 0; y < MAX_Y; y++){  
    if(field[x][y] == 'D'){  
     ds.push_back((P){x, y});  
     bfs((P){x, y}, dist[x][y]);  
    }else if(field[x][y] == '.'){  
     ps.push_back((P){x, y});  
    }  
   }  
  }  
  for(int i = 0; i < ds.size(); i++){  
   for(int j = 0; j < ps.size(); j++){  
    P d = ds[i], p = ps[j];  
    if(dist[d.x][d.y][p.x][p.y] >= 0){  
     for(int t = dist[d.x][d.y][p.x][p.y]; t <= max_t; t++){  
      add_edge((t - 1) * ds.size() + i, max_t * ds.size() + j);  
     }  
    }  
   }  
  }  
  if(ps.size() == 0){  
   printf("0\n");  
   return;  
  }  
  int num = 0;  
  memset(match, -1, sizeof(match));  
  for(int v = 0; v < max_t * ds.size(); v++){  
   memset(used, 0, sizeof(used));  
   if(dfs(v)){  
    if(++num == ps.size()){  
     printf("%d\n", v / ds.size() + 1);  
     return;  
    }  
   }  
  }  
  printf("impossible\n");  
 }  
 int main(){  
  int C;  
  scanf("%d", &C);  
  while(C--){  
   scanf("%d %d", &X, &Y);  
   memset(field, 'X', sizeof(field));  
   for(int i = 1; i <= X; i++){  
    scanf("%s", &field[i][1]);  
   }  
   solve();  
  }  
 }  

POJ.3041 Asteroids

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

2.Idea
Bipartite Matching

3.Source

 #define MAX_V 1000  
 int V;  
 vector<int> G[MAX_V];  
 int match[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int u, int v)  
 {  
      G[u].push_back(v);  
      G[v].push_back(u);  
 }  
 bool dfs(int v)  
 {  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           int u = G[v][i], w = match[u];  
           if (w < 0 || !used[w] && dfs(w)) {  
                match[v] = u;  
                match[u] = v;  
                return true;  
           }  
      }  
      return false;  
 }  
 int bipartite_matching()  
 {  
      int res = 0;  
      memset(match, -1, sizeof match);  
      for (int v = 0; v < V; v++) {  
           if (match[v] < 0) {  
                memset(used, 0, sizeof used);  
                if (dfs(v)) {  
                     res++;  
                }  
           }  
      }  
      return res;  
 }  
 #define MAX_K 10000  
 int N, K;  
 int R[MAX_K], C[MAX_K];  
 void solve()  
 {  
      V = N * 2;  
      for (int i = 0; i < K; i++) {  
           add_edge(R[i] - 1, N + C[i] - 1);  
      }  
      printf("%d\n", bipartite_matching());  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &K);  
      for (int i = 0; i < K; i++) {  
           scanf("%d%d", &R[i], &C[i]);  
      }  
      solve();  
      return 0;  
 }  

POJ.1795 DNA Laboratory

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

2.Idea and Source:
https://blog.csdn.net/GYH0730/article/details/90344515

POJ.3411 Paid Roads

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

2.Idea
bit DP + Bellman-Ford

3.Source

 #define MAX_N 10  
 #define MAX_M 10  
 struct Edge {  
      int a, b, c, p, r;  
 } Edges[MAX_M];  
 int dp[1 << MAX_N][MAX_N];  
 int n, m;  
 int main()  
 {  
      cin >> n >> m;  
      for (int i = 0; i < m; i++) {  
           cin >> Edges[i].a >> Edges[i].b >> Edges[i].c >> Edges[i].p >> Edges[i].r;  
           Edges[i].a--;  
           Edges[i].b--;  
           Edges[i].c--;  
      }  
      for (int i = 0; i < 1 << MAX_N; i++) {  
           fill(dp[i], dp[i] + MAX_N, INF);  
      }  
      dp[1][0] = 0;  
      bool update;  
      while (1) {  
           update = false;  
           for (int _ = 0; _ < n; _++) {  
                for (int i = 0; i < m; i++) {  
                     int a = Edges[i].a, b = Edges[i].b, c = Edges[i].c, p = Edges[i].p, r = Edges[i].r;  
                     for (int S = 0; S < 1 << n; S++) {  
                          if ((S & (1 << a)) && dp[S][a] < INF) {  
                               if (dp[S | (1 << b)][b] > dp[S][a] + r) {  
                                    update = true;  
                                    dp[S | (1 << b)][b] = dp[S][a] + r;  
                               }  
                               if ((S & (1 << c))) {  
                                    if (dp[S | (1 << b)][b] > dp[S][a] + p) {  
                                         update = true;  
                                         dp[S | (1 << b)][b] = dp[S][a] + p;  
                                    }  
                               }  
                          }  
                     }  
                }  
           }  
           if (!update) break;  
      }  
      int ans = INF;  
      for (int S = 0; S < 1 << n; S++) {  
           ans = min(ans, dp[S][n - 1]);  
      }  
      if (ans == INF) {  
           cout << "impossible" << endl;  
      }  
      else {  
           cout << ans << endl;  
      }  
      return 0;  
 }  

5367. Longest Happy Prefix

1.Problem
https://leetcode.com/contest/weekly-contest-181/problems/longest-happy-prefix/

2.Idea
Rolling_Hash

3.Source

 // ローリングハッシュ  
  struct RollingHash {  
      static const int base1 = 1007, base2 = 2009;  
      static const int mod1 = 1000000007, mod2 = 1000000009;  
      vector<long long> hash1, hash2, power1, power2;  
      // construct  
      RollingHash(const string &S) {  
           int n = (int)S.size();  
           hash1.assign(n + 1, 0);  
           hash2.assign(n + 1, 0);  
           power1.assign(n + 1, 1);  
           power2.assign(n + 1, 1);  
           for (int i = 0; i < n; ++i) {  
                hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1;  
                hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2;  
                power1[i + 1] = (power1[i] * base1) % mod1;  
                power2[i + 1] = (power2[i] * base2) % mod2;  
           }  
      }  
      // get hash of S[left:right) 
      inline pair<long long, long long> get(int l, int r) const {  
           long long res1 = hash1[r] - hash1[l] * power1[r - l] % mod1;  
           if (res1 < 0) res1 += mod1;  
           long long res2 = hash2[r] - hash2[l] * power2[r - l] % mod2;  
           if (res2 < 0) res2 += mod2;  
           return { res1, res2 };  
      }  
 };  
 class Solution {  
 public:  
      string longestPrefix(string s) {  
           // ロリハ  
           RollingHash rh(s);  
           // 求める  
           int N = s.size();  
           for (int i = 1; i < N; ++i) {  
                if (rh.get(i, N) == rh.get(0, N - i)) {  
         cout << i << endl;  
                     //get substr [i,j)
                     return s.substr(0, N - i);  
                }  
           }  
           return "";  
      }  
 };  

POJ.2441 Arrange the Bulls

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

2.Idea
bit DP

3.Source

 int N, M;  
 int cows[22][22];  
 int dp[1 << 20 + 1];  
 int solve(int i, int S)  
 {  
      if (dp[S] != -1) return dp[S];  
      if (i == N) return 1;  
      int res = 0;  
      for (int k = 0; k < M; k++) {  
           if (cows[i][k] && !((1 << k) & S)) {  
                res += solve(i + 1, S | (1 << k));  
           }  
      }  
      return dp[S] = res;  
 }  
 int main()  
 {  
      memset(dp, -1, sizeof dp);  
      cin >> N >> M;  
      for (int i = 0; i < N; i++) {  
           int p;  
           cin >> p;  
           for (int j = 0; j < p; j++) {  
                int t;  
                cin >> t;  
                cows[i][t - 1] = 1;  
           }  
      }  
      cout << solve(0, 0) << endl; // i-th cow, current mask  
      return 0;  
 }  

POJ.2836 Rectangular Covering

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

2.Idea
bit DP

3.Source

 struct Rect {  
      int x, y;  
      int w, h;  
      int mask;  
      bool contain(int qx, int qy) {  
           if (qx < x || qx > x + w) return false;  
           if (qy < y || qy > y + h) return false;  
           return true;  
      }  
      int area() const {  
           return w * h;  
      }  
 };  
 #define MAX_N 15  
 const int INF = 0x3f3f3f3f;  
 int x[MAX_N], y[MAX_N];  
 vector<Rect> rects;  
 int n;  
 int dp[1 << MAX_N];  
 void makeRect(int i, int j)  
 {  
      Rect rec;  
      rec.x = min(x[i], x[j]);  
      rec.y = min(y[i], y[j]);  
      rec.w = max(1, max(x[i], x[j]) - rec.x);  
      rec.h = max(1, max(y[i], y[j]) - rec.y);  
      rec.mask = 0;  
      for (int i = 0; i < n; i++) {  
           if (rec.contain(x[i], y[i])) {  
                rec.mask |= (1 << i);  
           }  
      }  
      rects.push_back(rec);  
 }  
 int main()  
 {  
      while (cin >> n) {  
           if (n == 0) break;  
           memset(dp, INF, sizeof(dp));  
           rects.clear();  
           for (int i = 0; i < n; i++) {  
                cin >> x[i] >> y[i];  
           }  
           for (int i = 0; i < n; i++) {  
                for (int j = i + 1; j < n; j++) {  
                     makeRect(i, j);  
                }  
           }  
           fill(dp, dp + MAX_N, INF);  
           dp[0] = 0;  
           for (int S = 0; S < (1 << n); S++) {  
                if (dp[S] != INF) {  
                     for (int k = 0; k < rects.size(); k++) {  
                          if (S != (S | rects[k].mask)) {  
                               dp[S | rects[k].mask] = min(dp[S | rects[k].mask], dp[S] + rects[k].area());  
                          }  
                     }  
                }  
           }  
           printf("%d\n", dp[(1 << n) - 1]);  
      }  
      return 0;  
 }  

POJ.3254 Corn Fields

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

2.Idea
bit DP

3.Source

 int field[13] = { 0 };  
 int dp[13][4096];  
 int R, C, C2;  
 vector<int> seq;  
 void solve()  
 {  
      for (int i = 0; i < R; i++)  
           for (int j = 0; j < C; j++) {  
                int tmp;  
                cin >> tmp;  
                if (!tmp) field[i + 1] |= 1 << j;  
           }  
      for (int i = 0; i < C2; i++) {  
           if (!(i & (i << 1))) seq.push_back(i);  
      }  
      fill(dp[0], dp[0] + C2, 1);  
      for (int i = 1; i <= R; i++) {  
           fill(dp[i], dp[i] + C2, 0);  
           for (int j = 0; j < C2; j++) {  
                if (~j & field[i]) continue;  
                for (int k = 0; k < seq.size(); k++) {  
                     int u = seq[k];  
                     if (u & j) continue;  
                     dp[i][j] += dp[i - 1][u | field[i - 1]];  
                     dp[i][j] %= 100000000;  
                }  
           }  
      }  
      cout << dp[R][field[R]] << endl;  
 }  
 int main()  
 {  
      cin >> R >> C;  
      C2 = 1 << C;  
      solve();  
      return 0;  
 }  

POJ.3171 Cleaning Shifts

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

2.Idea
dp + seg tree

3.Source

 const int MAX_N = 10004;  
 const int MAX_M = 86399;  
 const ll INF = 1e18;  
 template<class T>  
 struct SegTree {  
      int NN;  
      vector<T> seg;  
      T def; // default vale  
      T func(T a, T b) {  
           return min(a, b);  
      }  
      void gather(int u) {  
           seg[u] = func(seg[u * 2 + 1], seg[u * 2 + 2]);  
      }  
      void init(int N, T d) {  
           def = d;  
           NN = 1;  
           while (NN < N)  
                NN *= 2;  
           seg = vector<T>(2 * NN - 1, def);  
           // for (int i = 0; i < N; i++) {  
           //   seg[NN - 1 + i] = inp[i];  
           // }  
           build(0);  
      }  
      void build(int u) {  
           if (u >= NN - 1) { // leaf  
                return;  
           }  
           build(u * 2 + 1);  
           build(u * 2 + 2);  
           gather(u);  
      }  
      void _update(int idx, T val, int u, int l, int r) {  
           if (l > idx || r <= idx) {  
                return;  
           }  
           if (l == idx && idx + 1 == r) {  
                seg[u] = val;  
                return;  
           }  
           int m = (l + r) / 2;  
           _update(idx, val, u * 2 + 1, l, m);  
           _update(idx, val, u * 2 + 2, m, r);  
           gather(u);  
      }  
      T _query(int a, int b, int u, int l, int r) {  
           if (l >= b || r <= a) {  
                return def;  
           }  
           if (a <= l && r <= b) {  
                return seg[u];  
           }  
           int m = (l + r) / 2;  
           T res1 = _query(a, b, u * 2 + 1, l, m);  
           T res2 = _query(a, b, u * 2 + 2, m, r);  
           return func(res1, res2);  
      }  
      void update(int idx, T val) {  
           _update(idx, val, 0, 0, NN);  
      }  
      T query(int a, int b) {  
           return _query(a, b, 0, 0, NN);  
      }  
 };  
 int N, M, E;  
 ll dp[MAX_M + 1];  
 SegTree<ll> seg;  
 struct Cow {  
      ll s, t, c;  
      bool operator < (const Cow &a)const {  
           if (s == a.s) return t < a.t;  
           else return s < a.s;  
      }  
 } Cows[MAX_N];  
 int main()  
 {  
      scanf("%d%d%d", &N, &M, &E);  
      E -= M;  
      for (int i = 0; i < N; i++) {  
           scanf("%lld%lld%lld", &Cows[i].s, &Cows[i].t, &Cows[i].c);  
           Cows[i].s -= M;  
           Cows[i].t -= M;  
      }  
      sort(Cows, Cows + N);  
      fill(dp, dp + E + 1, INF);  
      seg.init(E + 1, INF);  
      int i1 = 0;  
      while (i1 < N && Cows[i1].s == 0) {  
           dp[Cows[i1].t] = min(dp[Cows[i1].t], Cows[i1].c);  
           seg.update(Cows[i1].t, Cows[i1].c);  
           i1++;  
      }  
      for (int i = i1; i < N; i++) {  
           ll v = min(dp[Cows[i].t], seg.query(Cows[i].s - 1, Cows[i].t + 1) + Cows[i].c);  
           dp[Cows[i].t] = v;  
           seg.update(Cows[i].t, v);  
      }  
      if (dp[E] == INF) cout << -1 << endl;  
      else cout << dp[E] << endl;  
      return 0;  
 }  

POJ.3735 Training little cats

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

2.Idea
Fast Power of Matrix.
Good blog:http://area.hateblo.jp/entry/2013/03/18/013421
3.Source

 int N;  
 ll A[101][101], B[101][101], C[101][101];  
 void mat_mul(ll a[][101], ll b[][101], ll dst[][101]) {  
      int i, j, k;  
      memset(C, 0, sizeof(C));  
      for (i = 0; i < N + 1; i++)  
           for (k = 0; k < N + 1; k++)  
                if (a[i][k])  
                     for (j = 0; j < N + 1; j++)  
                          C[i][j] += a[i][k] * b[k][j];  
      for (i = 0; i < N + 1; i++)  
           for (j = 0; j < N + 1; j++)  
                dst[i][j] = C[i][j];  
 }  
 void mat_pow(ll A[][101], ll n) {  
      int i;  
      memset(B, 0, sizeof(B));  
      for (i = 0; i < N + 1; i++) {  
           B[i][i] = 1;  
      }  
      while (n > 0) {  
           if (n & 1) mat_mul(B, A, B);  
           mat_mul(A, A, A);  
           n >>= 1;  
      }  
 }  
 int main()  
 {  
      ll n, m, k;  
      while (scanf("%lld%lld%lld", &n, &m, &k)) {  
           if (n + m + k == 0) break;  
           N = n;  
           memset(A, 0, sizeof(A));  
           for (int i = 0; i <= n; i++) A[i][i] = 1;  
           char a[5];  
           int b, c;  
           for (int i = 0; i < k; i++) {  
                scanf("%s", &a);  
                if (a[0] == 'g') {  
                     scanf("%d", &b);  
                     A[n][b - 1]++;  
                }  
                else if (a[0] == 'e') {  
                     scanf("%d", &b);  
                     for (int i = 0; i <= n; i++) A[i][b - 1] = 0;  
                }  
                else {  
                     scanf("%d%d", &b, &c);  
                     for (int i = 0; i <= n; i++) swap(A[i][b - 1], A[i][c - 1]);  
                }  
           }  
           mat_pow(A, m);  
           for (int i = 0; i < n; i++) {  
                printf("%lld%c", B[n][i], (i == n - 1) ? '\n' : ' ');  
           }  
      }  
      return 0;  
 }  

POJ.2506 Tiling

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

2.Idea
DP+BigInt Lib
3.Source

 const int Base = 1000000000;  
 const int Capacity = 100;  
 typedef long long huge;  
 struct BigInt {  
      int Len;  
      int Data[Capacity];  
      BigInt() : Len(0) {}  
      BigInt(const BigInt &V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof*Data); }  
      BigInt(int V) : Len(0) { for (; V>0; V /= Base) Data[Len++] = V%Base; }  
      BigInt &operator=(const BigInt &V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof*Data); return *this; }  
      int &operator[] (int Index) { return Data[Index]; }  
      int operator[] (int Index) const { return Data[Index]; }  
 };  
 int compare(const BigInt &A, const BigInt &B) {  
      if (A.Len != B.Len) return A.Len>B.Len ? 1 : -1;  
      int i;  
      for (i = A.Len - 1; i >= 0 && A[i] == B[i]; i--);  
      if (i<0)return 0;  
      return A[i]>B[i] ? 1 : -1;  
 }  
 BigInt operator+(const BigInt &A, const BigInt &B) {  
      int i, Carry(0);  
      BigInt R;  
      for (i = 0; i<A.Len || i<B.Len || Carry>0; i++) {  
           if (i<A.Len) Carry += A[i];  
           if (i<B.Len) Carry += B[i];  
           R[i] = Carry%Base;  
           Carry /= Base;  
      }  
      R.Len = i;  
      return R;  
 }  
 BigInt operator-(const BigInt &A, const BigInt &B) {  
      int i, Carry(0);  
      BigInt R;  
      R.Len = A.Len;  
      for (i = 0; i<R.Len; i++) {  
           R[i] = A[i] - Carry;  
           if (i<B.Len) R[i] -= B[i];  
           if (R[i]<0) Carry = 1, R[i] += Base;  
           else Carry = 0;  
      }  
      while (R.Len>0 && R[R.Len - 1] == 0) R.Len--;  
      return R;  
 }  
 BigInt operator*(const BigInt &A, const int &B) {  
      int i;  
      huge Carry(0);  
      BigInt R;  
      for (i = 0; i<A.Len || Carry>0; i++) {  
           if (i<A.Len) Carry += huge(A[i])*B;  
           R[i] = Carry%Base;  
           Carry /= Base;  
      }  
      R.Len = i;  
      return R;  
 }  
 istream &operator >> (istream &In, BigInt &V) {  
      char Ch;  
      for (V = 0; In >> Ch;) {  
           V = V * 10 + (Ch - '0');  
           if (In.peek() <= ' ') break;  
      }  
      return In;  
 }  
 ostream &operator<<(ostream &Out, const BigInt &V) {  
      int i;  
      Out << (V.Len == 0 ? 0 : V[V.Len - 1]);  
      for (i = V.Len - 2; i >= 0; i--) for (int j = Base / 10; j>0; j /= 10) Out << V[i] / j % 10;  
      return Out;  
 }  
 #define MAXN 250  
 BigInt dp[MAXN + 5];  
 int main()  
 {  
      memset(dp, 0, sizeof(dp));  
      dp[0] = 1;  
      dp[1] = 1;  
      dp[2] = 3;  
      dp[3] = 5;  
      for (int i = 4; i <= MAXN; i++) {  
           dp[i] = dp[i - 2] * 2 + dp[i - 1];  
      }  
      int t;  
      while (scanf("%d", &t) != EOF)  
           cout << dp[t] << endl;  
      return 0;  
 }  

POJ.3420 Quad Tiling

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

2.Idea
DP + Fast Power
Credit

3.Source

 typedef long long ll;  
 typedef vector<ll> vec;  
 typedef vector<vec> mat;  
 int n, M;  
 mat mul(mat A, mat B) {  
      mat C(A.size(), vec(B[0].size()));  
      for (int i = 0; i < A.size(); i++)  
           for (int k = 0; k < B.size(); k++)  
                for (int j = 0; j < B[0].size(); j++) {  
                     C[i][j] = (C[i][j] + (A[i][k] * B[k][j] % M)) % M;  
                }  
      return C;  
 }  
 mat pow(mat A, ll n)  
 {  
      mat B(A.size(), vec(A[0].size()));  
      for (int i = 0; i < A.size(); i++) {  
           B[i][i] = 1;  
      }  
      while (n) {  
           if (n & 1) B = mul(B, A);  
           A = mul(A, A);  
           n >>= 1;  
      }  
      return B;  
 }  
 int main()  
 {  
      int T[6][6] = {  
           { 1, 1, 1, 1, 0, 1 },  
           { 1, 0, 0, 1, 0, 0 },  
           { 1, 0, 0, 0, 1, 0 },  
           { 1, 1, 0, 0, 0, 0 },  
           { 0, 0, 1, 0, 0, 0 },  
           { 1, 0, 0, 0, 0, 0 }  
      };  
      mat A(6, vec(6, 0));  
      for (int i = 0; i < 6; i++) {  
           for (int j = 0; j < 6; j++) {  
                A[i][j] = T[i][j];  
           }  
      }  
      int Base[6][1] = {  
           { 1 },  
           { 1 },  
           { 1 },  
           { 1 },  
           { 0 },  
           { 1 },  
      };  
      mat B(6, vec(1, 0));  
      for (int r = 0; r < 6; r++)  
           B[r][0] = Base[r][0];  
      while (scanf("%d %d", &n, &M)) {  
           if (n == 0 && M == 0) break;  
           mat res = mul(pow(A, n - 1), B);  
           printf("%lld\n", res[0][0]);  
      }  
      return 0;  
 }  

POJ.1769 Minimizing maximizer

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

2.Idea
DP + Segtree

3.Source

 int n, m;  
 int s[MAX_M], t[MAX_M];  
 int dp[MAX_N + 1];  
 void solve()  
 {  
      rmq_init(n);  
      fill(dp, dp + n + 1, INF);  
      dp[1] = 0;  
      update(1, 0);  
      for (int i = 0; i < m; i++) {  
           int v = min(dp[t[i]], query(s[i], t[i] + 1) + 1);  
           dp[t[i]] = v;  
           update(t[i], v);  
      }  
      printf("%d\n", dp[n]);  
 }  

POJ.3233 Matrix Power Series

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

2.Idea
Binomial Power, DP

3.Source

 typedef vector<int> vec;  
 typedef vector<vec> mat;  
 int n, k, M;  
 mat A;  
 mat mul(mat &A, mat &B) {  
      mat C(A.size(), vec(B[0].size()));  
      for (int i = 0; i < A.size(); i++)  
           for (int k = 0; k < B.size(); k++)  
                for (int j = 0; j < B[0].size(); j++) {  
                     C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;  
                }  
      return C;  
 }  
 mat pow(mat A, ll n)  
 {  
      mat B(A.size(), vec(A[0].size()));  
      for (int i = 0; i < A.size(); i++) {  
           B[i][i] = 1;  
      }  
      while (n) {  
           if (n & 1) B = mul(B, A);  
           A = mul(A, A);  
           n >>= 1;  
      }  
      return B;  
 }  
 void solve()  
 {  
      mat B(n * 2, vec(n * 2));  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                B[i][j] = A[i][j];  
           }  
           B[n + i][i] = B[n + i][n + i] = 1;  
      }  
      B = pow(B, k + 1);  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                int a = B[n + i][j] % M;  
                if (i == j) a = (a + M - 1) % M;  
                printf("%d%c", a, j + 1 == n ? '\n' : ' ');  
           }  
      }  
 }  
 int main()  
 {  
      cin >> n >> k >> M;  
      mat AA(n, vec(n));  
      for (int i = 0; i < n; i++) {  
           for (int j = 0; j < n; j++) {  
                int t;  
                scanf("%d", &t);  
                AA[i][j] = t;  
           }  
      }  
      A = AA;  
      solve();  
      return 0;  
 }  

POJ.3734 Blocks

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

2.Idea
Using dp and fast power.

3.Source

 typedef vector<int> vec;  
 typedef vector<vec> mat;  
 const int M = 10007;  
 mat mul(mat &A, mat &B) {  
      mat C(A.size(), vec(B[0].size()));  
      for (int i = 0; i < A.size(); i++)  
           for (int k = 0; k < B.size(); k++)  
                for (int j = 0; j < B[0].size(); j++) {  
                     C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;  
                }  
      return C;  
 }  
 mat pow(mat A, ll n)  
 {  
      mat B(A.size(), vec(A[0].size()));  
      for (int i = 0; i < A.size(); i++) {  
           B[i][i] = 1;  
      }  
      while (n) {  
           if (n & 1) B = mul(B, A);  
           A = mul(A, A);  
           n >>= 1;  
      }  
      return B;  
 }  
 int N;  
 void solve()  
 {  
      mat A(3, vec(3));  
      A[0][0] = 2; A[0][1] = 1; A[0][2] = 0;  
      A[1][0] = 2; A[1][1] = 2; A[1][2] = 2;  
      A[2][0] = 0; A[2][1] = 1; A[2][2] = 2;  
      A = pow(A, N);  
      cout << A[0][0] << endl;  
 }  
 int main()  
 {  
      int t;  
      cin >> t;  
      while (t--) {  
           cin >> N;  
           solve();  
      }  
      return 0;  
 }  

POJ.2686 Traveling by Stagecoach

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

2.Idea
Bit DP.

3.Source

 #define MAX_N 8  
 #define MAX_M 30  
 int n, m, a, b, p;  
 int t[MAX_N];  
 int d[MAX_M][MAX_M];  
 double dp[1 << MAX_N][MAX_M];  
 void solve()  
 {  
      for (int i = 0; i < 1 << n; i++)   
           fill(dp[i], dp[i] + m, INF);  
      dp[(1 << n) - 1][a - 1] = 0;  
      double res = INF;  
      for (int S = (1 << n) - 1; S >= 0; S--) {  
           res = min(res, dp[S][b - 1]);  
           for (int v = 0; v < m; v++) {  
                for (int i = 0; i < n; i++) {  
                     if (S >> i & 1) {  
                          for (int u = 0; u < m; u++) {  
                               if (d[v][u] >= 0) {  
                                    dp[S & ~(1 << i)][u] = min(dp[S & ~(1 << i)][u], dp[S][v] + (double)d[v][u] / t[i]);  
                               }  
                          }  
                     }  
                }  
           }  
      }  
      if (res == INF) {  
           cout << "Impossible" << endl;  
      }  
      else {  
           cout << fixed << std::setprecision(6) << res << endl;  
      }  
 }  
 int main()  
 {  
      while (scanf("%d%d%d%d%d", &n, &m, &p, &a, &b) > 0) {  
           if (n + m + p + a + b == 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &t[i]);  
           }  
           for (int i = 0; i < p; i++) {  
                int x, y, g;  
                scanf("%d%d%d", &x, &y, &g);  
                x--;  
                y--;  
                d[x][y] = d[y][x] = g;  
           }  
           solve();  
      }  
      return 0;  
 }  

POJ.3264 Balanced Lineup

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

2.Idea
Two segment trees for Min and Max range queries.

3.Source

 const int MAX_N = 1 << 17;  
 const int I_MAX = 1 << 25;  
 const int I_MIN = -1;  
 int n, q, nn, datMin[2 * MAX_N - 1], datMax[2 * MAX_N - 1];  
 void update(int k, int a)  
 {  
      k += nn - 1;  
      datMin[k] = a;  
      datMax[k] = a;  
      while (k > 0) {  
           k = (k - 1) / 2;  
           datMin[k] = min(datMin[k * 2 + 1], datMin[k * 2 + 2]);  
           datMax[k] = max(datMax[k * 2 + 1], datMax[k * 2 + 2]);  
      }  
 }  
 int queryMin(int a, int b, int k, int l, int r)  
 {  
      if (r <= a || b <= l) return I_MAX;  
      if (a <= l && r <= b) return datMin[k];  
      else {  
           int v1 = queryMin(a, b, k * 2 + 1, l, (l + r) / 2);  
           int v2 = queryMin(a, b, k * 2 + 2, (l + r) / 2, r);  
           return min(v1, v2);  
      }  
 }  
 int queryMax(int a, int b, int k, int l, int r)  
 {  
      if (r <= a || b <= l) { return I_MIN; }  
      if (a <= l && r <= b) { return datMax[k]; }  
      else {  
           int v1 = queryMax(a, b, k * 2 + 1, l, (l + r) / 2);  
           int v2 = queryMax(a, b, k * 2 + 2, (l + r) / 2, r);  
           return max(v1, v2);   
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &n, &q);  
      nn = 2;  
      while (n > nn) nn *= 2;  
      for (int i = 0; i <= nn; i++) {  
           datMin[i] = I_MAX;  
           datMax[i] = I_MIN;  
      }  
      for (int i = 1; i <= n; i++) {  
           int tmp;  
           scanf("%d", &tmp);  
           update(i, tmp);  
      }  
      for (int i = 0; i < q; i++) {  
           int l, r;  
           scanf("%d%d", &l, &r);  
           printf("%d\n", queryMax(l, r + 1, 0, 0, nn) - queryMin(l, r + 1, 0, 0, nn));  
      }  
      return 0;  
 }  

POJ.2104 K-th Number

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

2.Idea
Sqrt decomposition

3.Source

 #define MAX_N 100000  
 const int B = 1000;  
 int N, M;  
 int A[MAX_N];  
 int I[MAX_N], J[MAX_N], K[MAX_N];  
 int nums[MAX_N];  
 vector<int> bucket[MAX_N / B];  
 void solve()  
 {  
      for (int i = 0; i < N; i++) {  
           bucket[i / B].push_back(A[i]);  
           nums[i] = A[i];  
      }  
      sort(nums, nums + N);  
      for (int i = 0; i < N / B; i++) {  
           sort(bucket[i].begin(), bucket[i].end());  
      }  
      for (int i = 0; i < M; i++) {  
           int l = I[i] - 1, r = J[i], k = K[i];  
           int lb = -1, ub = N - 1;  
           while (ub - lb > 1) {  
                int md = (lb + ub) / 2;  
                int x = nums[md];  
                int tl = l, tr = r, c = 0;  
                while (tl < tr && tl % B != 0) if (A[tl++] <= x) c++;  
                while (tl < tr && tr % B != 0) if (A[--tr] <= x) c++;  
                while (tl < tr) {  
                     int b = tl / B;  
                     c += upper_bound(bucket[b].begin(), bucket[b].end(), x) - bucket[b].begin();  
                     tl += B;  
                }  
                if (c >= k) ub = md;  
                else lb = md;  
           }  
           printf("%d\n", nums[ub]);  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &M);  
      for (int i = 0; i < N; i++) scanf("%d", &A[i]);  
      for (int i = 0; i < M; i++) scanf("%d%d%d", &I[i], &J[i], &K[i]);  
      solve();  
      return 0;  
 }  

POJ.3468 A Simple Problem with Integers

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

2.Idea
Segment Tree

3.Source

 #define MAX_N 100000  
 #define MAX_Q 100000  
 const int DAT_SIZE = (1 << 18) - 1;  
 int N, Q;  
 int A[MAX_N];  
 char T[MAX_Q];  
 int L[MAX_Q], R[MAX_Q], X[MAX_Q];  
 ll datA[DAT_SIZE], datB[DAT_SIZE];  
 void add(int a, int b, int x, int k, int l, int r)  
 {  
      if (a <= l && r <= b) {  
           datA[k] += x;  
      }  
      else if(l < b && a < r) {  
           datB[k] += (min(b, r) - max(a, l)) * x;  
           add(a, b, x, k * 2 + 1, l, (l + r) / 2);  
           add(a, b, x, k * 2 + 2, (l + r) / 2, r);  
      }  
 }  
 ll sum(int a, int b, int k, int l, int r)  
 {  
      if (b <= l || r <= a) {  
           return 0;  
      }  
      else if (a <= l && r <= b) {  
           return datA[k] * (r - l) + datB[k];  
      }  
      else {  
           ll res = (min(b, r) - max(a, l)) * datA[k];  
           res += sum(a, b, k * 2 + 1, l, (l + r) / 2);  
           res += sum(a, b, k * 2 + 2, (l + r) / 2, r);  
           return res;  
      }  
 }  
 void solve()  
 {  
      for (int i = 0; i < N; i++) {  
           cin >> A[i];  
           add(i, i + 1, A[i], 0, 0, N);  
      }  
      for (int i = 0; i < Q; i++) {  
           int a, b, x;  
           char c;  
           scanf(" %c", &c);  
           if (c == 'C') {  
                scanf("%d %d %d", &a, &b, &x);  
                add(a - 1, b, x, 0, 0, N);  
           }  
           else {  
                scanf("%d %d", &a, &b);  
                printf("%lld\n", sum(a - 1, b, 0, 0, N));  
           }  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &Q);  
      solve();  
      return 0;  
 }  

POJ.2991 Crane

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

2.Idea
Segment Tree

3.Source
Excellent example code here: http://mayokoex.hatenablog.com/entry/2015/08/17/203301
-----------------

 const double PI = 3.1415926536;  
 const int MAXN = 10010;  
 const int SEG_SIZE = (1 << 15) - 1;  
 int N, C;  
 int L[MAXN];  
 double ang[SEG_SIZE], vx[SEG_SIZE], vy[SEG_SIZE], pre[MAXN];  
 void init(int k, int l, int r) {  
      ang[k] = 0; vx[k] = 0;  
      if (r - l == 1) {  
           vy[k] = L[l];  
           return;  
      }  
      init(2 * k + 1, l, (l + r) / 2);  
      init(2 * k + 2, (l + r) / 2, r);  
      vy[k] = vy[2 * k + 1] + vy[2 * k + 2];  
 }  
 void change(int p, double add, int k, int l, int r) {  
      if (p <= l || p >= r) return;  
      int m = (l + r) / 2;  
      change(p, add, 2 * k + 1, l, m);  
      change(p, add, 2 * k + 2, m, r);  
      if (p <= m) ang[k] += add;  
      int chl = 2 * k + 1, chr = 2 * k + 2;  
      double s = sin(ang[k]), c = cos(ang[k]);  
      vx[k] = vx[chl] + c*vx[chr] - s*vy[chr];  
      vy[k] = vy[chl] + s*vx[chr] + c*vy[chr];  
 }  
 int main() {  
      int cnt = 0;  
      while (cin >> N >> C) {  
           if (cnt != 0) printf("\n");  
           cnt++;  
           for (int i = 0; i < N; i++) scanf("%d", L + i);  
           for (int i = 0; i <= N; i++) pre[i] = PI;  
           init(0, 0, N);  
           while (C--) {  
                int x, y;  
                scanf("%d%d", &x, &y);  
                double deg = y / 360. * 2 * PI;  
                double add = deg - pre[x];  
                change(x, add, 0, 0, N);  
                pre[x] = deg;  
                printf("%.2lf %.2lf\n", vx[0], vy[0]);  
           }  
      }  
      return 0;  
 }