2022年ccpc桂林站

A. Lily

题目链接：Problem - A - Codeforces

样例一输入：

5
..L..

样例一输出：

C.L.C

样例二输入：

2
..

样例二输出：

CC

简化题意：给定一个只含有字符.和L的字符串，我们要将尽可能多的.换成C输出，前提是需要保证这个.的两端不能含有字符L，输出我们构造后的字符串。

分析：直接贪心构造即可，遍历每个位置，如果这个位置及其左右三个字符均不为L，那么这个位置就可以输出C，否则输出原字符即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
char s[N];
int main()
{
	int n;
	cin>>n;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]!='L'&&s[i]!='L'&&s[i+1]!='L')
			printf("C");
		else printf("%c",s[i]);
	}
	return 0;
}

C. Array Concatenation

题目链接：Problem - C - Codeforces

 样例输入：

5 10
26463 39326 86411 75307 85926

样例输出：

806275469

题意：给定一个长度为n的数组，我们可以对这个字符进行m次操作，每次操作有两种选择，一种是将当前数组a1,a2,……an变为a1,a2,……an，a1,a2,……an，另一种操作是将当前数组变为an,an-1,……a1，a1,a2,……an,可以发现每次对数组进行一次操作后数组的长度都会变为原来的2倍，假设最后的数组是b1,b2,……,bn'，那么我们就是要最大化(∑i=1n′∑j=1ibj)" role="presentation" style="position: relative;">(∑n′i=1∑ij=1bj)$(\sum _{i=1}^{n^{\prime }}\sum _{j=1}^{i}bj)$,注意是对1e9+7取模后的最大值。

分析：通过简单的模拟我们可以发现一个非常重要的性质，就是如果数组是回文的(这里的回文是指长度为n的数组a中，对于任意的i<=n都有a[i]=a[n-i+1])，那么对其进行操作1和操作2所得到的操作后数组是相同的。这个性质有什么用呢？我们发现操作2后的数组一定是一个回文的，所以只要某一次操作选择了操作2，那么之后的操作是选择操作1还是操作2已经无所谓了，最后的数组一定是相同的，所以现在问题就转化为我们需要在O(1)的复杂度内求对一个数组进行若干次操作1后得到的数组的值，因为操作次数是m，我们需要枚举在第几次操作是进行的操作2，所以我们枚举复杂度就是O(m),对于每一种情况的求解复杂度必须要小于O(logn)，接下来我会给出一种O(1)的方法求解。

以原始数组为a1,a2,……an为例，进行n次操作1，得到的数组就是2^n个a1,a2,……an前后叠加，我们不妨把每一段这样的区间看成一个单元，那么我们肯定能够很容易求出来一个单元的贡献，这个复杂度是O(n)，不过这样的贡献我们只需要求一次，总的复杂度也不会受到影响。我们来看看相邻两个区间的贡献差是多少？容易发现前一个区间对应的数会比后一个区间对应的数多加了区间长度次，这个很容易发现，前一个区间比后一个区间总贡献就会多区间长度乘以区间和，这样我们就发现其实所有的区间的贡献就是一个等差序列，公差就是区间长度乘以区间和，那么利用这个性质我们就可以O(1)求出来一个区间进行若干次操作1后的贡献，同理我们可以求反转的区间的贡献，最后求一下反转后的数组的贡献，然后把这个数组当成一个单元再求一次进行m-i次操作1后的贡献即可，这样我们就可以枚举所有情况下的贡献了，最后只需要在过程中取一个最大值即可。需要注意的一点就是我们是枚举第几次操作进行操作2，还有一种不进行操作2的情况需要特别判断一下，最后整体取一个最大值即可。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int mod=1e9+7,N=1e5+10;
long long p[N],sum1,sum2,sum;
/*
	sum1存储正序的一段原始区间的贡献
	sum2存储倒序的一段原始区间的贡献
	sum存储原始区间的元素和 
*/ 
long long a[N];
int main(){
	p[0]=1;
	for(int i=1;i<N;i++)
		p[i]=p[i-1]*2%mod;
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum1=(sum1+a[i]*(n-i+1))%mod;
		sum2=(sum2+a[i]*i)%mod;
		sum=(sum+a[i])%mod;
	}
	long long ans=(p[m]*sum1%mod+sum*(p[m]*(p[m]-1)/2%mod)%mod*n%mod)%mod;//先存储一下不反转的情况下对应的贡献 
	for(int i=1;i<=m;i++)//枚举第几次反转 
	{
		long long val1=(p[i-1]*sum1%mod+sum*(p[i-1]*(p[i-1]-1)/2%mod)%mod*n%mod)%mod;
		long long val2=(p[i-1]*sum2%mod+sum*(p[i-1]*(p[i-1]-1)/2%mod)%mod*n%mod)%mod;
		long long val=((val2+sum*p[i-1]%mod*n%mod*p[i-1])%mod+val1)%mod;
		val=(p[m-i]*val%mod+sum*p[i]%mod*(p[m-i]*(p[m-i]-1)/2%mod)%mod*p[i]%mod*n%mod)%mod;
		ans=max(ans,val);
	}
	printf("%lld\n",ans);
	return 0;
}

E. Draw a triangle

题目链接：Problem - E - Codeforces

样例输入： 

3
1 0 1 4
0 1 0 9
0 0 2 2

样例输出：

2 0
1 1
-1 0

题意：在一个二维平面上给出两个格点位置，现在让输出第三个点使得这三个点能够构成一个三角形，而且使得三角形面积尽可能地小，前提是第三个点的位置必须要在格点上，而且三点不能共线。

分析：已经给定了两个点(x1,y1)和(x2,y2)，我们可以求得这两个点的直线方程为

(y2-y1)*x+(x1-x2)*y+(x2-x1)*y-x2*(y2-y1)=0

知道了两个点我们就可以让这两个点形成的边作为三角形的底边，那么剩下的我们就是要求最小的高从而使得三角形的面积最小，也就是求得一个点使得点到这条直线上的距离最小

点(x,y)到这条直线上的距离就是|(y2-y1)*x+(x1-x2)*y+(x2-x1)*y-x2*(y2-y1)|/((y2-y1)^2+(x2-x1)^2)，其中能够发现分母是一个定值，所以我们对分子进行化简可以得到：

|(y2-y1)*(x-x1)+(x1-x2)*(y-y1)|，不妨令y2-y1=a,x1-x2=b,x'=x-x1,y'=y-y1

那么原式就转化为|ax'+by'|，那么由欧几里得我们可以知道对于非负整数a和b，有ax'+by'=gcd(a,b)有解，那么可以知道对于gcd(a,b)就是最小的值，那么我们用扩展欧几里得就可以求出来对应的x'和y'，再分别加上x1和y1就可以求出来原来的x和y，需要特别注意的一点就是一定要保证a和b必须是正数，所以我们可以先用sx和sy记录一下a和b的符号，然后先把a和b变为正数，最后再乘以对应符号即可。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long r=exgcd(b,a%b,x,y);
	long long t=x;
	x=y;
	y=t-a/b*y;
	return r;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		long long x1,x2,y1,y2;
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		if(y1==y2)
		{
			printf("%lld %lld\n",x1,y1+1);
			continue;
		}
		else if(x1==x2)
		{
			printf("%lld %lld\n",x1+1,y1);
			continue;
		}
		long long a=y2-y1,b=x1-x2,c=(x2-x1)*y1-x1*(y2-y1);
		/*
			求ax+by+c绝对值的最小值等价于求解 
			(y2-y1)*x+(x1-x2)*y+(x2-x1)*y1-x1*(y2-y1)的绝对值的最小值
			对上式进行变形可以得到(y2-y1)*(x-x1)+(x1-x2)*(y-y1)的绝对值的最小值
			上式只有(x-x1)和(y-y1)是未知数，不妨设其为新的x和y，系数设置为a和b
			那么就是求解a*x+b*y的最小解，显然是gcd(a,b)，此时对应的x和y只要分别再加上x1和y1即可得到原来的x和y 
		*/
		int sx=1,sy=1;
		if(a<0)
		{
			a=-a;
			sx=-1;
		}
		if(b<0)
		{
			b=-b;
			sy=-1;
		}
		long long x=0,y=0;
		exgcd(a,b,x,y);
		x=x*sx+x1;y=y*sy+y1;
		printf("%lld %lld\n",x,y);
	}
	return 0;
}

M. Youth Finale

题目链接：Problem - M - Codeforces

 样例输入：

5 10
5 4 3 2 1
SSSSRSSSSR

样例输出：

10
6446466400

题意：给定一个n和m，n代表数组长度，m代表操作次数，每次操作我们有两种操作，一种是将整个数组反转，另一种操作是将整个数组循环左移一个单位，每次操作后输出对数组进行冒泡排序所需要的交换次数，注意操作前也需要输出一次。

分析：由于冒泡排序每次都是选择相邻的两个元素进行交换位置，所以每次交换完两个元素后逆序对数量都会减1，直至减为0为止，那么我们就可以知道实质上冒泡排序的交换次数就是数组的逆序对个数，也就是说题意让我们输出每次操作后的逆序对数目。其实对于两种操作要求逆序对数目并不难，首先我们可以用树状数组在O(nlogn)的复杂度内求出原始数组的逆序对数目，然后对于操作1反转，我们其实就是令逆序对从ans变为C(n,2)-ans，因为原来的大小关系全部反转，而且原数组是一个排列，那么不会存在相等的两个元素。对于循环左移一次的逆序对变化也不是很难求，比如最左边的数组是5，n是10，那么这个数右边有4个比他小的，有5个比他大的，由于循环右移后的结果就等价于把这个数组放在最右边，那么原来在其右边的数都变为在其左边，那么也就是说它的逆序对增加的个数就是右边比他大的数的数目，而其逆序对减少的个数就是右边比他小的个数，这样逆序对的变化就可以在O(1)求出来了，关键是我们应该怎么维护数组第一个元素呢？其实这个可以用一个技巧，我们现在数组的真实位置是a[l~r]，那么如果当前元素是正序的话我们就令a[++r]=a[l++]，这样就可以在O(1)的复杂度内对数组进行变换，而如果当前的反转次数为奇数次，那么当前的数组本质上是倒序的，那么其实数组的第一个位置就是a[r]，我们就用a[--l]=a[r--]即可完成数组左移，当前数组是正序还是逆序取决于在此操作之前到底进行了多少次反转操作。所以一开始在数组的读入过程中我们可以给其加一个偏移，这样就可以保证数组不会越界。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e6+10;
int a[N],n,m,c[N];
char s[N];
int lowbit(int x)
{
	return x&-x;
}
void add(int x,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=val;
}
int sum(int x)
{
	int ans=0;
	for(int i=x;i;i-=lowbit(i))
		ans+=c[i];
	return ans; 
}
int main()
{
	scanf("%d%d",&n,&m);
	//将数组向左偏移m位 
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i+m]);
		ans+=i-1-sum(a[i+m]-1);
		add(a[i+m],1);
	}
	scanf("%s",s+1);
	printf("%lld\n",ans);
	int l=1+m,r=n+m,cnt=0;//cnt记录反转次数 
	for(int i=1;i<=m;i++)
	{
		if(s[i]=='R')
		{
			ans=1ll*n*(n-1)/2-ans;
			cnt^=1;
		}
		else
		{
			if(!cnt)//代表当前数组的第一个位置是a[l]
			{
				ans+=n-a[l];
				ans-=a[l]-1;
				a[++r]=a[l++];
			}
			else//代表当前数组的第一个位置是a[r]
			{
				ans+=n-a[r];
				ans-=a[r]-1;
				a[--l]=a[r--];
			} 
		}
		printf("%lld",ans%10);
	}
	return 0; 
}