2022.1.24 学习总结

2022.1.24 学习总结

今天做了两道周测补题，分别是周测一的Make Them Equal - 洛谷 和 周测二的[B2] Alice Wins! (hard version) - 洛谷                                                                                      

记单词一个小时

在b站上看c++的视频两个小时

题目：
Make Them Equal - 洛谷

 由题意分析可知，要使序列中所有元素经过 *** 作后全部相等，同时我们可以发现 *** 作前后序列总和不变，那么我们就可以想到这题最后应该是得到一串相同数的序列，这个数值就应该是这个序列的平均数

 所以我们就有了一个确定的目标：使每个数等于这个序列的平均数

为了达到这个目标，我们需要先有一个数来存储序列的总和

这里根据题目给出的公式：
ai'=ai-x*i;

aj'=aj+x*i;

发现当 i = 1 时考虑较为简单，那么就把序列中的其它数字全部累积在a[1]上，最后再一 一分配平均到每个元素上

而因为某个元素的数字要转移到另一个元素上时需要经过上面的公式来进行，为了防止转移过程中数字出现变化，我们先将每个元素上的数字变为 i （当前位置）的整数倍，再将其转移到a[1]上，完成这些就可以分配平均数了。

#include
int n,t,sum,b[200010],a[200010];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int i,j,k;
		scanf("%d",&n);
		sum=0;
		for(i=0;i<=n;i++)
		{
			a[i]=0;
			b[i]=0;
		}
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			b[i]=a[i]%i;//这里是方便后面转移到a【1】，保证*i等于原数，保证后续得到的a[i]为i的倍数 
		}
		if( sum/n != 1.0*sum/n )//判断得到的平均数是否为整数，若不是，则无法使序列中每个元素相同 
		{
			printf("-1n");
			continue;
		}
		printf("%dn",3*(n-1));
		for(i=2;i<=n;i++)
		{
			printf("1 %d %dn",i,(i-b[i])%i);//使a[i]是i的整数倍，这里算操作(n-1)次 
			if( a[i] % i != 0 )//当a[i]不是i的整数倍时进行此操作，是整数倍的话操作前后数据不变 
			{
				a[1]-=((i-b[i])%i)*1;//此时i=1 ,提前将余数加到a[1]里面，不然后面无法得到预期的平均数 
				a[i]+=((i-b[i])%i)*1;//这里a[i]-余数后，即此时a[i]为i的整数倍 
			}
			printf("%d 1 %dn",i,a[i]/i);//把a[i]转移到a[1]上，这里算操作(n-1)次  
			a[1]=a[1]+a[i];
			a[i]=0;
		}
		for(i=2;i<=n;i++)
		{
			printf("1 %d %dn",i,sum/n);//将a[1]的值平均分给每个a[i],这里算操作(n-1)次,共3*（n-1）次操作 
			a[1]-=sum/n;
			a[i]=sum/n;
		}
	}
	return 0;
}

题目：

[B2] Alice Wins! (hard version) - 洛谷

这题和前面一道题（[B1] Alice Wins! (easy version) - 洛谷）很相似，只是前面那题要求“最多可以改变每队n个人的方案”，这题是“必须改变每队n个人的方案”。

也很简单，输入完数据后先整体判断当前A有几组获胜的情况，若获胜数不等于n，就修改方案至

获胜数刚好等于n,而获胜数等于n时，则将“未获胜的情况修改成另一种未获胜的情况”,保证修改次数等于n就好了，最后再对B队进行修改，此时的B队不用更多的考虑，因为所有情况已经在考虑A队时同时解决了。

#include
int a[200010],b[200010],book[200010],t;
int main() {
	scanf("%d",&t);
	while(t--) {
		int i,j,n,sum1=0,kk=0;
		scanf("%d",&n);
		for(i=1; i<=2*n; i++)
			scanf("%d",&a[i]);
		for(i=1; i<=2*n; i++)
			scanf("%d",&b[i]);
		i=1;
		for(i=1; i<=2*n; i++)
			if((a[i] == 1 && b[i] == 2) || (a[i] == 2 && b[i] == 3) || (a[i] == 3 && b[i] == 1)) {
				book[i]=1;
				sum1++;
			}
//	printf("sum1=%dn",sum1);
		for(i=1; i<=2*n; i++) { // A
			if(kk == n || sum1 == n)
				break;
			if( sum1 < n && book[i] == 0) { //把错的改对，至正确数为n
				book[i]=1;
				if (b[i] == 1)
					a[i]=3;
				else if (b[i] == 2)
					a[i]=1;
				else if (b[i] == 3)
					a[i]=2;
				sum1++;
				kk++;
			}//kk记录操作次数
			if( sum1 > n && book[i] == 1 ) { //把对的改错，至正确数为n
				book[i] = -1;//标记，防止对同一个数进行二次改动
				if (b[i] == 1)
					a[i]=1;
				else if (b[i] == 2)
					a[i]=2;
				else if (b[i] == 3)
					a[i]=3;
				sum1--;
				kk++;
			}
		}
		for(i=1; i<=2*n; i++) {
			if(kk == n)
				break;
			if(sum1 == n && book[i] == 0) { //把错的改成错的，不影响正确数
				if(a[i] == 1 && b[i] == 1)
					a[i]=2;
				else if(a[i] == 2 && b[i] == 1)
					a[i]=1;
				if(a[i] == 3 && b[i] == 2)
					a[i]=2;
				else if(a[i] == 2 && b[i] == 2)
					a[i]=3;
				if(a[i] == 3 && b[i] == 3)
					a[i]=1;
				else if(a[i] == 1 && b[i] == 3)
					a[i]=3;
				kk++;
			}
		}
		for(i=1; i<=2*n; i++) { //把错的改对   B
			if(book[i] == 1)
				continue;
			if (a[i] == 1)
				b[i]=2;
			else if (a[i] == 2)
				b[i]=3;
			else if (a[i] == 3)
				b[i]=1;
		}
		printf("%dn",2*n);
		for(i=1; i<=2*n; i++)
			printf("%d ",a[i]);
		printf("n");
		for(i=1; i<=2*n; i++)
			printf("%d ",b[i]);
		printf("n");
		for(i=1; i<=2*n; i++)
			book[i]=0;
	}
	return 0;
}

另外，我还做了一下周测二的最后一道补题（Alice and Bob are playing a Normal Game - 洛谷），花了不少时间，但是没整出来。。