首页 > 其他分享 >command_block 的《线性基小记》注

command_block 的《线性基小记》注

时间：2023-07-31 18:22:55浏览次数：76  
标签：lb int -- command 线性 return include block 小记

目录
command_block的《线性基小记》原文

1. 前置知识

  1. 线性有关/无关：
    知乎中有对线性相关与线性无关比较具象化的解释。可以发现，线性基就是一种线性无关构成的线性相关的集合。
  2. 张成：
    就是线性基的组成的集合。
  3. 基
    三个性质都很好理解，注意\(span(B)\)表示一个张成空间（属于集合）。
  4. 线性相关引理
    就是线性相关性质，没啥好说的。

2.OI中的线性基

在OI中，“线性基”专用于解决有关异或的一些问题。

张成空间判定问题Ⅰ&Ⅱ

\(\centerdot\) 判定问题Ⅰ很好理解，参见P4151 [WC2011] 最大XOR和路径就是引理的基本运用。
\(\centerdot\) 判定问题Ⅱ利用了三角矩阵优化，思维很好。

实数域线性基

其实很常规，但是没想到。
如果像异或那样写出一个式子，那么他长得看起来很像高斯消元。
但是只用得到消元的全式子同除以一个系数的部分。
P3265 [JLOI2015] 装备购买

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;

