POJ 1472 Instant Complexity 应该叫它编程题。。

　　这个题目是分到“模拟题”一类的，我觉得模拟的成分比较少，主要考察编程能力。独立写完这个题特别兴奋。。。所以我必须好好说一说，独家哦。。。

　　题意是计算一段伪代码的时间复杂度，整体代码夹在“BEGIN”和“END”之间，中间有很多循环语句，夹在“LOOP X”和“END”之间，表示循环X次。第一眼一看很难下手，其实只要想到一点这个题就非常水了：

　　“BEGIN”语句可以看做”LOOP 1“。

　　这样的话整个程序的递归结构就明显了，就是LOOP调用LOOP，直接写个LOOP函数就是了。。

　　不过这个题除去恶心到死的输出格式，还是有值得注意的地方的，比如递归过程中申请的临时空间是不方便传回的，而且函数结束后这些空间没法free掉，所以我们需要先申请空间，然后传入下一次递归，这样等下一次递归结束以后方便我们free掉，不然工程编码时就造成内存泄露了，不过对于ACM来说无所谓了。。。

　　最后说一下输出格式，系数大于一才输出系数，指数大于1才输出指数，要注意认真处理系数和指数是1和0的时候。还有注意输出0的情况，因为这个错了好久。

　　第一次写这么多题解。。最后是代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 //循环lpNum次，结果存入ans
 6 void loop(int *ans, char *lpNum)
 7 {
 8     char s[10], loopNum[10] = {0};
 9     while(scanf("%s", s) && s[0] != 'E')
10     {
11         if(s[0] == 'L')
12         {
13             //注意先申请tmp数组再递归，不要在递归的时候申请
14             //最好动态申请，便于释放，其他地方也是
15             //int tmp[11] = {0};
16             int *tmp = new int[11];
17             memset(tmp, 0, 11*sizeof(int));
18 
19             scanf("%s", loopNum);
20             loop(tmp, loopNum);
21             for(int i = 0; i <= 10; i++)
22                 ans[i] += tmp[i];
23 
24             //调用结束后释放，最近在学习写工程。。
25             //delete tmp;
26         }
27         else if(s[0] == 'O')
28         {
29             int x;
30             scanf("%d", &x);
31             ans[0] += x;
32         }
33     }
34     if(lpNum[0] == 'n')
35     {
36         for(int i = 10; i > 0; i--)
37             ans[i] = ans[i-1];
38         ans[0] = 0;
39     }
40     else
41     {
42         int x = atoi(lpNum);
43         for(int i = 0; i <= 10; i++)
44             ans[i] *= x;
45     }
46 }
47 
48 int main()
49 {
50     int t;
51     int ans[11];
52     scanf("%d", &t);
53     for(int item = 1; item <= t; item++)
54     {
55         memset(ans, 0, sizeof(ans));
56         scanf("%*s");
57         loop(ans, "1");
58 
59         //下面全是输出格式，不要看了，眼花。。
60         printf("Program #%d
Runtime = ", item);
61         bool first = 1;
62         for(int i = 10; i >= 0; i--)
63         {
64             if(ans[i] == 0)continue;
65             if(i == 0)printf("%s%d", first ? "" : "+", ans[0]);
66             else if(ans[i] == 1)
67                 printf("%sn", first ? "" : "+");
68             else if(ans[i] > 1)
69                 printf("%s%d*n", first ? "" : "+", ans[i]);
70             if(i > 1)printf("^%d", i);
71             first = 0;
72         }
73         if(first)printf("0");
74         printf("

");
75     }
76     return 0;
77 }

OOOOOO