寒假划水。

1.18

继续插头dp。

HDU 1964 Pipes

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 int N, M, ex, ey;
  8 char G[44][44];
  9 
 10 const int HASH = 10007;
 11 const int STATE = 1111111;
 12 struct HashMap
 13 {
 14     int sz, h[HASH];
 15     int nxt[STATE];
 16     int val[STATE];
 17     LL key[STATE];
 18 
 19     void init()
 20     {
 21         sz = 0;
 22         memset(h, 0, sizeof(h));
 23     }
 24 
 25     void push(LL Key, int Val)
 26     {
 27         int t = Key % HASH;
 28         for(int i = h[t]; i; i = nxt[i])
 29         if(key[i] == Key) {val[i] = min(val[i], Val); return;}
 30         nxt[++sz] = h[t];
 31         key[sz] = Key, val[sz] = Val;
 32         h[t] = sz;
 33     }
 34 } H[2];
 35 
 36 void decode(int * code, LL st)
 37 {
 38     for(int i = M; i >= 0; i--)
 39     {
 40         code[i] = st & 7LL;
 41         st >>= 3LL;
 42     }
 43 }
 44 
 45 int ch[22];
 46 LL encode(int * code)
 47 {
 48     LL st = 0;
 49     memset(ch, -1, sizeof(ch));
 50     int cnt = ch[0] = 0;
 51     for(int i = 0; i <= M; i++)
 52     {
 53         if(ch[code[i]] == -1) ch[code[i]] = ++cnt;
 54         code[i] = ch[code[i]];
 55         st <<= 3LL;
 56         st |= (LL) code[i];
 57     }
 58     return st;
 59 }
 60 
 61 void shift(int * code)
 62 {
 63     for(int i = M; i; i--) code[i] = code[i-1];
 64     code[0] = 0;
 65 }
 66 
 67 void solve(int x, int y, int cur)
 68 {
 69     H[cur^1].init();
 70     for(int i = 1; i <= H[cur].sz; i++)
 71     {
 72         int code[22];
 73         decode(code, H[cur].key[i]);
 74         int L = code[y-1], U = code[y];
 75         if(L && U)
 76         {
 77             if(L == U)
 78             {
 79                 if(x != ex || y != ey) continue;
 80                 code[y-1] = code[y] = 0;
 81                 if(y == M) shift(code);
 82                 H[cur^1].push(encode(code), H[cur].val[i] + (G[2*x-1][2*y] - '0') + (G[2*x][2*y-1] - '0'));
 83             }
 84             else
 85             {
 86                 code[y-1] = code[y] = 0;
 87                 for(int j = 0; j <= M; j++)
 88                 if(code[j] == U) code[j] = L;
 89                 if(y == M) shift(code);
 90                 H[cur^1].push(encode(code), H[cur].val[i] + (G[2*x-1][2*y] - '0') + (G[2*x][2*y-1] - '0'));
 91             }
 92         }
 93         else if(L || U)
 94         {
 95             int t = L ? L : U, v = L ? G[2*x][2*y-1] - '0' : G[2*x-1][2*y] - '0';
 96             if(y != M)
 97             {
 98                 code[y-1] = 0, code[y] = t;
 99                 H[cur^1].push(encode(code), H[cur].val[i] + v);
100             }
101             if(x != N)
102             {
103                 code[y-1] = t, code[y] = 0;
104                 if(y == M) shift(code);
105                 H[cur^1].push(encode(code), H[cur].val[i] + v);
106             }
107         }
108         else
109         {
110             if(x == N || y == M) continue;
111             code[y-1] = code[y] = 20;
112             if(y == M) shift(code);
113             H[cur^1].push(encode(code), H[cur].val[i]);
114         }
115     }
116     return;
117 }
118 
119 int main(void)
120 {
121     int T;
122     scanf("%d", &T);
123     while(T--)
124     {
125         scanf("%d %d", &N, &M); getchar();
126         ex = N, ey = M;
127         for(int i = 1; i <= N + N + 1; i++) gets(G[i] + 1);
128         int cur = 0;
129         H[cur].init();
130         H[cur].push(0, 0);
131         for(int i = 1; i <= N; i++)
132             for(int j = 1; j <= M; j++)
133                 solve(i, j, cur), cur ^= 1;
134         int ans = 9999999;
135         for(int i = 1; i <= H[cur].sz; i++) ans = min(ans, H[cur].val[i]);
136         printf("%d
", ans);
137     }
138     return 0;
139 }

Aguin

HDU 3377 Plan

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 int N, M, G[44][44];
  8 
  9 const int HASH = 10007;
 10 const int STATE = 1111111;
 11 struct HashMap
 12 {
 13     int sz, h[HASH];
 14     int nxt[STATE];
 15     int val[STATE];
 16     LL key[STATE];
 17 
 18     void init()
 19     {
 20         sz = 0;
 21         memset(h, 0, sizeof(h));
 22     }
 23 
 24     void push(LL Key, int Val)
 25     {
 26         int t = Key % HASH;
 27         for(int i = h[t]; i; i = nxt[i])
 28         if(key[i] == Key) {val[i] = max(val[i], Val); return;}
 29         nxt[++sz] = h[t];
 30         key[sz] = Key, val[sz] = Val;
 31         h[t] = sz;
 32     }
 33 } H[2];
 34 
 35 void decode(int * code, LL st)
 36 {
 37     for(int i = M; i >= 0; i--)
 38     {
 39         code[i] = st & 7LL;
 40         st >>= 3LL;
 41     }
 42 }
 43 
 44 int ch[22];
 45 LL encode(int * code)
 46 {
 47     LL st = 0;
 48     memset(ch, -1, sizeof(ch));
 49     int cnt = ch[0] = 0;
 50     for(int i = 0; i <= M; i++)
 51     {
 52         if(ch[code[i]] == -1) ch[code[i]] = ++cnt;
 53         code[i] = ch[code[i]];
 54         st <<= 3LL;
 55         st |= (LL) code[i];
 56     }
 57     return st;
 58 }
 59 
 60 void shift(int * code)
 61 {
 62     for(int i = M; i; i--) code[i] = code[i-1];
 63     code[0] = 0;
 64 }
 65 
 66 void solve(int x, int y, int cur)
 67 {
 68     H[cur^1].init();
 69     for(int i = 1; i <= H[cur].sz; i++)
 70     {
 71         int code[22];
 72         decode(code, H[cur].key[i]);
 73         int L = code[y-1], U = code[y];
 74         if(x == 1 && y == 1)
 75         {
 76             if(N != 1)
 77             {
 78                 code[y-1] = 1, code[y] = 0;
 79                 if(y == M) shift(code);
 80                 H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
 81             }
 82             if(M != 1)
 83             {
 84                 decode(code, H[cur].key[i]);
 85                 code[y-1] = 0, code[y] = 1;
 86                 if(y == M) shift(code);
 87                 H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
 88             }
 89         }
 90         else if(x == N && y == M)
 91         {
 92             if(L && U || !L && !U) continue;
 93             code[y-1] = code[y] = 0;
 94             int ok = 1;
 95             for(int i = 0; i < y - 1; i++)
 96                 if(code[i]) ok = 0;
 97             if(ok) H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
 98         }
 99         else
100         {
101             if(L && U)
102             {
103                 if(L == U) continue;
104                 else
105                 {
106                     code[y-1] = code[y] = 0;
107                     for(int j = 0; j <= M; j++)
108                     if(code[j] == U) code[j] = L;
109                     if(y == M) shift(code);
110                     H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
111                 }
112             }
113             else if(L || U)
114             {
115                 int t = L ? L : U;
116                 if(y != M)
117                 {
118                     code[y-1] = 0, code[y] = t;
119                     H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
120                 }
121                 if(x != N)
122                 {
123                     code[y-1] = t, code[y] = 0;
124                     if(y == M) shift(code);
125                     H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
126                 }
127             }
128             else
129             {
130                 code[y-1] = code[y] = 0;
131                 if(y == M) shift(code);
132                 H[cur^1].push(encode(code), H[cur].val[i]);
133                 if(x == N || y == M) continue;
134                 decode(code, H[cur].key[i]);
135                 code[y-1] = code[y] = 20;
136                 if(y == M) shift(code);
137                 H[cur^1].push(encode(code), H[cur].val[i] + G[x][y]);
138             }
139         }
140     }
141     return;
142 }
143 
144 int main(void)
145 {
146     int kase = 0;
147     while(~scanf("%d %d", &N, &M))
148     {
149         for(int i = 1; i <= N; i++)
150             for(int j = 1; j <= M; j++)
151                 scanf("%d", &G[i][j]);
152         if(N == 1 && M == 1) {printf("Case %d: %d
", ++kase, G[1][1]); continue;}
153         int cur = 0;
154         H[cur].init();
155         H[cur].push(0, 0);
156         for(int i = 1; i <= N; i++)
157             for(int j = 1; j <= M; j++)
158                 solve(i, j, cur), cur ^= 1;
159         int ans = -9999999;
160         for(int i = 1; i <= H[cur].sz; i++)
161             ans = max(ans, H[cur].val[i]);
162         printf("Case %d: %d
", ++kase, ans);
163     }
164     return 0;
165 }

Aguin

1.19

POJ 1739 Tony's Tour

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 int N, M, G[44][44];
  8 
  9 const int HASH = 10007;
 10 const int STATE = 1111111;
 11 struct HashMap
 12 {
 13     int sz, h[HASH];
 14     int nxt[STATE];
 15     LL val[STATE];
 16     LL key[STATE];
 17 
 18     void init()
 19     {
 20         sz = 0;
 21         memset(h, 0, sizeof(h));
 22     }
 23 
 24     void push(LL Key, int Val)
 25     {
 26         int t = Key % HASH;
 27         for(int i = h[t]; i; i = nxt[i])
 28         if(key[i] == Key) {val[i] += Val; return;}
 29         nxt[++sz] = h[t];
 30         key[sz] = Key, val[sz] = Val;
 31         h[t] = sz;
 32     }
 33 } H[2];
 34 
 35 void decode(int * code, LL st)
 36 {
 37     for(int i = M; i >= 0; i--)
 38     {
 39         code[i] = st & 7LL;
 40         st >>= 3LL;
 41     }
 42 }
 43 
 44 int ch[22];
 45 LL encode(int * code)
 46 {
 47     LL st = 0;
 48     memset(ch, -1, sizeof(ch));
 49     int cnt = ch[0] = 0;
 50     for(int i = 0; i <= M; i++)
 51     {
 52         if(ch[code[i]] == -1) ch[code[i]] = ++cnt;
 53         code[i] = ch[code[i]];
 54         st <<= 3LL;
 55         st |= (LL) code[i];
 56     }
 57     return st;
 58 }
 59 
 60 void shift(int * code)
 61 {
 62     for(int i = M; i; i--) code[i] = code[i-1];
 63     code[0] = 0;
 64 }
 65 
 66 void solve(int x, int y, int cur)
 67 {
 68     H[cur^1].init();
 69     for(int i = 1; i <= H[cur].sz; i++)
 70     {
 71         int code[22];
 72         decode(code, H[cur].key[i]);
 73         int L = code[y-1], U = code[y];
 74         if(!G[x][y])
 75         {
 76             if(L || U) continue;
 77             code[y-1] = code[y] = 0;
 78             if(y == M) shift(code);
 79             H[cur^1].push(encode(code), H[cur].val[i]);
 80         }
 81         else
 82         {
 83             if(x == N && y == 1)
 84             {
 85                 if(U)
 86                 {
 87                     code[y-1] = code[y] = 0;
 88                     H[cur^1].push(encode(code), H[cur].val[i]);
 89                 }
 90                 else
 91                 {
 92                     code[y-1] = 0, code[y] = 20;
 93                     H[cur^1].push(encode(code), H[cur].val[i]);
 94                 }
 95             }
 96             else if(x == N && y == M)
 97             {
 98                 if(L && U || !L && !U) continue;
 99                 code[y-1] = code[y] = 0;
100                 if(y == M) shift(code);
101                 H[cur^1].push(encode(code), H[cur].val[i]);
102             }
103             else
104             {
105                 if(L && U)
106                 {
107                     if(L == U) continue;
108                     else
109                     {
110                         code[y-1] = code[y] = 0;
111                         for(int j = 0; j <= M; j++)
112                         if(code[j] == U) code[j] = L;
113                         if(y == M) shift(code);
114                         H[cur^1].push(encode(code), H[cur].val[i]);
115                     }
116                 }
117                 else if(L || U)
118                 {
119                     int t = L ? L : U;
120                     if(G[x][y+1])
121                     {
122                         code[y-1] = 0, code[y] = t;
123                         H[cur^1].push(encode(code), H[cur].val[i]);
124                     }
125                     if(G[x+1][y])
126                     {
127                         code[y-1] = t, code[y] = 0;
128                         if(y == M) shift(code);
129                         H[cur^1].push(encode(code), H[cur].val[i]);
130                     }
131                 }
132                 else
133                 {
134                     if(!G[x+1][y] || !G[x][y+1]) continue;
135                     decode(code, H[cur].key[i]);
136                     code[y-1] = code[y] = 20;
137                     if(y == M) shift(code);
138                     H[cur^1].push(encode(code), H[cur].val[i]);
139                 }
140             }
141         }
142     }
143     return;
144 }
145 
146 int main(void)
147 {
148     while(~scanf("%d %d", &N, &M) && N)
149     {
150         memset(G, 0, sizeof(G));
151         for(int i = 1; i <= N; i++)
152         {
153             char s[11];
154             scanf("%s", s + 1);
155             for(int j = 1; j <= M; j++)
156                 if(s[j] == '.') G[i][j] = 1;
157         }
158         if(!G[N][1] || !G[N][M]) {puts("0"); continue;}
159         if(N == 1 && M == 1) {printf("%d
", G[1][1]); continue;}
160         int cur = 0;
161         H[cur].init();
162         H[cur].push(0, 1);
163         for(int i = 1; i <= N; i++)
164             for(int j = 1; j <= M; j++)
165                 solve(i, j, cur), cur ^= 1;
166         LL ans = 0;
167         for(int i = 1; i <= H[cur].sz; i++) ans += H[cur].val[i];
168         printf("%lld
", ans);
169     }
170     return 0;
171 }

Aguin

POJ 3133 Manhattan Wiring

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 int N, M, G[44][44];
  8 
  9 const int HASH = 10007;
 10 const int STATE = 1111111;
 11 struct HashMap
 12 {
 13     int sz, h[HASH];
 14     int nxt[STATE];
 15     int val[STATE];
 16     LL key[STATE];
 17 
 18     void init()
 19     {
 20         sz = 0;
 21         memset(h, 0, sizeof(h));
 22     }
 23 
 24     void push(LL Key, int Val)
 25     {
 26         int t = Key % HASH;
 27         for(int i = h[t]; i; i = nxt[i])
 28         if(key[i] == Key) {val[i] = min(val[i], Val); return;}
 29         nxt[++sz] = h[t];
 30         key[sz] = Key, val[sz] = Val;
 31         h[t] = sz;
 32     }
 33 } H[2];
 34 
 35 void decode(int * code, LL st)
 36 {
 37     for(int i = M; i >= 0; i--)
 38     {
 39         code[i] = st & 7LL;
 40         st >>= 3LL;
 41     }
 42 }
 43 
 44 int ch[22];
 45 LL encode(int * code)
 46 {
 47     LL st = 0;
 48     memset(ch, -1, sizeof(ch));
 49     int cnt = ch[0] = 0;
 50     for(int i = 0; i <= M; i++)
 51     {
 52         // if(ch[code[i]] == -1) ch[code[i]] = ++cnt;
 53         // code[i] = ch[code[i]];
 54         st <<= 3LL;
 55         st |= (LL) code[i];
 56     }
 57     return st;
 58 }
 59 
 60 void shift(int * code)
 61 {
 62     for(int i = M; i; i--) code[i] = code[i-1];
 63     code[0] = 0;
 64 }
 65 
 66 void solve(int x, int y, int cur)
 67 {
 68     H[cur^1].init();
 69     for(int i = 1; i <= H[cur].sz; i++)
 70     {
 71         int code[22];
 72         decode(code, H[cur].key[i]);
 73         int L = code[y-1], U = code[y];
 74         if(!G[x][y])
 75         {
 76             if(L || U) continue;
 77             code[y-1] = code[y] = 0;
 78             if(y == M) shift(code);
 79             H[cur^1].push(encode(code), H[cur].val[i]);
 80         }
 81         else
 82         {
 83             if(L && U)
 84             {
 85                 if(L == U)
 86                 {
 87                     if(G[x][y] != 1) continue;
 88                     code[y-1] = code[y] = 0;
 89                     // for(int j = 0; j <= M; j++)
 90                     // if(code[j] == U) code[j] = L;
 91                     if(y == M) shift(code);
 92                     H[cur^1].push(encode(code), H[cur].val[i] + 1);
 93                 }
 94             }
 95             else if(L || U)
 96             {
 97                 int t = L ? L : U;
 98                 if(G[x][y] == 1)
 99                 {
100                     if(G[x][y+1])
101                     {
102                         code[y-1] = 0, code[y] = t;
103                         H[cur^1].push(encode(code), H[cur].val[i] + 1);
104                     }
105                     if(G[x+1][y])
106                     {
107                         code[y-1] = t, code[y] = 0;
108                         if(y == M) shift(code);
109                         H[cur^1].push(encode(code), H[cur].val[i] + 1);
110                     }
111                 }
112                 else if(G[x][y] == t)
113                 {
114                     code[y-1] = code[y] = 0;
115                     if(y == M) shift(code);
116                     H[cur^1].push(encode(code), H[cur].val[i] + 1);
117                 }
118             }
119             else
120             {
121                 if(G[x][y] == 1)
122                 {
123                     code[y-1] = code[y] = 0;
124                     if(y == M) shift(code);
125                     H[cur^1].push(encode(code), H[cur].val[i]);
126                     if(!G[x+1][y] || !G[x][y+1]) continue;
127                     decode(code, H[cur].key[i]);
128                     code[y-1] = code[y] = 2;
129                     if(y == M) shift(code);
130                     H[cur^1].push(encode(code), H[cur].val[i] + 1);
131                     decode(code, H[cur].key[i]);
132                     code[y-1] = code[y] = 3;
133                     if(y == M) shift(code);
134                     H[cur^1].push(encode(code), H[cur].val[i] + 1);
135                 }
136                 else
137                 {
138                     if(G[x][y+1])
139                     {
140                         code[y-1] = 0, code[y] = G[x][y];
141                         H[cur^1].push(encode(code), H[cur].val[i] + 1);
142                     }
143                     if(G[x+1][y])
144                     {
145                         code[y-1] = G[x][y], code[y] = 0;
146                         if(y == M) shift(code);
147                         H[cur^1].push(encode(code), H[cur].val[i] + 1);
148                     }
149                 }
150             }
151         }
152     }
153     return;
154 }
155 
156 int main(void)
157 {
158     while(~scanf("%d %d", &N, &M) && N)
159     {
160         memset(G, 0, sizeof(G));
161         for(int i = 1; i <= N; i++)
162         for(int j = 1; j <= M; j++)
163         {
164             scanf("%d", &G[i][j]);
165             if(G[i][j] == 0 || G[i][j] == 1) G[i][j] ^= 1;
166         }
167         int cur = 0;
168         H[cur].init();
169         H[cur].push(0, 0);
170         for(int i = 1; i <= N; i++)
171             for(int j = 1; j <= M; j++)
172                 solve(i, j, cur), cur ^= 1;
173         int ans = 9999999;
174         for(int i = 1; i <= H[cur].sz; i++)
175             ans = min(ans, H[cur].val[i]);
176         printf("%d
", ans == 9999999 ? 0 : ans - 2);
177     }
178     return 0;
179 }

Aguin

1.24

ZOJ - 3466

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 int N, M, G[66][66];
  8 
  9 const int HASH = 10007;
 10 const int STATE = 1111111;
 11 struct HashMap
 12 {
 13     int sz, h[HASH];
 14     int nxt[STATE];
 15     LL key[STATE], val[STATE];
 16 
 17     void init()
 18     {
 19         sz = 0;
 20         memset(h, 0, sizeof(h));
 21     }
 22 
 23     void push(LL Key, LL Val)
 24     {
 25         int t = Key % HASH;
 26         for(int i = h[t]; i; i = nxt[i])
 27         if(key[i] == Key) {val[i] += Val; return;}
 28         nxt[++sz] = h[t];
 29         key[sz] = Key, val[sz] = Val;
 30         h[t] = sz;
 31     }
 32 } H[2];
 33 
 34 void decode(int * code, LL st)
 35 {
 36     for(int i = N + N; i >= 0; i--)
 37     {
 38         code[i] = st & 1LL;
 39         st >>= 1LL;
 40     }
 41 }
 42 
 43 LL encode(int * code)
 44 {
 45     LL st = 0;
 46     int cnt = 0;
 47     for(int i = 0; i <= N + N; i++)
 48     {
 49         st <<= 1LL;
 50         st |= (LL) code[i];
 51     }
 52     return st;
 53 }
 54 
 55 void shift(int op, int * code)
 56 {
 57     if(op % 2)
 58     {
 59         for(int i = N + N; i > 1; i--) code[i] = code[i-2];
 60         code[0] = code[1] = 0;
 61     }
 62     else code[0] = code[N+N] = 0;
 63 }
 64 
 65 void solve(int x, int y, int cur)
 66 {
 67     H[cur^1].init();
 68     for(int i = 1; i <= H[cur].sz; i++)
 69     {
 70         int code[66];
 71         decode(code, H[cur].key[i]);
 72         int U = code[2*x-2], L1 = code[2*x-1], L2 = code[2*x];
 73         int D = G[x+1][y], R1 = G[x+y%2-1][y+1], R2 = G[x+y%2][y+1];
 74         if(G[x][y])
 75         {
 76             if(U && L1 && L2) continue;
 77             if(U + L1 + L2 == 2)
 78             {
 79                 code[2*x-2] = code[2*x-1] = code[2*x] = 0;
 80                 if(x == N) shift(y, code);
 81                 H[cur^1].push(encode(code), H[cur].val[i]);
 82             }
 83             else if(U || L1 || L2)
 84             {
 85                 if(D)
 86                 {
 87                     code[2*x-2] = code[2*x-1] = 0, code[2*x] = 1;
 88                     H[cur^1].push(encode(code), H[cur].val[i]);
 89                 }
 90                 if(R1)
 91                 {
 92                     code[2*x-2] = 1, code[2*x-1] = code[2*x] = 0;
 93                     if(x == N) shift(y, code);
 94                     H[cur^1].push(encode(code), H[cur].val[i]);
 95                 }
 96                 if(R2)
 97                 {
 98                     decode(code, H[cur].key[i]);
 99                     code[2*x-2] = 0, code[2*x-1] = 1, code[2*x] = 0;
100                     if(x == N) shift(y, code);
101                     H[cur^1].push(encode(code), H[cur].val[i]);
102                 }
103             }
104             else
105             {
106                 if(D && R1)
107                 {
108                     code[2*x-2] = 1, code[2*x-1] = 0, code[2*x] = 1;
109                     H[cur^1].push(encode(code), H[cur].val[i]);
110                 }
111                 if(D && R2)
112                 {
113                     code[2*x-2] = 0, code[2*x-1] = code[2*x] = 1;
114                     H[cur^1].push(encode(code), H[cur].val[i]);
115                 }
116                 if(R1 && R2)
117                 {
118                     code[2*x-2] = code[2*x-1] = 1, code[2*x] = 0;
119                     if(x == N) shift(y, code);
120                     H[cur^1].push(encode(code), H[cur].val[i]);
121                 }
122             }
123         }
124         else
125         {
126             if(U || L1 || L2) continue;
127             if(x == N) shift(y, code);
128             H[cur^1].push(encode(code), H[cur].val[i]);
129         }
130     }
131     return;
132 }
133 
134 int main(void)
135 {
136     while(~scanf("%d %d", &N, &M))
137     {
138         memset(G, 0, sizeof(G));
139         for(int i = 1; i <= N; i++)
140             for(int j = 1; j <= 8; j++)
141                 G[i][j] = 1;
142         for(int i = 1; i <= M; i++)
143         {
144             char s[22];
145             scanf("%s", s + 1);
146             G[s[1]-'A'+1][s[2]-'A'+1] = 0;
147         }
148         int cur = 0;
149         H[cur].init();
150         H[cur].push(0, 1);
151         for(int j = 1; j <= 8; j++)
152             for(int i = 1; i <= N; i++)
153                 solve(i, j, cur), cur ^= 1;
154         LL ans = 0;
155         for(int i = 1; i <= H[cur].sz; i++) ans += H[cur].val[i];
156         printf("%lld
", ans);
157     }
158     return 0;
159 }

Aguin

ZOJ - 3256

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 typedef long long LL;
  6 const int mod = 7777777;
  7 int N, M;
  8 
  9 const int maxn = 120;
 10 struct Matrix
 11 {
 12     int m[maxn][maxn];
 13     Matrix(){memset(m, 0, sizeof(m));}
 14     void E(){memset(m, 0, sizeof(m)); for(int i = 0; i < maxn; i++) m[i][i] = 1;}
 15 } G;
 16 
 17 Matrix M_mul(Matrix a, Matrix b)
 18 {
 19     Matrix ret;
 20     for(int i = 0; i < maxn; i++)
 21         for(int j = 0; j < maxn; j++)
 22             for(int k = 0; k < maxn; k++)
 23                 ret.m[i][j] = ( ret.m[i][j] + ((LL) a.m[i][k] * b.m[k][j]) % mod ) % mod;
 24     return ret;
 25 }
 26 
 27 Matrix M_qpow(Matrix P, LL n)
 28 {
 29     Matrix ret;
 30     ret.E();
 31     while(n)
 32     {
 33         if(n & 1LL) ret = M_mul(ret, P);
 34         n >>= 1LL;
 35         P = M_mul(P, P);
 36     }
 37     return ret;
 38 }
 39 
 40 const int HASH = 10007;
 41 const int STATE = 1111111;
 42 struct HashMap
 43 {
 44     int sz, h[HASH];
 45     int nxt[STATE];
 46     int key[STATE];
 47 
 48     void init()
 49     {
 50         sz = 0;
 51         memset(h, 0, sizeof(h));
 52     }
 53 
 54     int push(int Key)
 55     {
 56         int t = Key % HASH;
 57         for(int i = h[t]; i; i = nxt[i])
 58         if(key[i] == Key) return i;
 59         nxt[++sz] = h[t];
 60         key[sz] = Key;
 61         h[t] = sz;
 62         return sz;
 63     }
 64 } H;
 65 
 66 void decode(int * code, LL st)
 67 {
 68     for(int i = N - 1; i >= 0; i--)
 69     {
 70         code[i] = st & 3LL;
 71         st >>= 2LL;
 72     }
 73 }
 74 
 75 int ch[44];
 76 LL encode(int * code)
 77 {
 78     LL st = 0;
 79     memset(ch, -1, sizeof(ch));
 80     int cnt = ch[0] = 0;
 81     for(int i = 0; i < N; i++)
 82     {
 83         if(ch[code[i]] == -1) ch[code[i]] = ++cnt;
 84         code[i] = ch[code[i]];
 85         st <<= 2LL;
 86         st |= (LL) code[i];
 87     }
 88     return st;
 89 }
 90 
 91 int main(void)
 92 {
 93     while(~scanf("%d %d", &N, &M))
 94     {
 95         H.init();
 96         H.push(0);
 97         int code[22] = {0};
 98         code[0] = code[N-1] = 1;
 99         H.push(encode(code));
100         G = Matrix();
101         for(int i = 2; i <= H.sz; i++)
102         for(int j = 0; j < (1 << N); j++)
103         {
104             decode(code, H.key[i]);
105             int ok = 1, up = 0;
106             for(int k = 0; k < N; k++)
107             {
108                 if((1 << k) & j)
109                 {
110                     if(up && code[k]) {ok = 0; break;}
111                     else if(up) code[k] = up, up = 0;
112                     else if(!up && !code[k]) code[k] = up = 20 + k;
113                 }
114                 else
115                 {
116                     if(!up && !code[k]) {ok = 0; break;}
117                     else if(up && code[k])
118                     {
119                         if(up == code[k] && (j || k != N - 1)) {ok = 0; break;}
120                         for(int p = 0; p < N; p++)
121                         if(code[p] == up) code[p] = code[k];
122                         code[k] = up = 0;
123                     }
124                     else if(code[k]) up = code[k], code[k] = 0;
125                 }
126             }
127             if(up) ok = 0;
128             if(!ok) continue;
129             int ii = H.push(encode(code));
130             G.m[i][ii] = 1;
131         }
132         G = M_qpow(G, M);
133         if(!G.m[2][1]) puts("Impossible");
134         else printf("%d
", G.m[2][1]);
135     }
136     return 0;
137 }

Aguin

2.13

主席树

HDU - 5919

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int maxn = 2e5 + 10;
 7 
 8 int cnt;
 9 int a[maxn];
10 int rt[maxn];
11 
12 struct node
13 {
14     int sum;
15     int ls, rs;
16 } nod[maxn * 40];
17 
18 void update(int l, int r, int &x, int y, int pos, int v)
19 {
20     nod[++cnt] = nod[y]; nod[cnt].sum += v; x = cnt;
21     if(l == r) return;
22     int mid = (l + r) >> 1;
23     if(pos <= mid) update(l, mid, nod[x].ls, nod[y].ls, pos, v);
24     else update(mid + 1, r, nod[x].rs, nod[y].rs, pos, v);
25 }
26 
27 int query(int p, int tl, int tr, int l, int r)
28 {
29     if(tr < l || r < tl) return 0;
30     if(l <= tl && tr <= r) return nod[p].sum;
31     int mid = (tl + tr) >> 1;
32     int ret = query(nod[p].ls, tl, mid, l, r);
33     ret += query(nod[p].rs, mid + 1, tr, l, r);
34     return ret;
35 }
36 
37 int query(int p, int tl, int tr, int k)
38 {
39     if(tl == tr) return tl;
40     int mid = (tl + tr) >> 1;
41     if(nod[nod[p].ls].sum < k) return query(nod[p].rs, mid + 1, tr, k - nod[nod[p].ls].sum);
42     return query(nod[p].ls, tl, mid, k);
43 }
44 
45 int pre[maxn];
46 int main(void)
47 {
48     int T;
49     scanf("%d", &T);
50     for(int kase = 1; kase <= T; kase++)
51     {
52         int n, m;
53         scanf("%d %d", &n, &m);
54         for(int i = 1; i <= n; i++) scanf("%d", a + i);
55         cnt = 0;
56         memset(pre, 0, sizeof(pre));
57         rt[n+1] = 0;
58         for(int i = n; i; i--)
59         {
60             update(1, n, rt[i], rt[i+1], i, 1);
61             if(pre[a[i]]) update(1, n, rt[i], rt[i], pre[a[i]], -1);
62             pre[a[i]] = i;
63         }
64         int ans = 0;
65         printf("Case #%d:", kase);
66         while(m--)
67         {
68             int l_, r_, l, r;
69             scanf("%d %d", &l_, &r_);
70             l = min((l_ + ans) % n + 1, (r_ + ans) % n + 1);
71             r = max((l_ + ans) % n + 1, (r_ + ans) % n + 1);
72             int k = (query(rt[l], 1, n, l, r) + 1) / 2;
73             ans = query(rt[l], 1, n, k);
74             printf(" %d", ans);
75         }
76         puts("");
77     }
78     return 0;
79 }

Aguin

2.22

斜率dp

HDU - 3507

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int maxn = 5e5 + 10;
 5 int sum[maxn], st[maxn], dp[maxn];
 6 
 7 
 8 int main(void)
 9 {
10     int n, m;
11     while(~scanf("%d %d", &n, &m))
12     {
13         for(int i = 1; i <= n; i++) scanf("%d", sum + i);
14         for(int i = 1; i <= n; i++) sum[i] += sum[i-1];
15         int p1 = 1, p2 = 1;
16         st[p1] = 0;
17         for(int i = 1; i <= n; i++)
18         {
19             while(p2 < p1 && (dp[st[p2+1]] + sum[st[p2+1]] * sum[st[p2+1]]) - (dp[st[p2]] + sum[st[p2]] * sum[st[p2]]) <= 2 * sum[i] * (sum[st[p2+1]] - sum[st[p2]])) p2++;
20             dp[i] = dp[st[p2]] + (sum[i] - sum[st[p2]]) * (sum[i] - sum[st[p2]]) + m;
21             while(p2 < p1 && ((dp[i] + sum[i] * sum[i]) - (dp[st[p1]] + sum[st[p1]] * sum[st[p1]])) * (sum[st[p1]] - sum[st[p1-1]]) <= ((dp[st[p1]] + sum[st[p1]] * sum[st[p1]]) - (dp[st[p1-1]] + sum[st[p1-1]] * sum[st[p1-1]])) * (sum[i] - sum[st[p1]])) p1--;
22             st[++p1] = i;
23         }
24         printf("%d
", dp[n]);
25     }
26     return 0;
27 }

Aguin

2.23

HDU - 3480

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[10010], dp[5005][10010], st[10010];
 6 
 7 int main(void)
 8 {
 9     int T;
10     scanf("%d", &T);
11     for(int kase = 1; kase <= T; kase++)
12     {
13         int n, m;
14         scanf("%d %d", &n, &m);
15         for(int i = 1; i <= n; i++) scanf("%d", a + i);
16         sort(a + 1, a + n + 1);
17         for(int i = 1; i <= n; i++) dp[1][i] = (a[i] - a[1]) * (a[i] - a[1]);
18         for(int i = 2; i <= m; i++)
19         {
20             int p1 = 1, p2 = 1;
21             st[p1] = 0;
22             for(int j = 1; j <= n; j++)
23             {
24                 while(p1 > p2 && dp[i-1][st[p2+1]] + a[st[p2+1]+1] * a[st[p2+1]+1] - dp[i-1][st[p2]] - a[st[p2]+1] * a[st[p2]+1] <= 2 * a[j] * (a[st[p2+1]+1] - a[st[p2]+1])) p2++;
25                 dp[i][j] = dp[i-1][st[p2]] + (a[st[p2]+1] - a[j]) * (a[st[p2]+1] - a[j]);
26                 while(p1 > p2 && (dp[i-1][j] + a[j+1] * a[j+1] - dp[i-1][st[p1]] - a[st[p1]+1] * a[st[p1]+1]) * (a[st[p1]+1] - a[st[p1-1]+1]) <= (dp[i-1][st[p1]] + a[st[p1]+1] * a[st[p1]+1] - dp[i-1][st[p1-1]] - a[st[p1-1]+1] * a[st[p1-1]+1]) * (a[j+1] - a[st[p1]+1])) p1--;
27                 st[++p1] = j;
28             }
29         }
30         printf("Case %d: %d
", kase, dp[m][n]);
31     }
32     return 0;
33 }

Aguin

2.24

HDU - 2829

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 LL s[1111], s2[1111], dp[1111][1111];
 6 int a[1111], st[1111];
 7 
 8 int main(void)
 9 {
10     int n, m;
11     while(~scanf("%d %d", &n, &m) && n)
12     {
13         for(int i = 1; i <= n; i++) scanf("%d", a + i), s[i] = s[i-1] + a[i], s2[i] = s2[i-1] + a[i] * a[i];
14         for(int i = 1; i <= n; i++) dp[0][i] = (s[i] * s[i] - s2[i]) / 2;
15         for(int i = 1; i <= m; i++)
16         {
17             int p1 = 1, p2 = 1;
18             st[1] = 0;
19             for(int j = 1; j <= n; j++)
20             {
21                 while(p1 > p2 && 2 * dp[i-1][st[p2+1]] + s[st[p2+1]] * s[st[p2+1]] + s2[st[p2+1]] - 2 * dp[i-1][st[p2]] - s[st[p2]] * s[st[p2]] - s2[st[p2]] <= 2 * s[j] * (s[st[p2+1]] - s[st[p2]])) p2++;
22                 dp[i][j] = dp[i-1][st[p2]] + ((s[j] - s[st[p2]]) * (s[j] - s[st[p2]]) - s2[j] + s2[st[p2]]) / 2;
23                 while(p1 > p2 && (2 * dp[i-1][j] + s[j] * s[j] + s2[j] - 2 * dp[i-1][st[p1]] - s[st[p1]] * s[st[p1]] - s2[st[p1]]) * (s[st[p1]] - s[st[p1-1]]) <= (2 * dp[i-1][st[p1]] + s[st[p1]] * s[st[p1]] + s2[st[p1]] - 2 * dp[i-1][st[p1-1]] - s[st[p1-1]] * s[st[p1-1]] - s2[st[p1-1]]) * (s[j] - s[st[p1]])) p1--;
24                 st[++p1] = j;
25             }
26         }
27         printf("%I64d
", dp[m][n]);
28     }
29     return 0;
30 }

Aguin