POJ1068 --（模拟）

这题是在看一个书的时候的一个例题，当时并不明白啥意思，于是便找了下原题，以前没在POJ上刷过，这是开了个头，以后努力刷这个网站

1.p序列：当出现匹配括号对时，从该括号对的右括号开始往左数，直到最前面的左括号数，就是pi的值。

2.w序列：当出现匹配括号对时，包含在该括号对中的所有右括号数（包括该括号对）,就是wi的值。

要求给定加密后的p数组，求出w数组。

可以根据给的p数组先求出字符串s， p[i]-p[i-1]为第i个右括号紧跟在它前面的有多少个左括号，求出s，这里用了一点小技巧，大家以后可以试试，即是括号对用01序列表示

遍历s，每次找到右括号，然后回溯，遇到右括号就计数（回溯前找到的那个也算），直到遇到与它匹配的左括号（vis[]=false)，因为一个右括号有唯一的左括号匹配，所以一旦找到它的左括号，就用vis[]=true标记下。
之前我看的是C语言代码，然后用java交总是错，最后发现是数组越界问题，改正后提交正确

import java.util.Arrays;

import java.util.Scanner;

public class Main4 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

      int p[]=new int [21];

      int w[] = new int [21];

      boolean vis[]= new boolean [42];

        int t = sc.nextInt();

        while(t-->0){

             String s = "";

             int n = sc.nextInt();

            for(int i=1;i<=n;i++)

                p[i] = sc.nextInt();

            p[0]=0;

            for(int i=1;i<=n;i++){

                for(int j=1;j<=p[i]-p[i-1];j++)

                    s+="(";

                s+=")";

            }

            int k=1;

            Arrays.fill(vis,false);

            for(int i=0;i<2*n;i++){

                int cnt=1;

                if(s.charAt(i)==')'){

                    for(int j=i-1;j>=0;j--){

                        if(s.charAt(j)==')')

                            cnt++;

                        if(s.charAt(j)=='('&&!vis[j])

                        {

                            vis[j]=true;

                            break;

                        }

                    }

                    w[k++]=cnt;

                }

            }

            for(int i=1;i<=n;i++)

                System.out.print(w[i]+" ");

            System.out.println();

        }

        }

}

不过看博客有大佬这样定义，把括号对用01序列表示，也很不错哦，附上代码： http://user.qzone.qq.com/289065406/blog/1299127551

巴特西

POJ1068 --（模拟）

最新文章

热门文章