Codeforces Round #788 (Div. 2)题解

题目大意：给定一个序列，能够交换任意两个数的正负性，问能否构造出不递减

方法: 负数必须是连续出现在前段，正数连续出现在后段。即构造出的序列是先负数后正数。

代码：

#include

using namespace std;

const int N=100010;
int p[N];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	
	int t;cin>>t;
	while(t--)
	{
		int n;
		cin>>n;		
		int cntn=0;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			p[i]=abs(x);
			if(x<0)cntn++;
		}
		bool flag=true;
		for(int i=1;i<=n;i++)
		{
			if(cntn)
			{
				cntn--;
				p[i]=-p[i];
			}
			if(i-1)
			{
				if(p[i-1]>p[i])
				{
					flag=false;
					break;
				}
			}
		}
		if(flag)
		{
			cout<<"YES"< 
B- 
题目大意：给定一个小写字母序列，再给若干个特殊的字母，每次操作，可以将序列中特殊字母的前一个字母删除。问删到不能删的时候，操作了几次
 
方法:   对于序列中出现的第一个特殊字母，它的操作数是前面的字母数； 
 
对于前有特殊字母的特殊字母，它的操作数是（1+特殊字母之间的字母数）
 
这个1是当删到特殊字母连续的时候，删一次就可以使开端只剩一个特殊字母。
 
然后将所有操作数取最大值
 
代码：
 
#include
#include
#include

using namespace std;

const int N=200010;
char a[N];
bool st[26];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(st,false,sizeof st);
		vector ans;
		int n;
		cin>>n;
		cin>>a+1;
		int k;cin>>k;
		for(int i=1;i<=k;i++)
		{
			char c;cin>>c;
			st[c-'a']=true;
		}
		int cnt1=0;
		int cnt2=0;
		for(int i=1;i<=n;i++)
		{
			if(st[a[i]-'a'])
			{
				ans.push_back(cnt1+cnt2);
				cnt2=1;
				cnt1=0;
			}else
			{
				cnt1++;
			}
		}
		int res=0;
		for(auto x:ans)
		{
			res=max(res,x);
		}
		cout< 
C- 
题目大意：给定2个全排列a，b。 再给一个需要构造的全排列c。
 
c[i]不是0：c[i]要么为a[i]要么为b[i],
 
c[i]是0，那么就可以任取a[i]或b[i]。
 
现在问能构造符合条件的全排列c的数字。
 
方法:   对于确定值的c[i]，不用考虑。不确定的就话，如果可以使对应所有的a[i],b[i]成一个圈，那么就有两种情况，即答案乘2。
 
注意：如果对于任选的a[i],b[i]（c!=0）在确定的a[i],b[i](c==0)出现过，说明不能任选，那么就构不成一个圈。
 
代码：
 
#include
#include
#include