放假之前

发布时间:2017-1-19 10:28:22 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"放假之前 ",主要涉及到放假之前 方面的内容,对于放假之前 感兴趣的同学可以参考一下。

  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 int G[22][22];  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     LL key[STATE], val[STATE]; 17  18     void init() 19     { 20         sz = 0; 21         memset(h, 0, sizeof(h)); 22     } 23  24     void push(LL Key, LL 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         if(G[x][y]) 74         { 75             int L = code[y-1], U = code[y]; 76             if(L && U) 77             { 78                 if(L == U) 79                 { 80                     if(x != ex || y != ey) continue; 81                     code[y-1] = code[y] = 0; 82                 } 83                 else 84                 { 85                     code[y-1] = code[y] = 0; 86                     for(int j = 0; j <= M; j++) 87                     if(code[j] == U) code[j] = L; 88                 } 89             } 90             else if(L || U) 91             { 92                 int t = L ? L : U; 93                 if(G[x][y+1]) 94                 { 95                     code[y-1] = 0, code[y] = t; 96                     H[cur^1].push(encode(code), H[cur].val[i]); 97                 } 98                 if(G[x+1][y]) 99                 {100                     code[y-1] = t, code[y] = 0;101                     if(y == M) shift(code);102                     H[cur^1].push(encode(code), H[cur].val[i]);103                 }104                 continue;105             }106             else107             {108                 if(!G[x][y+1] || !G[x+1][y]) continue;109                 code[y-1] = code[y] = 20;110             }111         }112         else code[y-1] = code[y] = 0;113         if(y == M) shift(code);114         H[cur^1].push(encode(code), H[cur].val[i]);115     }116     return;117 }118 119 int main(void)120 {121     ex = ey = 0;122     scanf("%d %d", &N, &M);123     for(int i = 1; i <= N; i++)124     {125         char s[22];126         scanf("%s", s + 1);127         for(int j = 1; j <= M; j++)128         if(s[j] == '.') G[i][j] = 1, ex = i, ey = j;129     }130     if(!ex && !ey) puts("0");131     else132     {133 134     int cur = 0;135     H[cur].init();136     H[cur].push(0, 1);137     for(int i = 1; i <= N; i++)138         for(int j = 1; j <= M; j++)139             solve(i, j, cur), cur ^= 1;140     LL ans = 0;141     for(int i = 1; i <= H[cur].sz; i++) ans += H[cur].val[i];142     printf("%I64d\n", ans);143     }144     return 0;145 }
Aguin

12.25

HDU 1693 Eat the Trees

简化版。改改板子。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6 typedef long long LL;  7 int G[22][22];  8 int N, M;  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     LL key[STATE], val[STATE]; 17  18     void init() 19     { 20         sz = 0; 21         memset(h, 0, sizeof(h)); 22     } 23  24     void push(LL Key, LL 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         if(G[x][y]) 74         { 75             int L = code[y-1], U = code[y]; 76             if(L && U) 77             { 78                 if(L == U) 79                 { 80                     // if(x != ex || y != ey) continue; 81                     code[y-1] = code[y] = 0; 82                 } 83                 else 84                 { 85                     code[y-1] = code[y] = 0; 86                     for(int j = 0; j <= M; j++) 87                     if(code[j] == U) code[j] = L; 88                 } 89             } 90             else if(L || U) 91             { 92                 int t = L ? L : U; 93                 if(G[x][y+1]) 94                 { 95                     code[y-1] = 0, code[y] = t; 96                     H[cur^1].push(encode(code), H[cur].val[i]); 97                 } 98                 if(G[x+1][y]) 99                 {100                     code[y-1] = t, code[y] = 0;101                     if(y == M) shift(code);102                     H[cur^1].push(encode(code), H[cur].val[i]);103                 }104                 continue;105             }106             else107             {108                 if(!G[x][y+1] || !G[x+1][y]) continue;109                 code[y-1] = code[y] = 20;110             }111         }112         else code[y-1] = code[y] = 0;113         if(y == M) shift(code);114         H[cur^1].push(encode(code), H[cur].val[i]);115     }116     return;117 }118 119 int main(void)120 {121     int T;122     scanf("%d", &T);123     for(int kase = 1; kase <= T; kase++)124     {125         memset(G, 0, sizeof(G));126         scanf("%d %d", &N, &M);127         for(int i = 1; i <= N; i++)128             for(int j = 1; j <= M; j++)129                 scanf("%d", &G[i][j]);130         int cur = 0;131         H[cur].init();132         H[cur].push(0, 1);133         for(int i = 1; i <= N; i++)134             for(int j = 1; j <= M; j++)135                 solve(i, j, cur), cur ^= 1;136         LL ans = 0;137         for(int i = 1; i <= H[cur].sz; i++) ans += H[cur].val[i];138         printf("Case %d: There are %I64d ways to eat the trees.\n", kase, ans);139     }140     return 0;141 }

上一篇:hibernate学习笔记之一 hibernate简介
下一篇:Win10激活KMS

相关文章

关键词: 放假之前

相关评论