线性基+查询集合空间是否含有x

偏执的太偏执、 2021-11-27 01:32 288阅读 0赞

一个线性基模板题：

给出一组数，给出x，y，查询这组数能否和 x 异或得到 y。

设我们这组数能异或出来z  x^z=y， 那么x^y  =z ,这样我们就转化为： 能否异或出x^y.

模板题；题目连接：[https://ac.nowcoder.com/acm/contest/180/D?&headNav=www][https_ac.nowcoder.com_acm_contest_180_D_headNav_www]

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50,mx=35;
    struct Node{
    	int num[mx];
    	void init(){
    		memset(num,0,sizeof(num));
    	}
    	void insert(int x){// 
    		for(int i=32;~i;i--){
    			if((x>>i)&1){//这一位有数字 
    				if(!num[i]){
    					num[i]=x;
    					break;
    				}else{
    					x^=num[i];
    				}
    			}
    		}
    	}
    	bool check(int x){//x是不是向量中的数字 
    		for(int i=32;i>=0;i--){
    			if((x>>i)&1){
    				if(!num[i])return 0;
    				else x^=num[i];
    			}
    		} 
    		if(x==0)return 1;
    		return 0;
    	}//判断目标值的每一位是否在线性基中存在
    } a;
    int main(){
    	int n,m;
    	scanf("%d",&n);
    	a.init();
    	for(int x,i=0;i<n;i++){
    		scanf("%d",&x);
    		a.insert(x);
    	}
    	scanf("%d",&m);
    	for(int x,y,i=0;i<m;i++){
    		scanf("%d%d",&x,&y);//能否和x异或得到y，那么x异或y也就等于那个数据， 
    		x^=y;
    		if(a.check(x))printf("YES\n"); 
    		else printf("NO\n");
    	}
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_180_D_headNav_www]: https://ac.nowcoder.com/acm/contest/180/D?&headNav=www

发表评论取消回复

表情：

评论列表（有 0 条评论，288人围观）

还没有评论，来说两句吧...

相关阅读

相关线性代数-基变换

[B站视频-线性代数的本质][B_-] 一般情况下，基向量为i-hat=【1,0】，j-hat=【0,1】使用不同基向量会怎样？如何在不同坐标系之间对向量进行转化？

左手的ㄟ右手/ 2023年06月13日 06:20/ 0 赞/ 41 阅读

相关线性代数1：向量、线性组合、张成的空间和基

课程地址：[【官方双语/合集】线性代数的本质 - 系列合集][-] 目录一、什么是向量 1. 向量的表达方式 2. 向量的加法 3. 向量的数乘二、线性组合、张

àì夳堔傛蜴生んèń/ 2022年12月31日 10:23/ 0 赞/ 197 阅读

相关线性空间

1：n维向量空间如何表示？很简单.只是因为我们处于三维空间,大于三维的度量不容易感知. 先从三维谈起,如向量\{x1,x2,x3\}在三维空间上必然可以分解

亦凉/ 2022年07月15日 14:52/ 0 赞/ 233 阅读

相关线性基

原本想整理下前段时间做的牛客网的赛题，其中有个题目是线性基解决，于是就误入了线形基的坑...看了b站上“时光蒸汽喵”大佬的讲解，很是舒适，今天来整理下几个常见的类型。学习过

小鱼儿/ 2022年03月17日 11:52/ 0 赞/ 225 阅读

相关【模板】线性基

include<bits/stdc++.h> using namespace std; define LL long long LL p[70]

灰太狼/ 2021年11月29日 18:38/ 0 赞/ 324 阅读

相关线性基+查询集合空间是否含有x

一个线性基模板题：给出一组数，给出x，y，查询这组数能否和 x 异或得到 y。设我们这组数能异或出来z x^z=y，那么x^y =z ,这样我们就转化为：能否异

偏执的太偏执、/ 2021年11月27日 01:32/ 0 赞/ 289 阅读

相关 HDU 3949 XOR——————线性基

[XOR][] Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

以你之姓@/ 2021年11月23日 04:28/ 0 赞/ 278 阅读

相关算法学习：线性基

线性基：通过将序列中的数字转化为二进制，表现为矩阵形式，于是通过矩阵的相关知识就能够快速的求取区间内的最大异或和模板：洛谷【P3812】 ![Cont

末蓝、/ 2021年11月17日 10:12/ 0 赞/ 267 阅读

相关线性基训练与总结

线性基我们先考虑基的一些定义和性质。唯一表示线性无关极小生成集 acm中的线性基一般是基于异或运算下的。根据第一条，我们可以解决一系

今天药忘吃喽~/ 2021年09月30日 06:10/ 0 赞/ 299 阅读

相关 SGU - 275 线性基初步

题意:求给出的数任意异或的最大值目前对线性基的理解过于肤浅,有空总结一下 include<iostream> include<algorithm>

缺乏、安全感/ 2021年09月29日 14:46/ 0 赞/ 294 阅读