Codeforces Round #619 (Div2) D. Shortest and Longest LIS

红太狼 2023-07-06 09:51 5阅读 0赞

[D. Shortest and Longest LIS][]

**题意**：最长上升子序数。  
给你一个数组长度n，数据为1-n，一个长度为n-1的字符串，这个字符串只有>或< ,表示这n个数的大小排列。  
字符串会让数组中的数据产生最长上升子序数，题目让你求一个最小的最长上升子序数和一个最大的最长上升子序数。

最小最长上升子序数：lis就是字符串中连续<中最大的个数+1，比如>><<<>>< ,lis=4  
最大最长上升子序数：lis就是字符串中所有<的个数+1，比如>><<<>>< ,lis=5

操作：  
最小最长上升子序数：数组初始值为n~1，翻转每一段<，数组为倒置的序列，我们翻转每一段<块这一段就是本数组的一个lis，每一段<互不干扰。

最大最长上升子序数：数组初始值为1~n，翻转每一段>，数组为正序的序列，我们只需要把>段的翻转过来，就是让这一段从<段后面开始只贡献一个值，每一段都严格小于前一段的。

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+10;
    ll num[maxn];
    void solvemin(ll n,string str)
    { 
    	for(int i=1;i<=n;i++)
    		num[i]=n-i+1;
    	ll len=str.size(),l=0,r=0,flag=0;
    	for(int i=0;i<len;i++)
    	{ 
    		if(str[i]=='<'&&!flag)
    		{ 
    			l=i+1;
    			flag=1;
    		}
    		if(str[i]=='<'&&(str[i+1]=='>'||i==len-1))
    		{ 
    			ll k=num[i+2];
    			for(int j=l;j<=i+2;j++)
    				num[j]=k++;
    			flag=0;
    		} 
    	}
    	for(int i=1;i<=n;i++)
    		cout<<num[i]<<" ";
    	cout<<endl;
    }
    void solvemax(ll n,string str)
    { 
    	for(int i=1;i<=n;i++)
    		num[i]=i;
    	ll len=str.size(),l=0,r=0,flag=0;
    	for(int i=0;i<len;i++)
    	{ 
    		if(str[i]=='>'&&!flag)
    		{ 
    			l=i+1;
    			flag=1;
    		}
    		if(str[i]=='>'&&(str[i+1]=='<'||i==len-1))
    		{ 
    			ll k=num[l];
    			for(int j=i+2;j>=l;j--)
    				num[j]=k++;
    			flag=0;
    		}
    	}
    	for(int i=1;i<=n;i++)
    		cout<<num[i]<<" ";
    	cout<<endl;
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		ll n;
    		string str;
    		cin>>n>>str;
    		solvemin(n,str);
    		solvemax(n,str);
    	}
    	return 0;
    }

[D. Shortest and Longest LIS]: http://codeforces.com/contest/1304/problem/D