poj 1090 Chain

　　简单格雷码加大数，最近想先看书，所以有空只是拿这些水题来练练手......

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int mod = 1000000000;
 5 int ans[40], dg;
 6 bool r[1005];
 7 
 8 void db(bool add){
 9     for (int i = 0; i < dg; i++){
10         ans[i] <<= 1;
11     }
12     if (add){
13         ans[0]++;
14     }
15     for (int i = 0; i < dg; i++){
16         while (ans[i] >= mod){
17             ans[i + 1]++;
18             ans[i] -= mod;
19         }
20     }
21     if (ans[dg]) dg++;
22 }
23 
24 void print(){
25     printf("%d", ans[dg - 1]);
26     for (int i = dg - 2; i >= 0; i--){
27         printf("%09d", ans[i]);
28     }
29 }
30 
31 void deal(int n){
32     dg = 0;
33     memset(ans, 0, sizeof(ans));
34     for (int i = 0; i < n; i++){
35         int a;
36 
37         scanf("%d", &a);
38         r[i] = a ? true : false;
39     }
40     db(r[n - 1]);
41     for (int i = n - 2; i >= 0; i--){
42         r[i] = r[i + 1] ^ r[i];
43         db(r[i]);
44     }
45     print();
46     puts("");
47 }
48 
49 int main(){
50     int n;
51 #ifndef ONLINE_JUDGE
52     freopen("in", "r", stdin);
53 #endif
54     while (~scanf("%d", &n)){
55        deal(n);
56     }
57 
58     return 0;
59 }

——written by Lyon