Codeforces Round 922 (Div. 2) A-C

这次还好，虽然还是不够满意，因为D题没写出来。。
A一个明显的贪心，都竖着放就好了

#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--)
	{
		cout<<(read()*(read()/2))<<endl;
	}
	return 0;
}

B其实可以发现，当你对其中一个数组排序完毕之后，如果要继续调整，那么在排序完的数组里面不管怎么调整都是会使逆序对增加的，
而在另一个数组里面则不一定增加。
而如果我们只考虑相邻交换的排序方式，则可以发现，你每一次交换如果能够让两边同时减少的话，整个的逆序对会变少，如果能保证一遍减少逆序对的话，这次操作肯定是不劣的。
那不就是对其中一个排序就好了

#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 n,a[200001],b[200001],p[200001];
bool mycmp(int x,int y)
{
	return a[x]<a[y];
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();
	while(T--)
	{
		n=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();p[i]=i;
		}
		for(int i=1;i<=n;i++)
		{
			b[i]=read();
		}
		sort(p+1,p+1+n,mycmp);
		for(int i=1;i<=n;i++)
		{
			cout<<a[p[i]]<<' ';
		}
		cout<<endl;
		for(int i=1;i<=n;i++)
		{
			cout<<b[p[i]]<<' '; 
		}
		cout<<endl;
	}
	return 0;
}

C题是一个贪心
对于a,b这两个数字，二进制分解，从高位往低位看
对于两边相同的位置，如果a上的是1，b上的是0，那么他们异或之后肯定是不一样的
如果他们原本就是一样的，那么他们异或之后肯定也是一样的，那异或也没有意义。
所以问题就简化了一点。
我们现在只需要考虑对他们在二进制上不一样的地方进行异或就好。
而如果他们是不一样的，同时对他们的这个位置异或1，其实结果就是同时取反。
我们要做的是让这个异或后的结果尽可能的小，那就是让大的变小，小的变大。
那其实就能贪心了，因为这个是二进制的表示，如果一个数字的高位是1的话，那不管另一个数字低位怎么折腾，这个数字总是更大。
所以其实可以用一个遍历，把这个两个数字从高位到地位一个一个比较下来，如果大的数字的某一位是1而小的数字的这一位是0 的话，就让他们同时在这一位异或上1。
每一位都这么做就好了。
然后对于r的限制，就判断一下他们同时异或的数字在加上这一位的时候会不会大于r就好了。
哦，还有一个特判，因为可能把r二进制分解之后，我们的答案如果在最高位取了1，会大于r，但是如果这一位不取1可能在后面可以产生更优的答案，所以就做两遍，然后其中一遍在第一个能取的地方选择不取就好了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
	char c=getchar();ll a=0,b=1LL;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1LL;
	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);
	ll T=read();
	while(T--)
	{
		ll na=read(),nb=read(),r=read(),ans=0;bool flag=0;
		if(na<nb)swap(na,nb);ll a=na,b=nb;
		for(ll i=62;i>=0;i--)
		{
			ll c1LL=(na>>i)&1LL;
			ll c2=(nb>>i)&1LL;
//			cout<<c1LL<<' '<<c2<<' '<<na<<' '<<nb<<' '<<i<<endl;	
			if(c1LL!=c2)
			{
				if(flag==0)
				{
					flag=1LL;continue;
				}
				if(c1LL==1LL&&c2==0)
				{
					if((ans+(1LL<<i))<=r)
					{
						ans+=(1LL<<i);
//						cout<<i<<endl;
						na^=(1LL<<i),nb^=(1LL<<i);
//						cout<<na<<' '<<nb<<endl;
						if(na<nb)swap(na,nb);
					}
				}
			}
		}
		ll fans=ans;
		ans=0;
		for(ll i=62;i>=0;i--)
		{
			ll c1LL=(na>>i)&1LL;
			ll c2=(nb>>i)&1LL;
//			cout<<c1LL<<' '<<c2<<' '<<na<<' '<<nb<<' '<<i<<endl;
			if(c1LL!=c2)
			{
				if(c1LL==1LL&&c2==0)
				{
					if((ans+(1LL<<i))<=r)
					{
						ans+=(1LL<<i);
//						cout<<i<<endl;
						na^=(1LL<<i),nb^=(1LL<<i);
//						cout<<na<<' '<<nb<<endl;
						if(na<nb)swap(na,nb);
					}
				}
			}
		}
//		cout<<ans<<endl;
		cout<<min(abs((a^ans)-(b^ans)),abs((a^fans)-(b^fans)))<<endl;
	}
	return 0;
}

D题的话，我第一个想的是dp，但是状态根本不好设计，因为有一维是bi，那也就是同时要记录abi的和以及最大的连续a[i]的和
草，那就记下来就好了啊，我tm好像会了。
额又不会了，我转移的时候要怎么选择最优转移呢？不就只能全部记下来，然后在结果的地方比较了吗。
难绷。
我写的时候想的是二分答案，然后二分答案明显是不可以的，cf上面第二个样例就是反例。

（所以想到这里我就洗洗澡睡觉去了