专栏文章

题解：AT_abc425_g [ABC425G] Sum of Min of XOR

ccodwarm
AT_abc425_g题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minqjxrx
此快照首次捕获于
2025/12/02 06:43
3 个月前
此快照最后确认于
2025/12/02 06:43
3 个月前
查看原文

G - Sum of Min of XOR

自己想的一个比较不同的做法。
好写好理解。00 观察。00 注意力。

题意

令 m=M−1m = M - 1。
求 ∑x=0mmin⁡1≤i≤N(x⊕ai)\displaystyle \sum_{x=0}^{m} \min_{1\le i\le N} \left(x\oplus a_i \right)。
M,ai≤109,N≤2×105M,a_i \le 10 ^ 9,N \le 2\times10^5。

做法

若 mm 比较小，则可以建 trie 树，遍历 00 到 mm，从高位到低位，每次能往相同的走就尽量走。
不能的话则第 ii 位会为答案增加一个 2i2^i 的贡献。
这启发我们去计算 trie 每一个树上的节点产生了多少贡献。
即大概是求一个节点会被多少个数走到，然后有多少个数会向 0/10/1 走。
但这似乎有点困难。
因为走到一个节点上的数是多个区间。
还有 mm 的限制，这导致了一个节点向 0/10/1 走的数的个数还不一样。
想想看，如果 m=2k−1m=2^k-1，那么可以保证的是 trie 树上任何一个节点
向 0/10/1 走的数个数都是一样的。
在 dfs 的过程中维护当前位和走到当前节点的数的个数即可。
容易想到我们可以把 [0,m][0,m] 拆成若干个长度为 2k2^k 的区间来做。
具体来说，就是先找到一个极大的区间 [0,2k−1][0,2^k-1]，然后继续去拆 [2k,m][2^k,m]。
对于一个 [x,x+2k−1][x,x + 2^k-1] 的区间，我们可以先在 trie 树上找到他们共同的父亲，然后再跑 dfs。
这样就等价于 m=2k−1m=2^k-1 的问题了。
CPP
int n,m,a[N];
int son[N * 32][2],tot;
void insert(int x)
{
	int p = 0;
	for (int j = 30;j >= 0;j--)
	{
		int ch = (x >> j & 1);
		if (!son[p][ch]) son[p][ch] = ++tot;
		p = son[p][ch];
	}
}
ll ans = 0;
void solve(int x,int w,int cnt)
{
	if (!son[x][0] && !son[x][1]) return;
	if (son[x][0] && son[x][1])
	{
		solve(son[x][0],w-1,cnt/2);
		solve(son[x][1],w-1,cnt/2);
	}
	else if (son[x][0])
	{
		ans += ((1ll<<w) * cnt / 2);
		solve(son[x][0],w-1,cnt);	
	}
	else{
		ans += ((1ll<<w) * cnt / 2);
		solve(son[x][1],w-1,cnt);
	}
}

void solvemain()
{
	cin >> n >> m;
	m--;
	rep(i,1,n) cin >> a[i],insert(a[i]); 

	for (int i = 30;i >= 0;i--)
		if (m >> i & 1)
		{
			int p = 0,cnt = (1<<i);
			for (int j = 30;j >= i;j--)
			{
				int ch = (m >> j & 1);if(j==i)ch=0;
				if (son[p][ch])p=son[p][ch];
				else p = son[p][!ch],ans += cnt * (1ll<<j); 
			}
			solve(p,i - 1,cnt);		
		}
	
	int p = 0,cnt = 1; // 还剩下一个 [m,m]
	for (int j = 30;j >= 0;j--)
	{
		int ch = (m >> j & 1);
		if (son[p][ch])p=son[p][ch];
		else p = son[p][!ch],ans += cnt * (1ll<<j); 
	}	
	cout << ans << endl;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...