算法学习之路|POJ 1068 Parencodings（简单模拟）
题目大意： 有一个括号串（括号成对），给出一串数字数组p，p[i]表示从左往右第i个右括号左边共有p[i]个左括号，求一个数组w，w[i]表示第i个右括号和其所匹配的左括号之间有多少个左括号（包括这个左括号本身） 一个例子： 括号串： (((()()()))) P 4 5 6 6 6 6 W 1 1 1 4 5 6 思路 用一个vis数组标标记，1表示左括号，0表示右括号，模拟出w数组时用2标记已经用过的左括号，-1标记已经用过的右括号 代码： #include<stdio.h> #include<string.h> #include<algorithm> #define maxn 100 int main() { int p[maxn],w[maxn],vis[maxn]; int t,n,index,ww; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); index=1;//标记vis数组 ww=1; p[0]=0; w[0]=0; for(int i=1;i<=n;i++) { scanf("%d",&p[i]); int temp=p[i]-p[i-1]; for(int j=1;j<=temp;j++) { vis[index++]=1; } index++; } for(int i=1;i<=n*2;i++)//输入数字有n个，说明括号有n对，因此vis数组有2n的长度 { int index2=1;//标记w数组 if(vis[i]==0) { vis[i]=-1; int x=i; while(vis[x]!=1) { if(vis[x]==2) { index2++; } x--; } w[ww++]=index2; vis[x]=2; } } for(int i=1;i<=n;i++) { printf("%d",w[i]); if(i<n) printf(" "); } printf("\n"); } return 0; } 就是简单模拟，没有坑。
