POJ 1068 Parencodings

小鱼儿 2022-09-30 00:44 90阅读 0赞

虽然是水题，但是还是费力。

思路：

先转换成01串，其中0表示‘（’，1表示‘）’，

再从头扫描，如果是0则跳过，我们关心的是1。如果是1，则匹配前面的0。默认应该是匹配1个0，记为count0。

这里匹配时候分为两种情况，

第一，如果往前扫描时候遇到1，则应该将countzero加1，表示应该多匹配一个0。

第二，如果往前扫描时候遇到0，如果countzero为0，则表示匹配出来了，当前遇到的这个0就是我们要匹配的那个0。否则则将countzero减1，继续下一次匹配。

另外，题目中说输入数字不超过20，但是还原成01串的时候会比20多。所以申请数组的时候需要多申请一些。

java代码如下：

import java.util.Scanner; public class Main \{ static int\[\] a = new int\[200\]; static int\[\] b = new int\[200\]; static int\[\] c = new int\[200\];// 记录最终生成的W数组 public static void main(String args\[\]) \{ Scanner cin = new Scanner(System.in); int n = cin.nextInt(); while (n != 0) \{ n--; int num = cin.nextInt(); for (int i = 0; i < num; i++) \{ a\[i\] = cin.nextInt(); \} // 先转换为01数组 int used = 0; int count = 0;// 记录已经填入的0的个数 int tempcount = count; int pos = 0;// 开始插入0的下标 for (int i = 0; i < num; i++) \{ int j = 0; for (j = pos; j < pos + a\[i\] - tempcount; j++) \{ b\[j\] = 0; count++; used++; \} tempcount = count; b\[j\] = 1;// 填完0之后填一个1 used++; pos = ++j; \} // 转换成01数组之后，查找每一个1之前与之匹配的位置，查看之间有几个0 int countzoer = 1;// 记录需要搜索的0的个数 int count0 = 0;// 记录搜索到匹配的那个0之前，搜索的0的个数，就是最终要输出的那个数字 int index = 0; int i; for (i = 0; i < used; i++) \{ count0 = 0; countzoer = 1; if (b\[i\] == 1) \{ // 往前搜索0.如果遇到1，则需要搜索的0的个数++； for (int j = i - 1; j >= 0; j--) \{ if (countzoer == 0) \{ c\[index\] = count0; index++; break; \} if (b\[j\] == 1) \{ countzoer++;// 需要搜索的0个数++ \} else \{ count0++; countzoer--; if (j == 0) \{ c\[index\] = count0; index++; \} \} \} \} \} c\[index\] = count0; int k; for (k = 0; k < num - 1; k++) \{ System.out.print(c\[k\] + " "); \} System.out.print(c\[k\]); System.out.println(); \} \} \}