CF1285D Dr. Evil Underscores

挂个链接

Description：

给你 \(n\) 个数 \(a_1,a_2,……,a_n\) ，让你找出一个 \(x\) ，使 \(x\) 分别异或每一个数后得到的 \(n\) 个结果的最大值最小。

Solution：

设 \(x\) 为题中所说， \(m\) 为 \(max{x^a_i}\) :

构建 \(01Trie\) ,将所有数的二进制形式存到 \(01Trie\) 上，对于第 \(k\) 位，存在两种情况：

一是都是0或都是1，这样只要使 \(x\) 的第 \(k\) 位为1或0，就可以使 \(m\) 的第k位为0.根据贪心的策略，高位为0的数一定比高位为1的数小，不管低位怎样。
二是这一位0和1都有，那么分开dfs，取最大值。这种情况不太好理解，具体可以见代码。

Code:

我没有建 \(Trie\) ，而是直接dfs。

\(dfs(v[],k)\) 表示 \(v\) 中的数的最小的 \(m\) ，并且已经搜到第 \(k\) 位了。（锹黑板,划重点！！！



#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 1e5+1;

ll n,ans;

ll dfs(vector<ll> v,ll k)

{

	vector<ll> v1,v2;

	if(k<0) return 0;

	for(int i=0;i<v.size();++i)

	{

		if((v[i]>>k)&1) v1.push_back(v[i]);

		else v2.push_back(v[i]);

	}

	if(v1.empty()||v2.empty()) return dfs(v,k-1);//01Trie 只有一个分支

	ll d1=dfs(v1,k-1),d2=dfs(v2,k-1);

	return min(max(d1,d2+(1<<k)),max(d1+(1<<k),d2));//有两个分支

}

int main()

{

	vector<ll> v;

	scanf("%lld",&n);

	while(n--)

	{

		ll tmp;scanf("%lld",&tmp);

		v.push_back(tmp);

	}

	printf("%lld\n",dfs(v,30));

	return 0;

}

巴特西

CF1285D Dr. Evil Underscores

挂个链接

Description：

Solution：

Code:

最新文章

热门文章