全解题报告索引目录 -> 【北大ACM – POJ试题分类】
模拟的题型,基本难度不大,关键读懂题意:
对于给出的原括号串,存在两种数字密码串:
1.p序列:当出现匹配括号对时,从该括号对的右括号开始往左数,直到最前面的左括号数,就是pi的值。
2.w序列:当出现匹配括号对时,包含在该括号对中的所有右括号数(包括该括号对),就是wi的值。
题目的要求:
对给出的p数字串,求出对应的s串。
串长限制均为20
提示:在处理括号序列时可以使用一个小技巧,把括号序列转化为01序列,左0右1,处理时比较方便
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
//Memory Time //256K 0MS #include<iostream> using namespace std; int main(void) { int p[21]={0}; //使 p[0]=0 int w[20]; int str[40]; //括号串,左0右1 int n; int cases; cin>>cases; while(cases--) { memset(str,0,sizeof(str)); //str串初始化为全0 cin>>n; int i,j,k; /*Input P-sequence*/ for(i=1;i<=n;i++) cin>>p[i]; /*Convert the P-sequence to the string of parenthesese*/ for(j=0,i=1;i<=n;i++) //把P数列转化为01串,左括为0,右括为1 for(k=0;;k++) if(k<p[i]-p[i-1]) //以每个右括为终点,把括号串分成多个01子串(子串左边全是0,右边只有唯一的1.每个子串至少含一个1) j++; //k为各个子串的指针,j为str串的指针 else if(k==p[i]-p[i-1]) { str[j++]=1; break; } const int length=j; //str串长 /*Convert the string of parenthesese to the W-sequence*/ int count; for(i=0;i<length;i++) //str串向W数列转换 if(str[i]==1) //在str中遇到1(右括)就回溯,找出离其最近的0(左括) { count=2; //计数器初始化为2是因为当前正在寻找的配对的01将置换为两个'F' for(j=i-1;;j--) { if(str[j]==0) { str[i]=str[j]='F'; //01配对后就都置为'F' break; } else count++; //在回溯找0的过程中,每遇到一个F,计数器就+1 } cout<<count/2<<' '; //计数器的个数就是当前 括号对 所包含的 括号对 (包括当前括号对)数量的两倍 } cout<<endl; } return 0; } |
转载请注明:EXP 技术分享博客 » POJ1068 – Parencodings