Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-1068 解题报告

POJ

题意简述

字符串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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *