CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)

A. Indirect Sort

题目链接：Problem - A - Codeforces

样例输入：

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

样例输出：

Yes
Yes
No
No
No
No
Yes

题意：一开始给定一个长度为n的1~n的排列，n>=3,我们可以对这个排列进行操作，每次操作选择三个位置i,j,k，满足1<=iak那么就令ai=ai+aj,否则交换aj和ak。问我们能否通过这种操作使得最后n个数呈现非递降序列。

分析：我们能够发现，如果a[i]是a[i~n]中的最小值，那么我们可以任意选择a[(i+1)~n]中的任意元素进行交换，肯定能够将其按照非递减顺序进行排序，但是我们发现a[i]的值不会被改变，这个时候如果a[i]是全局最小值，而且i!=1，那么前面的数是不能对a[i]的位置产生影响的，又没办法减少一个数的值，所以一定不可能使得最后呈现非递降顺序。所以我们只需要判断第一个位置是不是全局最小值即可。

代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		if(a[1]==1) puts("Yes");
		else puts("No");
	}
	return 0;
} 

B. Maximum Substring

题目链接：Problem - B - Codeforces

样例输入： 

6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0

样例输出：

9
12
16
12
9
1

题意：给定一个长度为n的01串，让我们求出来这个串中的子串的贡献的最大值。一个子串的贡献值计算方式如下：

先求出这个子串中的字符0的个数cnt0和字符1的个数cnt1

如果cnt0=0,那么贡献就是cnt1*cnt1

如果cnt1=0,那么贡献就是cnt0*cnt0

否则，贡献为cnt0*cnt1

分析：这个就很容易贪心了，由于cnt0和cnt1会随着区间长度的增大而增大，所以如果子串中同时含有1和0的话我们会尽可能地增大区间长度，答案贡献就是按照第三种方式进行计算，那么我们可以先计算一下整个字符串的字符0的个数和字符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);
		scanf("%s",s+1);
		int cnt0=0,cnt1=0;
		for(int i=1;i<=n;i++)
		{
			if(s[i]=='0') cnt0++;
			else cnt1++;
		}
		long long ans=1ll*cnt0*cnt1;
		if(!cnt0) ans=1ll*cnt1*cnt1;
		else if(!cnt1) ans=1ll*cnt0*cnt0;
		int mx0=0,mx1=0;
		for(int i=2;i<=n;i++)
		{
			int id=1;
			while(i<=n&&s[i]==s[i-1]) i++,id++;
			if(s[i-1]=='0') mx0=max(mx0,id);
			else mx1=max(mx1,id);
		}
		ans=max(ans,max(1ll*mx0*mx0,1ll*mx1*mx1));
		printf("%lld\n",ans);
	}
	return 0;
}

C. Complementary XOR

题目链接：Problem - C - Codeforces

 样例输入：

5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111

样例输出：

YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3

题意：给定两个长度为n的01串a和b，每次操作我们可以选择一个区间[l,r]，将a串中位于该区间内的数字反转，b串中不在该区间内的数字反转。问能否通过该操作使得a串和b串全部变成0串，如果能就输出操作方案，否则输出-1.

