算法学习之路|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; } 就是简单模拟,没有坑。