ACM括号编码(C++实现）

小咪咪 2022-05-15 13:07 195阅读 0赞

括号编码  
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;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，195人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM括号配对问题

在做南阳理工网站上的第二括号配对问题题目要求如下：描述现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0<N<=100）,表示有

快来打我*/ 2022年08月04日 09:13/ 0 赞/ 157 阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

ゝ一世哀愁。/ 2022年06月18日 10:55/ 0 赞/ 145 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX X

Love The Way You Lie/ 2022年06月18日 10:43/ 0 赞/ 192 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

一时失言乱红尘/ 2022年06月18日 10:18/ 0 赞/ 165 阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

深碍√TFBOYSˉ_/ 2022年05月15日 13:13/ 0 赞/ 132 阅读

相关 ACM非前缀编码 C++实现

非前缀编码 Description 有很多方法可以实现使用2进制序列对字符进行编码，比如典型的Huffman编码，如果在对字符的2进制编码中不存在某一个字符的编码是另

左手的ㄟ右手/ 2022年05月15日 13:12/ 0 赞/ 132 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX XX

灰太狼/ 2022年05月15日 13:09/ 0 赞/ 186 阅读

相关 ACM零件C++实现

零件 Description 有一种工业零件，分成左右两半，它们的形状由’X’和空格表示的二维图形表示，比如：左半的零件形状如下： XXXXX XXX XX

朴灿烈づ我的快乐病毒、/ 2022年05月15日 13:09/ 0 赞/ 178 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

小咪咪/ 2022年05月15日 13:07/ 0 赞/ 196 阅读

相关 ACM括号编码(C++实现）

括号编码 Description S = s1 s2...s2n 是一个符合格式的括号的字符串，S能按下面两种方式编码： P编码：编码是一个整数序列P = p1

Dear 丶/ 2022年05月15日 13:07/ 0 赞/ 167 阅读