Educational Codeforces Round 158 (Rated for Div. 2) C

链接

一个为了1300的题目而写的总结。挺可怕的。

赛时写了一个按位贪心，但是假了。我现在就是不知道，如果做法想假了，wa on test2到底要怎么来判断。我找不到反例，那就只能坐着等死。真的太难受了。要是做题能不能做对全看的想到的第一个做法对不对，和他有没有错在一些很离谱的地方，这我玩jb啊 。

反例其实也简单，但是我根本没有头绪，完全没法找。因为我根本就不觉得是我代码的问题，如果是我代码的问题的话，为什么我找不到反例？而我不觉得我代码有问题，我更是没有去找反例的需求，找的话也只是随机构造，能找到的概率微乎其微。

这就是一个死局啊，除非我能够感觉到我的做法有问题，不然就没办法了。
真的是不知道怎么办。这个题目我也不觉得是很简单的题目。但是它标着1300。我做它的时候的思维量根本就不是1300的题。至少1800。

要会这个题，首先要直接理解除2下取整的含义，就是删去二进制位的最后一个。然后这里有第一个贪心。我们每次操作都是让所有数字之间的差距变小，所以当我们用这些操作使得最大的数和最小的数字相等的时候，其他中间的数字也必然相等。

就这个贪心就不是1300的题目了吧。。。。。

然后第二个，当对最大数字和最小数字操作的时候，尽可能的让最小的数字被删去的最后一位是0。这样做是不劣的。这个其实就是让最小的尽可能变大，而最大的尽可能变小。可以发现，这样子操作并不会让最小的和最大的数字错过。因为其实变化量只有1。

这个贪心更是nmd无厘头。我是没有在题目里面的任何这个的启发性。。。这题标1300。。。是什么意思。

所以我们的操作就是，如果大的数字二进制末尾是0，小的是1，那这次操作就让x=1，否则让x=0

然后重复，直到相等。

这个题目，一方面你要从二进制的角度考虑，另一方面，第一个贪心又是纯纯的从数字之间的大小关系考虑。本身是一个很好的题目，但是表1300我只感觉我被嘲讽了。

真是做的我脑溢血。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char c=getchar();int a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();
	while(T--)
	{
		int n=read();
		int Minn=0x3f3f3f3f,Maxx=0;
		for(int i=1;i<=n;i++)
		{
			int x=read();
			Minn=min(Minn,x);
			Maxx=max(Maxx,x);
		}
		vector<int> ans;
		while(Minn!=Maxx)
		{
			int a=Minn&1,b=Maxx&1;
			if(a==1&&b==0)
			{
				ans.push_back(1);
				Minn++;
			}
			else
			{
				ans.push_back(0);
			}
			Minn>>=1;
			Maxx>>=1;
		}
		cout<<ans.size()<<endl;
		if(ans.size()<=n&&ans.size()!=0)
		{
			for(int i=0;i<ans.size();i++)
			{
				cout<<ans[i]<<' ';
			}
			cout<<endl;
		}
	}
	return 0;
}

但是，还是要总结的。
这题的难点就在于要从大小和二进制的两个方向考虑，分别得到结论，同时还要进行验证。
而且这个结论的正确性不明显。所以是要经过一定的考虑得到的。

所以我tmd还是不理解给这题标个1300，1400是几个意思。

哦不对，我知道为什么我做不出来了。我对下取整的思考不够，下取整每次能够造成的影响我没有好好考虑。这是我之前总结过的，但是我又犯了这个错。