Codeforces Round #779 (Div. 2)

A. Marin and Photoshoot

题目链接：Problem - A - Codeforces

样例输入： 

9
3
000
3
001
3
010
3
011
3
100
3
101
3
110
3
111
19
1010110000100000101

样例输出：

4
2
1
0
2
0
0
0
17

题意：给定一个长度为n的01字符串，问我们至少要在这个区间内插入多少个1字符才能使得对于任意区间均有字符0的个数小于等于字符1的个数。

分析：通过分析不难发现对于任意两个相邻(此处的相邻不考虑中间的1)的0我们都要保证其之间至少要有2个1，简单模拟一下就能发现这个规律，然后我们按照这个方法分析一下每两个相邻的0然后统计一下需要插入的1即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
char s[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int ans=0;
		scanf("%s",s+1);
		int last=0;
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='0')
			{
				if(last) ans+=max(2-(i-last-1),0);
				last=i;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

B. Marin and Anti-coprime Permutation

题目链接：Problem - B - Codeforces

题意： 给定一个n，p1~pn为1~n的一个排列，问有多少个排列满足gcd(1⋅p1,2⋅p2,…,n⋅pn)>1，通过样例我们能够发现当n为奇数时，最大公约数一定是1，当n为偶数时，我们存在那种最大公约数大于1的情况，但是不存在最大公约数大于等于3的情况。现在我们就来分析一下n为偶数时最大公约数为2的方案数，那么就是一个奇数和一个偶数进行组合，总共有n/2个偶数，n/2个奇数，那么总的排列方案数就是(n/2)!*(n/2)!.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10,mod=998244353;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		if(n&1) puts("0");
		else
		{
			long long t=n/2;
			long long ans=1;
			for(int i=t;i>=1;i--)
				ans=ans*i%mod*i%mod;
			printf("%lld\n",ans);
		}
	}
	return 0;
} 

C. Shinju and the Lost Permutation

题目链接：Problem - C - Codeforces

样例输入： 

6
1
1
2
1 2
2
2 2
6
1 2 4 6 3 5
6
2 3 1 2 3 4
3
3 2 1

样例输出：

YES
YES
NO
NO
YES
NO

题意：有一个1~n的排列p1~pn，但是我们不知道这个排列是什么，现在有数组b[i][]=

[pn−i+1,…,pn,p1,p2,…,pn−i],也就是对原数组进行循环右移i次得到的结果，现在定义一个数组c[]，其中对于数组b[i][]，c[i]就是max(b[i][1~i]),c数组的权值定义为c数组中不同元素值的个数。现在给定b[1~n][]的对应权值数组c[1~n]，问是否存在一个排列满足上述要求。

题意写的可能有点乱，建议读英文题目

分析：能够发现对于c[i]等于1的位置代表p数组向右循环右移i次后最大的位置落在了右移后数组的第一个位置。那么该位置之后的数都会是最大值，那么在这种情况下再进行循环右移一次有可能使得这个数组的权值+1，但是绝对不可能+2及以上，因为只增加一个不同的值，不可能通过改变一个元素却导致权值增加的值不止1，这个简单分析就能得到.但是权值有可能减少，减少的值可以为任意情况。这就是我们判断序列是否合法的方法。最后需要注意的一点就是数组中不可能出现两个1，因为最大值只会有一个。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		bool flag=true;
		int id=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			a[i+n]=a[i];
			if(a[i]==1)
			{
				if(id) flag=false;
				id=i;
			}
		}
		for(int i=id+1;i<id+n;i++)
			if(a[i]-a[i-1]>1)
			{
				flag=false;
				break;
			}
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}

D1. 388535 (Easy Version)

题目链接：Problem - D1 - Codeforces

样例输入： 

3
0 3
3 2 1 0
0 3
4 7 6 5
0 2
1 2 3

样例输出：

0
4
3

题意：给定一个区间[l,r]，然后将这个区间的值修改为l~r的一个排列，现在将这个区间内的每一个值都异或上x得到另一个数组，现在给定这个数组问x的值可能是多少，输出任意一个满足题意的x即可。

