括号编码
Description
S = s1 s2...s2n 是一个符合格式的括号的字符串,S能按下面两种方式编码:
P编码:编码是一个整数序列P = p1 p2...pn,pi是第i个右括号之前的左括号的数目。
W编码:编码是一个整数序列W= p1 p2...pn,wi是第i个右括号的编码值,它等于这个右括号到与之匹配的左括号之间的右括号的数目(包括它自己)。
比如:
S ( ( ( ( ) ( ) ( ) ) ) )
P 4 5 6 6 6 6
W 1 1 1 4 5 6
请写一个程序将P序列转换成W序列。
输入:
第一行是一个整数K,表示有多少个测试用例,以后每两行一个测试用例。每个测试用例第一行为一个整数n(1 <= n <= 20),表示P序列长度,每个测试用例第二行n个非负整数,每个整数之间有一个空格分隔。
输出:
每行输出一个测试用例的结果。每行包括n个整数,每个整数之间用一个空格分隔。
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
//
#include<iostream>
using namespace std;
int a[1000],stack[1000],count[1000];
char str[1010];
int main()
{
int k,n,i,j,s,t,top,sum;
scanf("%d",&k);
while(k--)
{
cin>>n;
s=0;a[0]=0;sum=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
t=a[i]-a[i-1];
for(j=1;j<=t;j++)
{
str[++s]='(';
count[s]=sum;
}
str[++s]=')';
sum++;
count[s]=sum;
}
top=0;
for(i=1;i<s;i++)
{
if(str[i]=='(') stack[++top]=i;
else
cout<<count[i]-count[stack[top--]]<<" ";
}
cout<<count[i]-count[stack[top--]]<<endl;
}
return 0;
}
分享到:
相关推荐
ACM 在线测评第二题,括号配对!表示完全是自己写的,没有参考他人思想!有不足之处请指正!
这是一道比较经典的剪枝题目,如果不仔细考虑到 题目特性,就不能了解到搜索的速度
ACM ICPC程序设计与分析(C++实现)全本,挺厚的一本书,看的时候抓住关键点去看
包含ACM中常用的c++技巧与模板库,算是一些经验总结和技巧
基于C++的ACM模板
acm 括号匹配;
我网上发现的,欢迎大家使用,,对自己提高很有帮助,,的东西,,
利用低级音频函数WaveX,如waveinopen等函数,实现的语音压缩。
acm吃糖果的题目,自己根据提示写的比较简单的代码,欢迎指正
ACM杭电Problem 1002 C++程序 大数相加问题,注意输出的限制
基于C++实现的ACM-ACM竞赛常用模板
北大acm JudgeOnline 1979号 Red and Black题目的C++语言源代码
红黑树(c/c++)实现 acm 数据结构 红黑树(c/c++)实现 acm 数据结构 红黑树(c/c++)实现 acm 数据结构 红黑树(c/c++)实现 acm 数据结构
ACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和一些题目的代码实现c++源码.zipACM模板和...
用于GNURadio的DVB-S2ACM块_C++_Python_源码_下载.zip
ACM程序设计常用算法与数据结构参考
介绍了c++的一些基础知识,以及算法的解答与应用,对初学者很有用,可以参考。。
我测试通过的大数计算模板,遇到一些简单题可以直接代入
poj上面的300道AC题,c++源码,自己写的不会有任何问题。
acm模板acm模板acm模板acm模板acm模板acm模板acm模板acm模板