Parencodings POJ - 1068
2021/10/15 23:47:26
本文主要是介绍Parencodings POJ - 1068,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Parencodings POJ - 1068
题目链接 :https://vjudge.net/problem/POJ-1068
题意:S是一个配对好的括号序列。P序列:
P
1
P
2
P
3...
P
n
,
P
i
P1 P2 P3 ...Pn, Pi
P1P2P3...Pn,Pi表示第i个右括号之前有多少个左括号。
W序列:
W
1
,
W
2
,
W
3
,
.
.
.
W
n
W1,W2,W3,...Wn
W1,W2,W3,...Wn Wi表示从
第
i
个
右
括
号
对
应
的
左
括
号
的
位
置
第i个右括号对应的左括号的位置
第i个右括号对应的左括号的位置 到
第
i
个
右
括
号
的
位
置
第i个右括号的位置
第i个右括号的位置有多少个右括号。
比如:
S (((()()()))) P-sequence 4 5 6666 W-sequence 1 1 1456
问题:给你P序列,求出W序列。
思路:读懂之后很容易。由P求出S,由S求出W,模拟这个过程即可。
具体见代码:
#include<iostream> #include<stack> using namespace std; const int maxn=27; int p[maxn]; int w[maxn]; int pa[maxn]; int r_pos[maxn]; stack<char>stk; int getw(int id,string s){ int res=0; int l=pa[id]; int r=r_pos[id]; //cout<<"l="<<l<<" r="<<r<<endl; for(int i=l;i<=r;i++){ if(s[i]==')')res++; } //cout<<"res="<<res<<endl; return res; } int main(){ int t; cin>>t; while(t--){ while(!stk.empty())stk.pop(); int n; cin>>n; int i; p[0]=0; for(i=1;i<=n;i++){ cin>>p[i]; } //p-->s string s=""; for(i=1;i<=n;i++){ int j; int num=p[i]-p[i-1]; for(j=1;j<=num;j++){ s+='('; } s+=')'; } //cout<<s<<endl; int tem=0;//l int sum=0;//r for(i=0;i<s.size();i++){ if(s[i]=='(')stk.push(++tem); else{ sum++; tem++; r_pos[sum]=i; int per=stk.top(); stk.pop(); pa[sum]=per; } } for(i=1;i<=sum;i++){ pa[i]-=1; } for(i=1;i<=n;i++){ w[i]=getw(i,s); } for(i=1;i<=n;i++){ if(i!=n)cout<<w[i]<<" "; else cout<<w[i]<<endl; } } return 0; }
这篇关于Parencodings POJ - 1068的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain