用处 没用我学这东西干嘛  快速查询一个数是否可以被一堆数异或出来 快速查询一堆数可以异或出来的最大/最小值 快速查询一堆数可以异或出来的第k大值  这么点？ 还有点性质在下面 可能有点用 性质  原数列里的任何一个数都可以通过线性基里的数异或表示出来 线性基里任意一个子集的异或和都不为\(0\) 一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的  原理&实现 由于我想写简单一点，直接对代码写，所以真正的关于线性代数的那一部分就没写了 妄图掩盖自己不会的事实 约定 以下\(p[i]\)表示原序列的线性基数组。 构造 先贴代码 把一个数插入线性基： ...

线性基板子题，注意特判\(0\)，开\(long~long\)就好。 #include <cstdio> #include <cstring> using namespace std; #define R register #define LL long long #define int long long const int MAXN=1e4+10; const int MB=63; int n,q,cnt,zero; LL p[MAXN],a[MAXN]; inline void ins(LL x) { for(R int i=MB;i>=0;i--) { i...

题目很显然就是要求序号的线性基。我们希望线性基里的权值最大，就按权值从大到小插入就行了。 为什么是对的呢？插入线性基的一个矿石只会和另一些矿石在一个位置上冲突，而那些矿石也只能插入这一位，同时它们价值不如当前的矿石，所以这是最优的。 #include <cstdio> #include <algorithm> using namespace std; #define R register #define LL long long const int MAXN=1e3+10; const int MB=62; int n; struct Node { LL x; int ...

Nim游戏的结论就是先手异或和不为0的时候必胜，所以就排个序，留下线性基就行了。 #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R register int n; int a[1000]; inline bool cmp(int x,int y) { return x>y; } int cnt,p[40]; inline int ins(int x) { for(R int i=3...

把每个对应的序列看成二进制数，能控制就把这一位设为\(1\)，那么每异或出来一个新的数就对应一种情况。 根据线性基的性质，任意一个子集异或和都不一样，所以直接线性基即可。 #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R register #define LL long long const int Mod=2008; int n,m; char s[70]; LL p[70]; int...

线性基板子题 #include <cstdio> using namespace std; #define R register #define LL long long LL p[52]; LL n; inline void ins(LL x) { for(R int i=51;i>=0;i--) { if(x&(1LL<<i)) { if(!p[i]) { p[i]=x; return ;} else x^=p[i]; } } } int main() { scanf("%lld",&n); LL x,ans=0; for(...

坐标:HN - ZZ QQ:2167306203

T15 Apio2011 方格染色 20分算法：暴力枚举每个点 抄题解做的还是好好写总结吧 把红色视为0，蓝色视为1 假设有一个表格如下：    A C E G     B D F H    根据题设有\(A\bigoplus B\bigoplus C\bigoplus D=C\bigoplus D\bigoplus E\bigoplus F=1\) 然后有\(A\bigoplus B\bigoplus E\bigoplus F=0\) 而\(E\bigoplus F\bigoplus G\bigoplus H=1\) 所以\(A\bigoplus B\bigoplus G\bigoplus ...

题目大意： 有n对数字，让你将这n对数字染色成红的或蓝的，求\((Rmax-Rmin)*(Bmax-Bmin)\) \(n<=2e5,0<a<=1e9\) 解题过程: 还是luogu比较香..... 在atcode上不会做今天用luogu看就会了是什么鬼... (难道我的水平和OJ界面成正比？？？） 首先这里只有两组而且显然是计算答案的时候是对称的两组 所以考虑让最大值出现在R里面，那么最小值就有两种情况  最小值出现在B里面 那就很easy了，让\(Rmin\)最大，\(Bmax\)最小即可，直接 大的丢到\(a\)里小的丢到\(b\)里就行 最小值出现在\(R\)里面 这...

我寻思这题为什么LCT题解这么少啊... 这个题目连换根都不要的话LCT岂不是不用维护翻转操作了嘛？ 然后pushdown,makeroot等等函数都不要写了 然后50行就完事了？？？ #include <cstdio> #define R register const int MAXN=1e5+10; int ch[MAXN][2],fa[MAXN],id[MAXN],co[MAXN]; #define ls(x) ch[x][0] #define rs(x) ch[x][1] inline int nroot(int x) { return ls(fa[x])==x||rs(f...

本来考场切了的，结果代码没保存，爆炸成80，自闭了。 考场上我是一个一个部分分做的，所以这里我也一个一个部分分写。 0pts \(n=1\) 这个档位是针对样例写的。。。因为不写我就过不了样例。。。 显然如果有一个1操作就输出YES，没有就看相不相等完事。。。 贴一个没有什么用的代码。 inline void Solve_0pts() { if(flg1==1) { printf("YES\n"); } else if(a[1]==b[1]) { printf("YES\n"); } else { printf("NO\n"); } ...

正题 一开始的时候显然第\(i\)天以前可以放\(i\)个任务是吧，然后考虑用一棵线段树维护这个数量，设每天的这个值为\(lev(i)\) 考虑在\(t\)这个截止时间位置放了一个任务，那\((t,n)\)这个区间的$ lev(i)$ 都要减去\(1\)。    插入 设插入的终止时间为\(t\),这个任务的价值为\(p\)。那如何插入呢？  当这个任务与其他的任务不冲突的时候，直接加入完事。也就是当\(min(lev(t\rightarrow n))>0\)的时候不会冲突，然后直接加进去就完事了 当这个任务与其他任务冲突的时候，一个显然的想法就是替换掉最小的，或者不替换。那这个最小的值...

T3 怎么用树剖+线段树啊   不知道线段树怎么维护诶