| Problem:1068 | User: qq1203456195 | |
| Memory: 164K | Time: 0MS | |
| Language: C | Result: Accepted |
开始没读明白题的意思【鄙人英文太烂】，百度了题意，刚接触算法时间不长，没啥好想法，就想先根据q序列把()序列还原，然后再推w序列。
用了一个中午的时间把q序列还原成()了，然后就是推w序列。
既然是运算符匹配，肯定是栈了。又不想弄一个栈出来，怎么办呢？突然想到用一个变量就可以了，因为序列中只有(和非(两种情况，只要两类字符的数目抵消就是匹配完了。
#include <stdio.h> #include <string.h> int main() { int n,i,k,m,d,q,p,r,tk; char c[41]; scanf("%d",&n);//n个case while (n--) { //构造()序列 scanf("%d",&k);//q序列中k个元素 memset(c,'(',sizeof(c)); d=0;//(的数量 q=0;//栈 tk=k;//temp_k scanf("%d",&m);//q中的元素 tk--;//读取一个就记录一个 for (i=0;i<2*k;i++) { if(d==m && c[i]=='(')//匹配 {//确定Wi q=r=1; p=i-1; while(q&&p>=0) { if (c[p]=='(') q--;//出栈 else { q++;//入栈 r++;//）的数量 } p--; } c[i]=r+48; if(tk--)//读一个q中的元素 scanf("%d",&m); } if(c[i]=='(') d++;//统计(的数量 } for (i=0;i<2*k-1;i++) { if(c[i]!='(') printf("%d ",c[i]-48); } printf("%d\n",c[i]-48); } return 1; }
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/04/13/2446236.html，如需转载请自行联系原作者