inline int read(){
	int x = 0 ,y = 1 ;
	char c = getchar() ;
	while(c < '0' || c > '9'){
		if(c == '-')	y = -1 ;
		c = getchar() ;
	}
	while(c <= '9' && c >= '0'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * y ;
}

const int MAXN = 505 ;
const double eps = 1e-5 ;
int n ,m ;
struct Stuff{
	double z[MAXN] ;
	int cost ;
}s[MAXN] ;

inline bool cmp(Stuff a , Stuff b){
	return a.cost < b.cost ;
}

int tot ,ans ;
int lb[MAXN] ;
inline void add(int x){
	for(int i = 1;i <= m;++i){//枚举每一位 
		if(s[x].z[i] <= eps && s[x].z[i] >= -eps) continue ; 
		if(lb[i] == 0){
			lb[i] = x ;
			tot++ ;
			ans += s[x].cost ;
			return ;
		}else{
			double k = s[x].z[i] / s[lb[i]].z[i] ;//做差消掉这件商品的每一个已知lb 
			for(int j = i;j <= m;++j){
				s[x].z[j] -= k * s[lb[i]].z[j] ;
			}
		}
	}
}

int main(){
	n = read() ,m = read() ;
	for(int i = 1;i <= n;++i){
		for(int j = 1;j <= m;++j)	scanf("%lf" , &s[i].z[j]) ;
	}
	for(int i = 1;i <= n;++i)	s[i].cost = read() ;
	sort(s+1 , s+1+n , cmp) ;
	for(int i = 1;i <= n;++i){//遍历到第i件物品 
		add(i) ;
	}
	printf("%d %d" , tot , ans) ;
	return 0 ;
}

k小子集异或和

woc 5min一发过P3857 [TJOI2008] 彩灯
结论很好感性理解 感觉很好记
小心-1的情况

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std ;

const int MAXN = 55 ;

int n ,m ;
bitset<MAXN> num ;
bitset<MAXN> s[MAXN] ;
int tot ;
inline void add(bitset<MAXN> x){
	for(int i = 50;i >= 0;--i){
		if(x[i]){
			if(s[i].none() == false){
				x ^= s[i] ;
			}else{
				s[i] = x ;
				tot++ ;
				return ;
			}
		}
	}
}

int main(){
	scanf("%d%d" , &n , &m) ;
	for(int i = 1;i <= m;++i){
		char str[MAXN] ;
		scanf("%s" , str) ;
		for(int j = 0;j < n;++j){
			if(str[j] == 'O'){
				num[j] = 1 ;
			}else{
				num[j] = 0 ;
			}
		}
		add(num) ;
	}
	printf("%d" , (1ll << tot) % 2008) ;
	return 0 ; 
}

线性基合并

暴力合并即可。
P3292 [SCOI2016] 幸运数字

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std ;

const int MAXM = 2e4+10 ;

int n ,m ;
int jump[MAXM][17] ,dep[MAXM] ;
ll f[MAXM][17][62] ,lb[62] ;
ll val[MAXM] ;

struct Edge{
    int to ,next ;
}edge[MAXM<<1] ;
int head[MAXM] ,edge_cnt ;
inline void edge_add(int from , int to){
	edge[++edge_cnt].to = to ;
	edge[edge_cnt].next = head[from] ;
	head[from] = edge_cnt ;
}

inline void insert(ll *a , ll x){
    for(int i=60;i>=0;i--){
        if(!((x >> i) & 1ll)) continue ;
        if(!a[i]){
			a[i] = x ;
			return ;
		}
        else x ^= a[i] ;
    }
}

inline void merge(ll *a,ll *b){
    for(int i = 60;i >= 0;--i)	if(b[i]) insert(a , b[i]) ;
}

inline void dfs(int node , int fa){
    jump[node][0] = fa ;
    dep[node] = dep[fa] + 1 ;
    for(int i = 1;i <= 16;++i)
        if(jump[node][i-1]){
        	jump[node][i] = jump[jump[node][i-1]][i-1];
        	memcpy(f[node][i] , f[node][i-1] , sizeof f[node][i-1]) ; 
        	merge(f[node][i] , f[jump[node][i-1]][i-1]) ;
        }
    for(int i = head[node];i;i = edge[i].next){
    	int v = edge[i].to ;
        if(v == fa)	continue ;
        dfs(v , node) ;
    }
}

inline int LCA(int x , int y){
    if(dep[x]<dep[y]) swap(x , y) ;
    int dist = dep[x] - dep[y] ;
    for(int i = 16;i >= 0;--i){
        if((dist>>i) & 1)	merge(lb , f[x][i]) ,x = jump[x][i] ;
    }
    if(x == y) return x ;
    for(int i = 16;i >= 0;--i){
        if(jump[x][i] != jump[y][i]){
            merge(lb , f[x][i]) ;
			merge(lb , f[y][i]) ;
            x = jump[x][i] ;
			y = jump[y][i] ;
        }
    }
    merge(lb , f[x][0]) ;
    insert(lb , val[y]) ;
    return jump[x][0] ;
}

int main(){
    scanf("%d%d" , &n , &m) ;
    for(int i=1;i<=n;i++){
        ll a ;scanf("%lld" , &a) ;
        val[i] = a ;
        insert(f[i][0] , a) ;
    }
    for(int i = 1;i < n;++i){
    	int u ,v ;
        scanf("%d%d" , &u , &v) ;
        edge_add(u , v) ;
        edge_add(v , u) ;
    }
    dfs(1 , 0) ;
    while(m--){
        memset(lb , 0 , sizeof lb) ;
        int u , v ;scanf("%d%d" , &u , &v) ;
        int lca = LCA(u , v) ;
        merge(lb , f[lca][0]) ;
        ll ans = 0 ;
        for(int i = 60;i >= 0;--i)	ans = max(ans , ans ^ lb[i]) ;
        printf("%lld\n" , ans) ;
    }
    return 0 ;
}

P4839 P 哥的桶
线段树维护线性基合并时 三种合并query情况分开！不同区间的线性基不能合并！

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std ;

const int MAXN = 5e4+10 ;

int n ,m ;

struct Lb{
	int a[32] ;
	
	void insert(int x){
		for(int i = 31;i >= 0;--i)
			if(x & (1 << i)){
				if(a[i])	x ^= a[i] ;
				else{
					a[i] = x ;
					return ;
				}
			}
	}
	
	void merge(Lb n){
		for(int i = 31;i >= 0;--i)
			if(n.a[i])	insert(n.a[i]) ;
	}
}tree[MAXN<<2] ;

inline void update(int node , int li , int ri , int x , int delta){
	if(x < li || x > ri)	return ;
	tree[node].insert(delta) ;
	if(li == ri)	return ;
	int mid = (li + ri) >> 1 ;
	if(x <= mid)	update(node<<1 , li , mid , x , delta) ;
	else update(node<<1|1 , mid+1 , ri , x , delta) ;
}

Lb ans ;
inline void query(int node , int li , int ri , int l , int r){
	if(l <= li && ri <= r){
		ans.merge(tree[node]) ;
		return ;
	}
	int mid = li + ri >> 1 ;
	/*if(l <= mid)	query(node<<1 , li , mid , l , r) ;
	if(mid < r)	query(node<<1 , mid+1 , ri , l , r) ;*/
	if(r <= mid)	query(node<<1 , li , mid , l , r) ;//三种可能分清楚！ 
	else if(mid < l)	query(node<<1|1 , mid+1 , ri , l , r) ;
	else query(node<<1 , li , mid , l , mid) ,query(node<<1|1 , mid+1 , ri , mid+1 , r) ;
	//l r区间要分开！两边的线性基不能合并！ 
}

int maxx = 0 ;
int main(){
	scanf("%d%d" , &n , &m) ;
	for(int i = 1;i <= n;++i){
		int opt ;scanf("%d" , &opt) ;
		if(opt == 1){
			int k ,x ;scanf("%d%d" , &k , &x) ;
			update(1 , 1 , m , k , x) ;
		}else{
			int l ,r ;scanf("%d%d" , &l , &r) ;
			memset(ans.a,0,sizeof(ans.a));
			maxx = 0 ;
			query(1 , 1 , m , l , r) ;
			for(int j = 31;j >= 0;--j)	maxx = max(maxx , maxx ^ ans.a[j]) ;
			printf("%d\n" , maxx) ;
		}
	}
	return 0 ;
}

P4869 albus就是要第一个出场
推式子很好推 但是实现有较多细节。

#include<iostream>
#include<cstdio>
using namespace std ;

const int MAXN = 1e5+10 ;
const int mod = 10086 ;
int lb[MAXN] ;
int n ,id ;
int cnt = 1 ;

inline void insent(int x){
	for(int i = 30;i >= 0;--i){
		if((1 << i) & x){
			if(lb[i] == 0){
				lb[i] = x ;
				return ;
			}else{
				x ^= lb[i] ;
			}
		}
	}
	if(x == 0){//这个数可以被线性基表示 
		cnt = (cnt << 1) % mod ;//方案数*2 表示乘法原理多一位 
	}
}

int main(){
	scanf("%d" , &n) ;
	for(int i = 1;i <= n;++i){
		int x ;scanf("%d" , &x) ;
		insent(x) ;
	}
	scanf("%d" , &id) ;
	int rk = 0 ,tp = 1 ;
	for(int i = 0;i <= 30;++i){
		if(lb[i]){//线性基中有这位 说明可以计算 
			if((id >> i) & 1) rk += tp ;//需要利用线性基中的这位元素 加上2^i种情况 
			tp <<= 1 ;
		}
	}
	rk %= mod ;//大小上排这么多位 
	printf("%d" , ((rk * cnt == mod) ? 0 : ((rk * cnt + 1) % mod))) ;//每一个数都有一位乘法原理系数 
	return 0 ;
}

P5607 [Ynoi2013] 无力回天 NOI2017
有点麻烦。线段树套线性基，需要用树状数组维护差分。我猜这个做法是唯一维护线段树套线性基的方法。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 5e4+10 ;

inline int read(){
	int x = 0 ,y = 1 ;
	char c = getchar() ;
	while(c < '0' || c > '9'){
		if(c == '-')	y = -1 ;
		c = getchar() ;
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * y ;
}

int n ,m ,w[MAXN] ,c[MAXN] ;
struct LB{
	int lb[35] ;
	inline void insert(int x){
		for(int i = 30;i >= 0;--i){
			if(x & (1 << i)) {
				if(lb[i]){
					x ^= lb[i] ;
				}else{
					lb[i] = x ;
					return ;
				}
			}
		}
	}
} ;

inline LB merge(LB x, LB y) {
	for(int i = 30;i >= 0;--i){
		if (y.lb[i]) x.insert(y.lb[i]) ;
	}
	return x ;
}

struct Segtree{
	LB tree[MAXN<<2] ;

	inline void build(int node , int l , int r){
		for(int i = l;i <= r;++i) tree[node].insert(w[i]) ;
		if(l == r) return ;
		int mid = l + r >> 1 ;
		build(node << 1, l, mid) ;
		build(node << 1 | 1, mid + 1, r) ;
		tree[node] = merge(tree[node << 1] , tree[node << 1 | 1]) ;
	}
	
	inline void update(int node , int li , int ri , int idx , int v){
		if(li == ri){
			memset(tree[node].lb, 0, sizeof tree[node].lb) ;
			tree[node].insert(w[li] ^= v) ;
			return ;
		}
		int mid = li + ri >> 1 ;
		if(idx <= mid) update(node << 1 , li , mid , idx , v) ;
		else update(node << 1 | 1 , mid + 1 , ri , idx , v) ;
		tree[node] = merge(tree[node << 1], tree[node << 1 | 1]) ;
	}
	
	inline LB query(int node , int li , int ri , int l , int r){
		if (li == l && ri == r) return tree[node] ;
		int mid = li + ri >> 1 ;
		if (mid >= r) return query(node << 1, li , mid , l , r) ;
		else if (mid + 1 <= l) return query(node << 1 | 1 , mid + 1 , ri , l , r) ;
		else return merge(query(node << 1 , li , mid , l , mid) , query(node << 1 | 1 , mid + 1 , ri , mid + 1 , r)) ;
	}
}seg ;

inline int lowbit(int x){
	return x & -x ;
}

inline void modify(int i , int x){
	for(int j = i;j <= n;j += lowbit(j)) c[j] ^= x ;
}

inline int trebitquery(int i){
	int ans = 0;
	for(int j = i;j >= 1;j -= lowbit(j)) ans ^= c[j] ;
	return ans ;
}

int main() {
	n = read(); m = read();
	for(int i = 1;i <= n;++i) w[i] = read() ;
	for(int i = n;i >= 2;--i) w[i] ^= w[i - 1] ;
	for(int i = 1;i <= n;++i) modify(i , w[i]) ;
	seg.build(1 , 1 , n) ;
	for(int i = 1;i <= m;++i){
		int opt = read(), l = read() ,r = read() ,v = read() ;
		if(opt == 1){
			modify(l , v) ;
			seg.update(1 , 1 , n , l , v) ;
			if(r < n) {
				modify(r + 1 , v);
				seg.update(1 , 1 , n , r+1 , v) ;
			}
		}else{
			int k = trebitquery(l) ;
			if(l == r){
				printf("%d\n" , max(k ^ v , v)) ;
			}else{
				LB ans = seg.query(1 , 1 , n , l+1 , r) ;
				ans.insert(k) ;
				for(int i = 29;i >= 0;--i){
					if ((v ^ ans.lb[i]) > v) v = (v ^ ans.lb[i]) ;
				}
				printf("%d\n" , v) ;
			}
		}
	}
	return 0 ;
}

带删除线性基

\(\centerdot\)强制在线
感觉就是纯分讨。没啥好说的。不会自己看blog。
\(\centerdot\)离线
就是P3733。
好像有不带log的解法。咕咕咕。

总结

感觉比较板。。。
实数域线性基没太想到。
关于数据结构部分还需练习。

标签：lb,int,--,command,线性,return,include,block,小记
From： https://www.cnblogs.com/adolf-stalin/p/17590804.html

相关文章

  • Linux fdisk command All In One
    LinuxfdiskcommandAllInOnediskpartition/磁盘分区$fdisk-hUsage:fdisk[options]<disk>changepartitiontablefdisk[options]-l[<disk>...]listpartitiontable(s)Displayormanipulateadiskpartitiontable.Options:......
  • Visual Studio 调试技巧[Command Window & Immediate Window ](Tips)
    VisualStudio调试技巧[CommandWindow&ImmediateWindow](Tips)1.immediatewindow定义的一些alias（//z2012-3-1314:04:44PMIS2120alias?Debug.Printalias??Debug.QuickWatchaliasAddProjFile.AddNewProjectaliasaliasTools.Al......
  • python的tril，pad，block_diag在LLM上的使用
    最近需要对position_ids和attention_mask进行重构，所以需要掌握numpy的一些操作，以下是一些示例，多个下三角矩阵拼接：importnumpyasnpfromscipy.linalgimportblock_diagA=np.ones((2,2))B=np.ones((3,3))b=[A,B]print(np.tril(block_diag(*b)))[[1.0.0.0.0.]......
  • 基于C语言设计的Bootblock设计
    完整资料进入【数字空间】查看——搜索"writebug"一、Project1Bootloader设计文档中国科学院大学[王苑铮]1.1Bootblock设计流程请至少说明以下内容Bootblock主要完成的功能把kernel从sd卡读取到内存中的指定位置，之后跳转到内核的起始地址让内核开始执行。Bootblock被载......
  • 单例模式小记
    1.概念单例模式是一种设计模式。保证一个类只有一个实例，提供一个全局访问点。2.实例构造函数私有化，防止外部创建对象。提供静态成员函数getInstance，获取单例指针。使用静态指针保存单例实例。classSingleton{public:staticSingleton*getInstance(){......
  • CommandLineRunner、ApplicationRunner、InitializingBean、@PostConstruct 执行顺序
    概述开发中可能会有这样的场景，需要在容器启动的时候执行一些内容。比如读取配置文件，数据库连接之类的。SpringBoot给我们提供了两个接口来帮助我们实现这种需求,两个启动加载接口分别是：CommandLineRunner和ApplicationRunner。Spring提供了接口InitializingBean，jdk提供了@PostC......
  • android studio ninja: build stopped: subcommand failed.
    解决AndroidStudioNinjaBuild停止的问题概述在使用AndroidStudio进行开发时，有时候会遇到"androidstudioninja:buildstopped:subcommandfailed."的错误提示。这通常是由于项目构建过程中的某些问题导致的。下面我将详细介绍解决这个问题的步骤，并提供相应的代码示......
  • 【Java】信创开发（东方通）中台后端项目踩坑小记
    在万事国产化以备世界风云突变之日，我们做软件开发的也不可避免的需要完成一部分信创项目，通常Web项目国产化部署的首要选择都是东方通Web容器。此次中台项目信创适配过程中踩坑无数，唯独这个坑让我印象深刻念念不忘，接下来就请诸君与我共同复盘一下。背景：中台项目源于ruoyi开......
  • Qt QCommandLineOption类
    QCommandLineOption类定义了可能的命令行选项头文件：#include<QCommandLineOption>cmake：find_package(Qt6COMPONENTSCoreREQUIRED)target_link_libraries(mytargetPRIVATEQt6::Core)qmake：QT+=core引入：Qt5.2详细说明该类用于描述命令行上的选项。它允许......
  • Qt 解析命令行（QCommandLineOption和QCommandLineParser类）
    Qt从5.2版开始提供了两个类QCommandLineOption和QCommandLineParser来解析应用的命令行参数。一、命令行写法命令行："-abc"在QCommandLineParser的解析模式为ParseAsCompactedShortOptions(默认)时会被认为是3个参数，即"-a"、"-b"和"-c"1QCommandLineOptionop1("a");2......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99