求数列中两数异或合最大值最富有的人 trie树贪心

呃.... 我这个人 ... 看到好东西就想转.....

Description

　　你经过了一段时间的打工，老板带你来到了他的私人金库。在你的面前有n堆金子，老板要求你只能选择其中的两堆，而你的工资为这两堆金子价值的xor值，你想成为最富有的人，你就要做出最优的选择。

 

Input

第一行包含一个正整数t，表示有t组数据。 每组数据的第一行包含两个正整数n，表示有n堆金子； 第二行包含n个正整数，表示每堆金子的价值。

Output

对于每组数据用一行输出。 每行包含一个正整数，表示能获得的最大工资。

Sample Input

2 5 1 2 3 4 5 10 1 2 3 4 5 6 7 8 9 10

Sample Output

7 15

HINT

数据范围：

t<=10 2<=n<=100000 每堆金子数<=2^31-1

 

这题好玄学啊一看就是数论题对不对… 不对.本题的正解是踹树大法.将数字转成二进制,从最高位(第31位)开始往树里扔;然后枚举每个数,在trie树中寻找一条跟它异或值最大的路径更新答案.寻找这条路径只需要非常简单的贪心思想:由于是从最高位开始比较的,所以尽可能满足当前枚举到的一位不同,如果只能相同就只能认怂了…

这种贪心思想源于XOR运算的性质:10000^00000<10000^01111.理解了这个性质,本题自然迎刃而解.

转载传送门

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 999983 using namespace std; int n,m; long long dp[110][110][110];//dp[i][j][k]表示前i行有j列放了1個砲,k列放了2個砲的方案數. long long ans; int main() { cin>>n>>m; dp[0][0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<=m;k++) { dp[i][j][k]=dp[i-1][j][k]; if(j)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-j-k+1))%MOD; if(k)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%MOD; if(j>=2)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*(m-j-k+1)*(m-j-k+2)/2)%MOD; if(j&&k)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*(m-j-k+1)*j)%MOD; if(k>=2)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*(j+2)*(j+1)/2)%MOD; } } } for(int i=0;i<=m;i++) { for(int j=0;j<=m;j++)ans=(ans+dp[n][i][j])%MOD; } printf("%lld",ans); return 0; }