第k小线性基求助
  • 板块学术版
  • 楼主hfjh
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/6/7 21:05
  • 上次更新2023/10/23 13:42:39
查看原帖
第k小线性基求助
251449
hfjh楼主2023/6/7 21:05

站外求助,求调

题目链接 大意就是 nn 个数求异或第 kk 大 测试点大的都过了,就这个过不了

输入

输入

答案

答案

我的输出

我的答案 (每个都和正确答案差一点)

我的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n,m;
ll x,lb[60],ans[60],ff;
void add(ll x){
	int bj = 0;
	for(int i = 55; i >= 0; --i){
		if(x >> i & 1){
			if(lb[i])
				x = x ^ lb[i];
			else{
				lb[i] = x;
				x = i;
				bj = 1;
				break;
			}
		}
	}
	if(x == 0) ff = 1;
	if(bj == 0) return ;
	for(int i = x - 1; i >= 0; --i)
		if(((lb[x] >> i) & 1) && lb[i])
			lb[x] = lb[x] ^ lb[i];
	for(int i = 55; i >= x + 1; --i){
		if(lb[i] && ((lb[i] >> x & 1) ))
			lb[i] = lb[i] ^ lb[x];
	}
}
void output(){
	for(int i = 0;i <= 55; ++i){
		cout<<lb[i]<<' ';
	}
}
void input(){
	cin>>n;
	for(int i = 1 ; i <= n; ++i){
		cin>>x;
		add(x);
	}
}
void op(){
	int tot = -1;
	for(int i = 0; i <= 55; ++i)
		if(lb[i])
			ans[++tot] = lb[i];
	cin>>m;
	for(int i = 1; i <= m; ++i){
		cin>>x;
		x -= ff;
		ll an = 0;
		if(x >> (tot + 1) >= 1){
			cout<<-1<<'\n';
		}else{
			for(int j = 0; j <= tot; ++j){
				if(x >> j & 1){
					an = an ^ ans[j];
				}
			}
			cout<<an<<'\n';
		}
	}
	
}
int main(){
	input();
	op();
	return 0;
}


2023/6/7 21:05
加载中...