rprp

数据结构

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

/ 注册

全部文章 / 数据结构（共18篇）

Luogu [ZJOI2015]幻想乡战略游戏

显然，一棵树的带权重心最多只有两个，最少会有一个，而且在这两个点的答案一定相等。（都是带权重心当然相等）鉴于点分治的写法貌似并不太需要这样的分析，就不说了。我不会首先建出一颗点分树，然后考虑在点分树上跳儿子来保证复杂度，于是我们就需要快速算出所有点到这个重心的带权距离和。由于这题是点分树，考虑在点...

动态点分治

2020-05-05

0 375

线性基小结

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

线性基

2020-05-01

0 401

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

Luogu P4301 [CQOI2013]新Nim游戏

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

Nim 线性基

2020-05-01

0 467

Luogu P3857 [TJOI2008]彩灯

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

线性基位运算

2020-05-01

0 469

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 P4116 【Qtree3】

我寻思这题为什么LCT题解这么少啊... 这个题目连换根都不要的话LCT岂不是不用维护翻转操作了嘛？然后pushdown,makeroot等等函数都不要写了然后50行就完事了？？？ #include <cstdio> #define R register const int MAX...

Link-Cut-Tree

2020-04-30

0 349

Luogu P3631 【[APIO2011]方格染色】

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

并查集位运算妙啊

2020-04-30

0 716