HDU5269 – ZYB loves Xor I(字典树)

题目链接:HDU5269

【题意】

【分析】容易得到两个数a,b异或后lowbit的值就是当a,b的最低p-1位相同,lowbit值为2^p;比赛的时候想从左往右把每一位上出现过的0的次数和1的次数用sum[29][2]记下来,然后处理到a[i]时,a[i]和a[1~i-1]的所有lowbit之和为它的每一位值p:f[i]*sum[i][p^1]之和;可是这样一个数可能会被计算多次,怎样让每个数只计算一次且是最低位的那次;比赛中就一直卡住了;其实可以用字典树低位到高位插入,每次都插29位,插入的时候累加每个f[i]*sum[ch[i][p^1]]即可。

【AC CODE】93ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, MOD = 998244353;
int ch[35*MAXN][2], sum[35*MAXN], cnt, ans;
int newnode()
{
	ch[cnt][0] = ch[cnt][1] = -1;
	sum[cnt++] = 0;
	return cnt-1;
}
void insert(int u, int v)
{
	rep(i,0,29)
	{
		int p = (bool)(v&(1<<i));
		if(~ch[u][p^1])
			ans = (ans+(LL)(1<<(i+1))*sum[ch[u][p^1]]%MOD)%MOD;
		if(-1 == ch[u][p]) ch[u][p] = newnode();
		sum[u]++;
		u = ch[u][p];
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t,count = 0;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n;
		scanf("%d%*c", &n);
		cnt = ans = 0;
		int root = newnode();
		rep(i,0,n)
		{
			int a;
			scanf("%d", &a);
			insert(root,a);
		}
		printf("Case #%d: %d\n", ++count,ans);
	}
	return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

请输入正确的验证码