POJ1068 Parencodings 解题报告
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).
Following is an example of the above encodings:S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456Write 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.
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.
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
分析:
对于给出的序列,明显是一定不会下降的,用ans[]来记录答案当A[i]>A[j]时其对应的ans[i]=1;注意到A[i]-ans[i]其实就是当前右括号对应的左括号的前面有多少个左括号很明显对每个A[i]-ans[i]都是唯一的,用它来作为匹配过的左括号的编号,这个编号从0开始所以当A[i]==A[i-1]时 令k=ans[i-1]+1;不断增加k直到A[i]-k的值没有在前面出现过时,ans[i]=k;
#include <iostream>
#include <cstring>
using namespace std;
int f[], g[], ans[];
int t, n, k, sum;
int main() {
cin >> t;
while (t--) {
cin >> n;
memset (g, , sizeof g);//数组g用来记录使用过的左括号
for (int i = ; i <= n; i++) {
cin >> f[i];
if (f[i] > f[i - ]) {//比前面的数大
ans[i] = ;//ans[i]赋值为一
g[f[i] - ans[i]] = ;//标记使用过的左括号
}
else {
int k = ans[i - ] + ;
while (g[f[i] - k]) k++;//找到没有使用过的左括号
g[f[i] - k] = ;
ans[i] = k;
}
}
cout << ans[];
for (int i = ; i <= n; i++)
cout << ' ' << ans[i];
cout << endl;
}
return ;
}
http://www.cnblogs.com/keam37/ keam所有 转载请注明出处
最新文章
- 【AR实验室】ARToolKit之制作自己的Marker/NFT
- 深入理解Java的接口和抽象类(转)
- 免费图片存储和图话【提供demo下载】
- YII的Modules模块化
- 【java项目小记--JManager】项目开始原因及github部署
- Mongodb Manual阅读笔记:CH4 管理
- 洛谷10月月赛Round.1| P3399 丝绸之路 [DP]
- 如何用c语言调用c++做成的动态链接库
- web设计经验<;七>;13步打造优雅的WEB字体
- ES6 - 对象
- c++ ,protected 和 private修饰的构造函数
- git使用之如何将github库下载到本地与如何将代码上传github
- js闭包深度讲解
- 面向对象(__item__)
- Object:所有类的超类
- 潭州课堂25班:Ph201805201 django 项目 第三十课 linux 系统迁移 (课堂笔记)
- 微软职位内部推荐-Software Engineer-Sharepoint
- 【转】Python xlrd、xlwt、xlutils读取、修改Excel文件
- Node.js中Process.nextTick()和setImmediate()的区别
- Airbnb JavaScript Style Guide
热门文章
- js的replace函数把";$";替换成成";\$";
- php socket通信演示以及socket操作类
- 简洁大方的wordpress主题,不容错过的主题,附带主题源码下载
- Elasticsearch--集群&;时光之门和恢复控制
- 阿里云虚拟主机的域名添加https的方法
- Winsock2_WSADATA
- vitualbox网络设置链接
- Laravel Excel模板导出-带图片
- js 给url添加时间戳 解决浏览器缓存
- 下载kaggle数据集,验证手机号