注意：简单版本中l=0

分析：我们可以从l=0这个条件入手，由l=0我们可以知道，[0,r]中所有数中对于二进制的每一位上都有0的个数大于等于1的个数，所以我们对于修改后的数组统计每一位上1的个数，如果出现了1的个数大于0的个数，说明x的这一位为1，导致0和1进行了反转，否则就是0，代表未反转，通过这个方法我们就可以求出x的值。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		for(int i=l;i<=r;i++)
			scanf("%d",&a[i]);
		long long x=0;
		for(int i=0;i<17;i++)
		{
			int t0=0,t1=0;
			for(int j=l;j<=r;j++)
				if(a[j]>>i&1) t1++;
				else t0++;
			if(t1>t0) x+=1<<i;
		}
		printf("%lld\n",x);
	}
	return 0;
}

D2. 388535 (Hard Version)

题目链接：Problem - D2 - Codeforces

样例输入： 

3
4 7
3 2 1 0
4 7
4 7 6 5
1 3
0 2 1

样例输出：

4
0
3

题意：给定一个区间[l,r]，然后将这个区间的值修改为l~r的一个排列，现在将这个区间内的每一个值都异或上x得到另一个数组，现在给定这个数组问x的值可能是多少，输出任意一个满足题意的x即可。

注意：困难版本中l不一定为0

分析：我一开始还是按照通过分析1的个数是否发生变化来分析该位是否发生0和1的反转，但是交上之后发现wa了，通过分析发现对于0的数目和1的数目相同的情况时利用这种分析方法会出现问题，比如[1,2]^2=[0,3]，我们能够发现这样就会出现问题。

下面来阐述一下正解：

我们知道对于所给的数组b[]是由原数组a[]^x得到的，那么就有a[]=b[]^x,所以x一定是对于任意的i满足l<=i<=r，a[i]^b[j]，因为只有这样我们才能通过a[i]^b[j]^b[j]得到a[i],我们可以选择a[i]=l,那么就是l^b[j]中的一个(l<=j<=r)，我们暴力判断一下即可。我们知道由于b[j]!=b[k](j!=k)，那么就有l^b[j]!=l^b[k],也就是说l异或上r-l+1个不同的b数组会得到r-l+1个不同的数，我们要保证这r-l+1个数是l~r的一个排列，等价于判断这r-l+1个数中的最大值是r，最小值是l，这个复杂度是log级别的，再加上对n个数进行判断，所以复杂度总体是nlogn的，求异或最大值最小值就是tire树的模板题，直接利用tire树优化一下就可以了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e6+10;
int a[N];
int son[N][2],idx;
void insert(int x)
{
	int p=0;
	for(int i=16;i>=0;i--)
	{
		int u=x>>i&1;
		if(!son[p][u]) son[p][u]=++idx;
		p=son[p][u];
	}
}
int max_val(int x)
{
	int ans=0;
	int p=0;
	for(int i=16;i>=0;i--)
	{
		int u=x>>i&1;
		if(son[p][!u])
		{
			ans+=1<<i;
			p=son[p][!u];
		}
		else
			p=son[p][u];
	}
	return ans;
}
int min_val(int x)
{
	int ans=0;
	int p=0;
	for(int i=16;i>=0;i--)
	{
		int u=x>>i&1;
		if(son[p][u])
			p=son[p][u];
		else
		{
			p=son[p][!u];
			ans+=1<<i;
		}
	}
	return ans;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		idx=0;
		int l,r;
		scanf("%d%d",&l,&r);
		for(int i=l;i<=r;i++)
		{
			scanf("%d",&a[i]);
			insert(a[i]);
		}
		for(int i=l;i<=r;i++)
		{
			if(max_val(a[i]^l)==r&&min_val(a[i]^l)==l)
			{
				printf("%d\n",a[i]^l);
				break;
			}
		}
		for(int i=0;i<=idx;i++)
			son[i][0]=son[i][1]=0;
	}
	return 0;
}