Codeforces Round 896 (Div. 2)补题

Make It Zero（Problem - A - Codeforces）

题目大意：有一个数组a[],我们每次可以选定一个区间，求区间内的异或和s，然后将区间中的数全部改成s,最后要使所有元素都变成0，问需要操作多少次，每次选的区间是是什么。（不要求最优解）

思路：我们可以发现，如果选定一个偶数长度的区间，这个区间的异或和如果不为0，那么再选它一次就够了基于这个性质来求解，一定要记住偶数个相同的非0数的异或值才为0，奇数个是不可以的。而且这个题没说最小，所以一个区间即使为0了同样可以再选它。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
		}
		if(n%2==0)
		{
			printf("2\n");
			printf("1 %d\n",n);
			printf("1 %d\n",n);
		}
		else
		{
			printf("4\n");
			printf("1 %d\n",n-1);
			printf("1 %d\n",n-1);
			printf("2 %d\n",n);
			printf("2 %d\n",n);
		}
	}
}

2D Traveling（Problem - B - Codeforces）

题目大意：有n个城市，其中k个城市是主要城市，主要城市之间通航免费，其余城市之间通行的费用是两个城市坐标的曼哈顿距离，现在要从城市a到城市b，问最少花费。

思路：如果要经过主要城市那肯定是两者都到离它最近的主要城市去，然后免费飞一次，如果不转直接飞就算一下曼哈顿距离，比较一下谁更小即可。另外两个城市之间曼哈顿距离的最大值是4e9，最小值初始化的时候要注意一下。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n,k,a,b;
		scanf("%lld%lld%lld%lld",&n,&k,&a,&b);
		vector<pair<int,int>>p;
		int x1,y1,x2,y2;
		for(int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			if(i<=k) p.push_back({x,y});
			if(i==a) x1=x,y1=y;
			if(i==b) x2=x,y2=y;
		}
		int mi1=4e9,mi2=4e9;
		for(int i=0;i<p.size();i++)
		{
			int x=p[i].first,y=p[i].second;
			int d1=abs(x1-x)+abs(y1-y);
			int d2=abs(x2-x)+abs(y2-y);
			mi1=min(mi1,d1);
			mi2=min(mi2,d2);
		}
		int ans=abs(x1-x2)+abs(y1-y2);
		ans = min(ans,mi1+mi2);
		cout<<ans<<endl;
	}
}

Fill in the Matrix（Problem - C - Codeforces）

题目大意：现有一个为空的n行m列的矩阵，要求往矩阵中填数，每一行都是一个排列，然后求每一列的mex,然后再求所有列mex的mex，最后需要输出矩阵和最终mex的值。

思路：这道题求mex的过程实际很简单，很容易发现，m>n的时候，mex的值就取决于行数，有多少行就有多少个0，那么我们就可以将这些0，尽可能地分散，那么就可以产生0-n这么多个mex值，最后总的mex就是n+1,如果m<=n，那么我们可以将m个数尽可能地分散，那么就前m-1行尽可能分散，后面地每一列都填一样的数,而且与第m-1行相同，那么m列就可以产生0-m-1个mex值，最后的结果就是m。当然有一个特例，m=1的时候，我们只有数字0可以填，那么这一列的mex是1，最后结果的mex是0。然后关于尽可能打散的问题，我们只要按照锯齿形来填相同的数即可，那么锯齿形其实横纵坐标是有规律的。如下图就是一种赋值方式：

当然还有别的赋值方式，只要保证全部打散即可，为了防止每一列所有的值都有，我们在适当的时候将每一列后面所有值全部统一。

但是由于这道题的数据范围比较特殊，建数组不太好建，所以最好找到规律逐行输出。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		if(m==1) printf("0\n");
		else if(n<m) printf("%d\n",n+1);
		else printf("%d\n",m);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cout<<(j+min(i,m-1)-1)%m<<" ";
			}
			cout<<endl;
		}
	}
}

Candy Party (Easy Version)（Problem - D1 - Codeforces）

题目大意：现在有n个人，每人手里有若干个糖果，每人只能也必须进行一次操作：就是挑选一个人，送出2^x个糖果，当然这个2^x需要小于它手里送出前的糖果数（因为它可以先收再送），要求，每个人必须且只能送出一次糖果，同时也必须且只能收到一次糖果，最后所有人的糖果数量要相同，问是否可以实现。

思路：首先这里的2^x就很明显提示我们要从二进制的角度考虑，然后我们来思考，每个人既要送出又要获得，那么最后净变化是多少。很显然就是从目前的数量到它们的平均数，如果平均数非正数，那么显然不能成立。然后我们算出每个人的净变化了就要从这里入手，假设净变化的绝对值是d，那么它送出2^x个，获得2^y，个它们之间差的绝对值要等于净变化的绝对值。我们从二进制的角度来看这个减法，

1000000

0000010

相减：
0111110

所以如果可以通过减法得到，那么就找出最高位1的位置c，和最低位1的位置l

2^(c+1)-2^l就可得到。

