POJ 1068 Parencodings (类似括号的处理问题)
2024-08-29 11:44:48
Parencodings
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 19550 | Accepted: 11804 |
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of
left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right
parenthesis, say a in S, we associate an integer which is the number of
right parentheses counting from the matched left parenthesis of a up to
a. (W-sequence).
q By an integer sequence P = p1 p2...pn where pi is the number of
left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right
parenthesis, say a in S, we associate an integer which is the number of
right parentheses counting from the matched left parenthesis of a up to
a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The
first line of the input contains a single integer t (1 <= t <=
10), the number of test cases, followed by the input data for each test
case. The first line of each test case is an integer n (1 <= n <=
20), and the second line is the P-sequence of a well-formed string. It
contains n positive integers, separated with blanks, representing the
P-sequence.
first line of the input contains a single integer t (1 <= t <=
10), the number of test cases, followed by the input data for each test
case. The first line of each test case is an integer n (1 <= n <=
20), and the second line is the P-sequence of a well-formed string. It
contains n positive integers, separated with blanks, representing the
P-sequence.
Output
The
output file consists of exactly t lines corresponding to test cases.
For each test case, the output line should contain n integers describing
the W-sequence of the string corresponding to its given P-sequence.
output file consists of exactly t lines corresponding to test cases.
For each test case, the output line should contain n integers describing
the W-sequence of the string corresponding to its given P-sequence.
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 题目分析:
poj的一道英文题目,读了好久啊还借助了别人的翻译指导。此题多组处理数据,每组输入n个数,每个a[i]代表当前对应的右括号前面共有多少个左括号。
比如:n=6, 4 5 6 6 6 6 。 对应第一个右括号前有4个左括号,第二个右括号前有5个左括号,不过千万不要落下第一个右括号啊,以此类推下去。。。。。。
现在要求输出另一个数组,数组元素为当前右括号包含的括号总数!
比如:(()())
第一个右括号只包含自己,故为 1;
第二个右括号也只包含自己, 故为 1;
第三个右括号包含前面两个括号,再加上自己,故为 3.
所以应输出:1 1 3 ; 算法思路:根据n个数的数组模拟出原来的括号字符串,而我用的整形数组代替的,就是用1代表'(',用2代表‘)’,然后对这个整形数组处理。
样例解析:
(((()()()))))
1 1 112 12 12 2 2 2 2
标记数组:0 0 000 00 00 0 0 0 0
第一次处理:0 0 011..............等 标记数组遇到"2"则变成“1”。此时找到2了,则往2的前面去找1,也就是所谓的左括号,然后将找到的左括号标记为1,接下来将
该输出的数存入输出数组,计算公式为:(i-j+1)/2; i为右括号的下标,j为找到的匹配的左括号的下标。 Accepted的代码如下:
#include <stdio.h>
#include <string.h> int a[30];
int b[100], e;
int c[100];
int d[100], dd; int main()
{
int t, n;
int i, j, k; scanf("%d", &t) ;
while(t--)
{
e = 0;
scanf("%d", &n);
scanf("%d", &a[0] ); for(j=0; j<a[0]; j++)
{
b[e++] = 1;
}
b[e++]=2; for(i=1; i<n; i++)
{
scanf("%d", &a[i] );
for(j=0; j<(a[i]-a[i-1]); j++)
{
b[e++] = 1;
}
b[e++] = 2;
}
memset(c,0, sizeof(c));
dd = 0;
for(i=0; i<e; i++ )
{
if( b[i]==2 && c[i]==0 )
{
c[i]=1;
for(j=i-1; j>=0; j--)
{
if( b[j]==1 && c[j]==0 )
{
c[j]=1;
d[dd++] = (i-j+1)/2 ;
break;
}
}
}
}
for(k=0; k<dd; k++)
{
printf("%d%c", d[k],k==dd-1?'\n':' ' );
}
}
return 0;
}
最新文章
- ORACLE清理、截断监听日志文件(listener.log)
- async?
- Installscript如何给自定义路径的变量赋值
- 深入理解JavaScript系列(1):编写高质量JavaScript代码的基本要点
- freeCodeCamp:Repeat a string repeat a string
- 关于Linux的10个核心面试问题与答案
- jeesite 经常出现java.lang.ClassNotFoundException: org.springframework.web.context.ContextLoaderL解决思路
- MyBatis错误--Invalid bound statement (not found)
- 关于MVC EntityType has no key defined的问题
- 管道通信(使用popen和pclose功能简单的控制管道)
- Spring - bean的lazy-init属性(懒加载)
- 异常:This application has no explicit mapping for /error, so you are seeing this as a fallback.
- 利用 jQuery 来验证密码两次输入是否相同
- new Date().getTime()和System.currentTimeMillis()对比
- nginx中有关 root 和 alias的主要区别
- codeforces 1065F Up and Down the Tree
- BZOJ1036[ZJOI2008]树的统计——树链剖分+线段树
- eclipse的调试模式以及断点运行
- 关于JSONObject和JSONArray所需要的jar
- Java中动态获取项目根目录的绝对路径
热门文章
- WebScarab安装
- 使用新版MonoDevelop来进行unity工程调试
- 使用WebStorm将项目部署到IIS
- ssh不检查server变化
- 禁止";Windows Media Player Network Sharing Service";服务自动启动
- java -cp 命令 java jar 命令和 hadoop jar 命令
- windows_64下python下载安装Numpy、Scipy、matplotlib模块
- LeetCode_Minimum Depth of Binary Tree
- 【Mac + Pycharm】之实用东西以及配置东西
- jquery插件2