求助 QWQ
查看原帖
求助 QWQ
1072440
Kevin__Jun楼主2025/2/1 23:20

求助 QWQQWQ

为啥样例都过不了

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500010
typedef long long ll;
int trie[MAXN*32][2],sz[MAXN*32];
int n,k,tot;
ll a[MAXN];
struct node {
	ll w;
	int x,y;
	bool operator < (const node &A) const {	
		return w<A.w;
	}
};
priority_queue <node> q;
node d[MAXN];
void insert(ll val) {
	int u=0;
	for(int i=32;i;i--) {
		int a=(val>>i)&1;
		if(!trie[u][a])
			trie[u][a]=++tot;
		u=trie[u][a];
		sz[u]++;
	}
} 
ll find (ll val,int t) {
	ll s=0;
	int u=0;
	for(int i=32;i;i--) {
		int a=(val>>i)&1;
		if(sz[trie[u][!a]]>=t) 
				u=trie[u][!a],s+=(1ll<<i);
		else {
			t-=sz[trie[u][!a]];
			u=trie[u][a];
		}
	}
	return s;
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		a[i]^=a[i-1];
		cout<<a[i]<<" ";
	} 
	puts("");
	for(int i=0;i<=n;i++) 
		insert(a[i]);
	k*=2;
	for(int i=0;i<=n;i++) {
		d[i].w=find(a[i],1);
		d[i].x=i;
		d[i].y=1;
		q.push(d[i]);
	}
	ll ans=0;
	node tmp;
	for(int i=1;i<=k;i++) {
		tmp=q.top();
		q.pop();
		ans+=tmp.w;
		//cout<<tmp.x<<" "<<tmp.y<<" "<<tmp.w<<'\n';
		d[tmp.x].y++;
		d[tmp.x].w=find(a[tmp.x],d[tmp.x].y);
		q.push(d[tmp.x]);
	}
	ans/=2;
	printf("%lld\n",ans);
	return 0;
}

感谢帮助!!

2025/2/1 23:20
加载中...