那么我们就对差值d进行c和l的查找，如果找的的值相减之后不等于d，就说明d没办法得到，是无效值，否则就记录这两个值，我们用一个数组来记录需要给出的值，一个数组记录需要获得的值，两个数组排序后相等就说明可以成立，否则就不可以。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
int b[70];
signed main()
{
	b[1]=1;
	for(int i=2;i<=60;i++) b[i]=b[i-1]*2;
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n;
		scanf("%lld",&n);
		int sum=0;
		for(int i=0;i<n;i++)
		{
			int x;

			scanf("%lld",&x);
			a[i]=x;
			sum += x;
		}
		if(sum%n==0) 
		{
			int avg=sum/n;
			vector<int>g,s;
			int flag=1;
			for(int i=0;i<n;i++)
			{
				int d=abs(a[i]-avg);
				int tmp=a[i]-avg;
				int c=0,l=-1;
				while(d)
				{
					c++;
					if(l==-1&&d%2) l=c;
					d/=2;
				}//中间有0的情况没判断
				if(b[c]==abs(tmp))
				{
					if(tmp>0)//多给少收
					{
						g.push_back(c);
						s.push_back(0);
					}
					else if(tmp<0)
					{
						g.push_back(0);
						s.push_back(c);
					}
				}
				else
				{
					if(tmp&&b[c+1]-b[l]!=abs(tmp)) 
					{
						flag=0;
						break;
					}
					if(tmp>0)//多给少收
					{
						g.push_back(c+1);
						s.push_back(l);
					}
					else if(tmp<0)
					{
						g.push_back(l);
						s.push_back(c+1);
					}
				}
			}
			if(flag==0) printf("NO\n");
			else
			{
				sort(g.begin(),g.end());
				sort(s.begin(),s.end());
				if(g==s) printf("YES\n");
				else printf("NO\n");
			}
		}
		else printf("NO\n");
	}
}

?显然这么写还是略显麻烦，首先那个预处理实际上可以用位运算替代，位运算的时间复杂度是O（1）所以我们甚至不用这么写，直接写个嵌套循环去找c+1和l，如果能找到就记录，如果找不到直接判否即可。另外由于两个数组相等的性质，我们可以直接对对应位进行标识，如下

for(int k=0;k<n;k++)
{
	for(int i=31;i>=0;i--)
	{
		for(int j=31;j>=0;j--)
		{
			if(a[k]+(1<<i)-(1<<j)==avg)
			{
				d[i]++;
				d[j]--;
			}
		}
	}
}
int flag=1;
for(int i=31;i>=0;i--)
{
	if(d[i])
	{
		flag=0;
		break;
	}
}
if(flag) printf("YES\n");
else printf("NO\n");

这样简单很多。

Candy Party (Hard Version)（https://codeforces.com/contest/1869/problem/D2）

题目大意：与上面大差不差，就是现在每个人最多只能给出一次，最多只能获得一次，其余的条件没有区别。

思路：这里其实真的区别不大，只不过那些差值恰好是2的幂的数多了一种选择而已。所以我们可以首先将它们全部记成不拆解，然后当不够的时候再拆解它们来补充，并不用关心每个数具体拆不拆。然后问题就解决了，但是代码部分有点麻烦。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p1[100],p2[100],b[100],a[200010];
signed main()
{
	int t;
	scanf("%lld",&t);
	
	while(t--)
	{
		int n;
		int sum=0;
		scanf("%lld",&n);
		for(int i=0;i<=34;i++) p1[i]=0,p2[i]=0,b[i]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			sum += a[i];
		}
		if(sum%n) 
		{
			printf("NO\n");
			continue;
		}
		sum /= n;
		int flag=1;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==sum) continue;
			int st=0;
			for(int j=31;j>=0;j--)
			{
				if(a[i]-(1<<j)==sum)//给出
				{
					p1[j]++;
					st=1;
					break;
				}
				if(a[i]+(1<<j)==sum)//获得
				{
					p2[j]++;
					st=1;
					break;
				}
			}
			if(st) continue;
			for(int j=31;j>=0;j--)
			{
				for(int k=31;k>=0;k--)
				{
					if(a[i]+(1<<j)-(1<<k)==sum)//-是获得，+是给出，因为给出的可以给后面
					{
						b[j]--;
						b[k]++;
						st=1;
						break;
					}
				}
			}
			if(!st) 
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			printf("NO\n");
			continue;
		}
		int st=1;
		for(int i=31;i>=0;i--)
		{
			b[i] += p1[i]-p2[i];//剩余可以给出的。
			if(b[i]==0) continue;
			if(b[i]>0)//可以给出的有剩余，能补给下一位
			{
				//实际就是将一部分需要获得2^(i-1)的拆成获得2^i,给出2^(i-1)
				//那就是直接被用作获得2^(i-1)的部分变少了，减少的个数刚好是b[i]
				//同时它给出一部分2^[i-1],那么这个相当于变多了
				p2[i-1] -=  b[i];
				b[i-1] += b[i];
				if(p2[i-1]<0)//如果能被拿来用的不够
				{
					st=0;
					break;
				}
			}
			else//b[i]为负，则需要活得，那么就要拆一部分需要给出的2^(i-1)
			{
				//将一部分需要给出的2^(i-1)变成获得2^(i-1),给出2^i
				//那么直接用于给出的2^(i-1)变少，
				//需求的2^(i-1)变多，b中的2^(i-1)应该变少
				p1[i-1] -= -b[i];
				b[i-1] -= -b[i];
				if(p1[i-1]<0)
				{
					st=0;
					break;
				}
			}
		}
		if(st) printf("YES\n");
		else printf("NO\n");
	}
}