题目链接:QuestOJ 2067。
题目
题意简述
一个长度为 $n−1$ 的、仅由 <
与 >
组成的字符串。你现在要求出两个排列,要求如下:
- 排列中元素的大小关系与字符串中描述的一致。
- 在保证第一个要求的情况下,求出最长上升子序列最长的排列和最长上升子序列最短的排列。
数据范围
$$1\leq n\leq 2\times 10^5$$
时空限制
$$1\text{s}/256\text{MiB}$$
题解
思路
考虑序列,发现只要把连续的小于号连起来则有最长上升子序列。
最短上升子序列的情况处理一下即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=200000+5;
inline void Read(void);
inline void Work(void);
int main(void){
Read();
Work();
return 0;
}
int n;
char str[MAXN];
inline void Read(void){
scanf("%d\n%s",&n,str+1);
return;
}
bool l[MAXN],r[MAXN];
int a[MAXN];
inline void Work(void){
for(reg int T=0;T<=1;++T){
memset(l,false,sizeof(l));
memset(r,false,sizeof(r));
reg int last=0;
for(reg int i=1;i<=n;++i)
if(str[i]=='<'&&!last)
last=i;
else if((str[i]=='>'||i==n)&&last){
l[last]=r[i]=true;
last=0;
}
stack<int> ID,temp;
reg bool flag=false;
for(int i=n;i>=1;--i){
if(l[i]){
ID.push(i);
while(!temp.empty())
ID.push(temp.top()),temp.pop();
flag=false;
}
else if(r[i])
flag=true,temp.push(i);
else if(flag)
temp.push(i);
else
ID.push(i);
}
for(reg int i=n;i>=1;--i){
a[ID.top()]=i;
ID.pop();
}
if(T==1)
reverse(a+1,a+1+n);
for(reg int i=1;i<=n;++i)
printf("%d%c",a[i],i==n?'\n':' ');
reverse(str+1,str+n);
for(reg int i=1;i<=n-1;++i)
str[i]^=2;
}
return;
}
近期评论