rprp

分类

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 668人学习

全部文章（共8篇）

Luogu P3812 【模板】线性基

线性基板子题 #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...

线性基位运算

2020-05-01

0 418

Luogu P3857 [TJOI2008]彩灯

把每个对应的序列看成二进制数，能控制就把这一位设为\(1\)，那么每异或出来一个新的数就对应一种情况。根据线性基的性质，任意一个子集异或和都不一样，所以直接线性基即可。 #include <cmath> #include <cstdio> #include <cst...

线性基位运算

2020-05-01

0 469

Luogu P4301 [CQOI2013]新Nim游戏

Nim游戏的结论就是先手异或和不为0的时候必胜，所以就排个序，留下线性基就行了。 #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using nam...

Nim 线性基

2020-05-01

0 467

Luogu P4570 [BJWC2011]元素

题目很显然就是要求序号的线性基。我们希望线性基里的权值最大，就按权值从大到小插入就行了。为什么是对的呢？插入线性基的一个矿石只会和另一些矿石在一个位置上冲突，而那些矿石也只能插入这一位，同时它们价值不如当前的矿石，所以这是最优的。 #include <cstdio> #include...

线性基

2020-05-01

0 457

HDU 3949 XOR

线性基板子题，注意特判\(0\)，开\(long~long\)就好。 #include <cstdio> #include <cstring> using namespace std; #define R register #define LL long long #def...

线性基

2020-05-01

0 368

线性基小结

用处没用我学这东西干嘛快速查询一个数是否可以被一堆数异或出来快速查询一堆数可以异或出来的最大/最小值快速查询一堆数可以异或出来的第k大值这么点？还有点性质在下面可能有点用性质原数列里的任何一个数都可以通过线性基里的数异或表示出来线性基里任意一...

线性基

2020-05-01

0 400

Luogu P4151 [WC2011]最大XOR和路径

原题传送门看见异或最值，估计线性基跑不了了。考虑先随便提出一条从\(1\)到\(n\)的路径，这显然不一定是最优的，但是可以让它变强。比如可以让它中间插入一个环来让它变优。比如说有一条路径: \(1->A->B->C->N\) 可以补成： \(1->A->B-...

线性基妙啊

2020-05-02

0 419

Luogu P3292 [SCOI2016]幸运数字

看到异或最值，显然想到线性基。用树上倍增的方法，维护当前点\(x\)到倍增父节点\(fa[x][i]\)这条路径上的线性基，在倍增的时候暴力合并即可。注意这个线性基的倍增数组是没有包括最后一个点的信息的，需要特殊处理。然后就搞完了。时间复杂度\(O(n*log_n*log_v+q*log_n*...

倍增线性基

2020-05-03

0 379