前言
本题解采用折半搜索算法完成，对于不打算用这种方法的同学，这篇题解可能会浪费你人生中宝贵的十几分钟。
思路
此题似乎找不出什么好的性质，那么考虑暴力。
发现 \(x,a\) 都在 \(2^{30}\) 内，直接枚举必然无法承受，怎么办？折半！
我们把 \(x,a_i\) 劈成两半，一半为前 \(15\) 位，一半为后 \(15\) 位，分别暴力计算。
令 \(c_i\) 表示 \(a_i \oplus x\) 得到的数的前 \(15\) 位的 \(1\) 的个数（前 \(15\) 位，指：从高往低数前 \(15\) 位）；
令 \(d_i\) 表示 \(a_i \oplus x\) 得到的数的后 \(15\) 位的 \(1\) 的个数（后 \(15\) 位，指：从低往高数前 \(15\) 位）。
那么 \(c_i + d_i\) 就表示 \(a_i \oplus x\) 得到的数在二进制表示下 \(1\) 的个数，题目要求所有的 \(c_i + d_i\) 必须相等，那么我们可以列出必须满足的式子：\(c_i + d_i = c_{i-1} + d_{i-1},\ 2 \le i \le n\)。
你会发现这个式子没有简单的判定方法，那考虑把式子换一种形式，既然要保证所有的 \(c_i + d_i\) 相等，那么只要满足 \(c_i + d_i = c_1 + d_1\) 就可以了。
貌似有一些思路，但是还没有复杂度较低的判定方法，那就再把式子换一种形式：\(c_i - c_1 = d_1 - d_i\)，这样就可做了。
实现
我们求 \(c\) 数组的时候把每一个 \(x\) 所对应的所有 \(c_i - c_1\) 存下来。求 \(d\) 数组的时候，把所有 \(d_1 - d_i\) 存下来。
如果某一个 \(x\)，与其对应的 \(c_i - c_1\) 和 \(d_1 - d_1\) 每一项都相等，那么就满足条件了，输出即可。
插曲
如何快速地求一个数在二进制下的 \(1\) 的个数？先上代码~
int get_cnt(int val)
{
int res = 0;
while (val) val &= val - 1, res ++ ;
return res;
}
我们举个例子来看一看
总的来说 \(x-1\) 相当于是把 \(x\) 在二进制表示下最靠后的 \(1\) 以及这个 \(1\) 后面的所有 \(0\) 按位取反，得到的数再与上 \(x\) 相当于把最靠后的 \(1\) 消去了。
Code
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
const int N = 110;
const int Mo = (1 << 15) - 1;
int n;
int a[N];
map<vector<int>, int> mp;
int get_cnt(int val)
{
int res = 0;
while (val) val &= val - 1, res ++ ;
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int x = 0; x < (1 << 15); x ++ )
{
int c1 = get_cnt((a[1] >> 15) ^ x);
vector<int> vec;
for (int i = 2; i <= n; i ++ ) vec.push_back(get_cnt((a[i] >> 15) ^ x) - c1);
mp[vec] = x;
}
for (int x = 0; x < (1 << 15); x ++ )
{
int d1 = get_cnt((a[1] & Mo) ^ x);
vector<int> nw;
for (int i = 2; i <= n; i ++ ) nw.push_back(d1 - get_cnt((a[i] & Mo) ^ x));
if (mp.count(nw))
{
cout << (mp[nw] << 15) + x << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
完结撒花
这是我折半搜索第一次学明白的题了，也是我第一道灰题！收~
标签：Them,洛谷,val,int,题解,res,15,include,式子 From： https://www.cnblogs.com/LittleMoMol-kawayi/p/LuoGu_solution_CF1257F.html