分析：首先我们不难发现，只有当a串和b串完全相反或者完全相同时才能使得经过操作后全部变成0串。如果a串和b串一开始完全相同的话那么我们可以先对整个区间进行一次操作，那么a串和b串就会变成完全相反。然后我们每次对a串中为1的位置进行操作即可，每次选定一个区间操作后，a串和b串要么完全相同，要么完全相反，那么当a串变为全0后，b串要么全0，要么全1，如果要是全0的话那么我们就不需要额外操作，否则选定区间[1,1],[2,n],[1,n]分别进行一次操作即可使得b数组变为全0。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
char s1[N],s2[N];
int l[N],r[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		scanf("%s%s",s1+1,s2+1);
		bool flag=true;
		int tt=0;
		if(s1[1]==s2[1])
		{
			l[++tt]=1,r[tt]=n;
			for(int i=1;i<=n;i++)
				s1[i]='0'+((s1[i]-'0')^1);
		}
		for(int i=2;i<=n;i++)
			if(s1[i]==s2[i])
			{
				flag=false;
				break;
			}
		if(!flag)
		{
			puts("NO");
			continue;
		}
		int cnt10=0,cnt20=0;
		for(int i=1;i<=n;i++)
		{
			if(s1[i]=='0') cnt10++;
			else cnt20++;
		}
		puts("YES");
		int cnt=0;//记录s1中1的个数
		for(int i=1;i<=n;i++)
			if(s1[i]=='1')
				l[++tt]=i,r[tt]=i,cnt++;
		if(cnt&1)
		{
			printf("%d\n",tt);
			for(int i=1;i<=tt;i++)
				printf("%d %d\n",l[i],r[i]);
		}
		else
		{
			l[++tt]=1,r[tt]=1;
			l[++tt]=2,r[tt]=n;
			l[++tt]=1,r[tt]=n;
			printf("%d\n",tt);
			for(int i=1;i<=tt;i++)
				printf("%d %d\n",l[i],r[i]);
		}
	}
	return 0;
}

D. Count GCD

题目链接：Problem - D - Codeforces

样例输入： 

5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2

样例输出：

3
1
0
595458194
200000000

题意：给你一个长度为n的数组a，每个元素的值都是大于等于1小于等于m的，现在让我们构造一个数组b，使得对于任意的1<=i<=n都满足gcd(b1,b2,……,bi)=ai，问这样的b数组的方案数是多少，其中b数组中的元素也都是大于等于1小于等于m的，结果对998244353取模。

分析：由gcd(a,b,c)=gcd(gcd(a,b),c)，我们可以知道a[i+1]=gcd(b1,b2,……,b[i+1])=gcd(gcd(b1,b2,……,bi),b[i+1])=gcd(ai,b[i+1])，其中b[i+1]<=m，那么就等价于求解满足等式a[i+1]=gcd(a[i],b[i+1])的b[i+1]的个数，也就是满足等式gcd(a[i]/a[i+1],b[i+1]/a[i+1])=1的b[i+1]/a[i+1]的个数，那么这个我们显然可以直接通过容斥(a[i]/a[i+1])的因子来进行求解。不会容斥原理的小伙伴可以看下这里：容斥原理_AC__dream的博客-CSDN博客_容斥原理csdn

但是需要注意的一点就是如果a[i+1]不是a[i]的因子时我们直接退出循环即可，否则会超时，因为实际上我们每次计算的gcd是非递增的，但是如果不考虑a[i+1]和a[i]的关系，那么我们计算的复杂度就不会一直减小，那么就会超时。

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10,mod=998244353;
long long a[N];
int log_2[N];
int lowbit(int x)
{
	return x&-x;
}
int main()
{
	int T;
	cin>>T;
	for(int i=0;(1<<i)<N;i++) log_2[1<<i]=i;//预处理一下以2为底的对数数组
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		long long ans=1;
		for(int i=2;i<=n;i++)
		{
			long long tm=m/a[i];//上界 
			long long ta=a[i-1]/a[i];
			if(ta*a[i]!=a[i-1])
			{
				ans=0;//无解
				break;
			}
			long long tans=0;
			vector<int>p;//存储质因子
			for(int j=2;j*j<=ta;j++) 
			{
				if(ta%j==0)
				{
					p.push_back(j);
					while(ta%j==0) ta/=j;
				}
			}
			if(ta>1) p.push_back(ta);
			int tt=p.size();
			for(int j=0;j<1<<tt;j++)
			{
				int sign=1;
				long long t=1;
				int jj=j;
				while(jj)
				{
					sign*=-1;
					t*=p[log_2[lowbit(jj)]];
					jj-=lowbit(jj);
					if(t>tm) break;
				}
				tans+=sign*(tm/t);
			}
			ans=ans*tans%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}