POJ-1068 解题报告

题意简述

字符串s仅由括号构成（e.g.“(((()()())))”）。它可以用以下两种形式编码：

1、P编码： 记录每个右括号前有几个左括号。例如：上面的S串可被表示为：4 5 6 6 6 6；

2、W编码： 记录每对对应的左右括号之间有几个右括号。例如：上面的S串可被表示为：1 1 1 4 5 6

给定测试组数t(1 <= t <= 10)，输入每组的右括号数量，和该串的P编码。输出该串的W编码。

算法分析

直接模拟。从读入的P编码中还原原串（我直接还原为01串，0为左括号1为右括号）。

建一个栈。从头向后扫描还原的串。遇到左括号则压入栈内，遇到右括号则出栈，记录下该对左右括号的位置。

扫描每对左右括号间有多少个右括号。输出结果。

Problem Status: AC。时间0ms，内存120k

——————————————————————分割线——————————————————————

优化：

该题POJ排名第一的成绩，耗时0ms，内存0k……太恐怖了……想不到这么神奇的算法……

程序样例

#include<stdio.h>

int main() {
  int t, i, j, n[20][2], p = 0, s[50] = {
    0
  }, tem, stack[50], ans;
  scanf("%d", & i);
  for (; i > 0; i--) {
    scanf("%d%d", & t, & n[0][0]);
    for (p = 0; p < n[0][0]; p++) s[p] = 0;
    s[p] = 1;
    p++;
    for (j = 1; j < t; j++) {
      scanf("%d", & n[j][0]);
      tem = p + n[j][0] - n[j - 1][0];
      for (; p < tem; p++) s[p] = 0;
      s[p] = 1;
      p++;
    }
    p = 0;
    for (j = 0; j < t * 2; j++) {
      if (s[j] == 0) {
        stack[p] = j;
        p++;
      } else {
        n[(j - p + 2) / 2 - 1][0] = stack[p - 1];
        n[(j - p + 2) / 2 - 1][1] = j;
        p--;
      }
    }
    for (j = 0; j < t; j++) {
      ans = 0;
      for (p = n[j][0]; p <= n[j][1]; p++) ans += s[p];
      printf("%d ", ans);
    }
    printf("\n");
  }
  system("pause");
  return 0;
}