#11263. 括弧编码

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

有一个括号串(括号成对),给出一串数字数组p,p[i]表示从左往右第i个右括号左边共有p[i]个左括号,

请根据数组p,求数组w,其中w[i]表示第i个右括号和其所匹配的左括号之间有多少个左括号(包括这个左括号本身)

例如:

一组括号 (((()()())))

p数组为:4 5 6 6 6 6,表示第1个右括号左边有4个左括号;第2个右括号左边有5个左括号...

w数组为:1 1 1 4 5 6,表示第1个右括号与它的匹配左括号之间有1个左括号;第2个右括号与它的匹配左括号之间有1个左括号...

题目要求根据p求w.

输入格式

第一行,测试数据的组数t(1 <= t <= 10)

接下来t组,每组第一行,是一个整数n(1 <= n <= 20),表示右括号个数;第二行是n个数,表示p数组的数据。

输出格式

共t行,每一行表示w数组的数据

样例

样例输入

2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9

样例输出

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

数据范围与提示

POJ1068 Parencodings

解题思路:

  1. 虽然没说,但是可以推测出,括号的个数是偶数;第一个一定是(,最后一个一定是)
  2. P方法和W方法之间可能存在公式类的规律,但是要寻找不是特别简单
  3. 手动分析过程中,我们知道,可以模拟出推到W的过程-模拟法
  4. 括号匹配,一定是stack结构
  5. 思路就是:根据P还原括号数组,利用stack,推到出W