[刷题笔记] 异或

Problem

给定一个包含 \(n\) 个数的可重集，每个数为 0 或 1 ，初始时答案变量 \(ans=0\) 。
你需要进行 \(n-1\) 次操作，每次操作进行如下：

1. 选取可重集中的两个数 \(x,y\) ，并计算出 \(z=x \operatorname{xor} y\) 。
2. 将 \(ans\) 增加 \(z\) 。
3. 在可重集中删除 \(x,y\) ，并加入 \(z\) 。

显然，最终可重集只会剩下一个数。

请求出操作结束后能够获得的最大的 \(ans\) 值为多少。

解释：\(\operatorname{xor}\) 表示异或，在 C++ 中运算符为 ^，异或结果的二进制某一位为 1 当且仅当参与运算的两个数在这位不同。（\(0\operatorname{xor}0=1\operatorname{xor}1=0,\ \ 0\operatorname{xor}1=1\operatorname{xor}0=1\)）
对于 \(10\%\) 的数据，\(n=2\) 。

对于 \(30\%\) 的数据，\(n\leq 10\) 。

对于 \(50\%\) 的数据，\(n\leq 300\) 。

对于 \(70\%\) 的数据，\(n\leq 10^6\) 。

对于 \(100\%\) 的数据，\(T\leq 10,2\leq n\leq 10^{18}\) 。

Description

题目描述非常明了，不做说明。

Solution

一看数据1e18。结论题。

我们发现，只是给定了0和1的个数，并没有告诉你具体序列如何，考虑构造。

那么如何构造使得 \(ans\)最大呢？

首先特判如果没有1则无论如何构造都不可能出现1，输出0即可。

接下来显然需要尽可能的使0和1配对，因为0&1=1。设有\(k\)个0，\(k\)个1，那么这样的构造显然能凑出\(k\)对01，也就是会给ans贡献\(k\)
为什么一定能凑出\(k\)对01呢？若1的数量少于0的数量怎么办！

举个例子：
0001
我们合并01，变成1，然后继续合并01......显然由于\(0 xor 1 = 1\),哪怕1的数量少于0也可以凑出。

对于这样的构造我们会消去所有的0，原来有多少1现在还有多少1。

接下来考虑如何抵消1。

最后消完会剩下一个1，剩下的都变成0即可，因此一共会给答案贡献\((k-1)/2\)

还有，记得开long long

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll T;
int main()
{
	scanf("%lld",&T); 
	while(T--)
	{
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if(b == 0) cout<<"0"<<endl;
		else cout<<a+(b-1)/2<<endl;	
	}	
	return 0;
}