CodeForce 18D

 1 #include"iostream"
 2 #include"cstdio"
 3 #include"cstring"
 4 #include"algorithm"
 5 using namespace std;
 6 int num[2010][700],pre_pow[5010];
 7 int n;
 8 char cmd[5010][7];
 9 int pow[5010],res[700];
10 struct s1
11 {
12     int l,r,pow;
13 }ans[5010];
14 bool vis[5010];
15 
16 bool cmp(s1 a,s1 b)
17 {
18     return a.pow>b.pow;
19 }
20 
21 int main()
22 {
23     int i,j,c = 0;
24     int tot = 0;
25     memset(res,0,sizeof(res));
26     num[0][0] = num[0][1] = 1;
27     for(i = 1; i<=2000; ++i) {
28         num[i][0] = num[i-1][0]+1;
29         for(j = 1; j<=num[i][0]; ++j) {
30             num[i][j] = (num[i-1][j]<<1)+c;
31             c = num[i][j]/10;
32             num[i][j] %= 10;
33         }
34         if(!num[i][num[i][0]])
35             --num[i][0];
36     }
37     scanf("%d",&n);
38     for(i = 1; i<=n; ++i) {
39         scanf("%s%d",cmd[i],&pow[i]);
40         if(cmd[i][0]=='w')
41             pre_pow[pow[i]] = i;
42         else {
43             if(pre_pow[pow[i]]) {
44                 ans[++tot].l = pre_pow[pow[i]];
45                 ans[tot].r = i;
46                 ans[tot].pow = pow[i];
47                 pre_pow[pow[i]] = 0;
48             }
49         }
50     }
51     sort(ans+1,ans+1+tot,cmp);
52     for(i = 1; i<=tot; ++i) {
53         bool ok = 1;
54         for(j = ans[i].l; j<=ans[i].r; ++j) {
55             if(vis[j]) {
56                 ok = 0;
57                 break;
58             }
59         }
60         if(ok) {
61             for(j = ans[i].l; j<=ans[i].r; ++j) {
62                 vis[j] = 1;
63             }
64             int tar = ans[i].pow;
65             res[0] = max(res[0],num[tar][0])+1;
66             for(j = 1; j<=res[0]; ++j) {
67                 res[j] += num[tar][j]+c;
68                 c = res[j]/10;
69                 res[j] %= 10;
70             }
71             if(!res[res[0]])
72                 --res[0];
73         }
74     }
75     if(!res[0])
76         ++res[0];
77     for(j = res[0]; j>=1; --j) {
78         printf("%d",res[j]);
79     }
80     printf("
");
81 }
//还是把功能分给各个函数好一些，这样也易于调试