回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

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

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共1124篇）

P5829 【模板】失配树

P5829 【模板】失配树题目：题解：参考题解我们先想一个问题：如何求出一个字符串的所有border？如果一个字符串既是 S的前缀又是 S 的后缀，那么我们把 SS 自己平移一下就可以前后重合，然后我们就可以继续匹。。。。。这不就是KMP吗求两个前缀的最长公共border，先对原串进行KMP...

失配树 ***

2021-02-18

0 641

失配树（border树）

4和6没有border关系举例子：当i = 3时，j = fa[i-1] = fa[2] = 0s[j+1] = s[1] = a = s[3]所以把i = 3点的父亲设为j+1 = 1P5829 [模板]失配树

失配树

2021-02-18

0 671

P3265 [JLOI2015]装备购买

题目描述：给N个整数向量，每个向量带权值，求权值和最小的线性基题解：按权值v从小->大排序，依次插入线性基。整数线性基的思想类似，只是此时“消去”不能直接xor完成，需要类似高斯消元一样for一遍代码： #include<bits/stdc++.h> #define eps...

线性基 *** 高斯消元

2021-02-18

0 632

[TJOI2008]彩灯

题目： Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 N个独立的灯泡构成的，并且有 MM 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 2^N^个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没...

线性基 ***

2021-02-18

0 536

【acwing210 异或运算】

【acwing210 异或运算】题意：给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，问所有能得到的不同的结果中第k小的结果是多少。题解：把所有数插入线性基，把k二进制分解然后把1对应的位置xor起来；注意这样是从第0小=0开始数，需要特判0是否能够被x...

** 线性基

2021-02-18

0 627

P4301 [CQOI2013] 新Nim游戏

P4301 [CQOI2013] 新Nim游戏题目：在传统的Nim游戏基础上加一步，在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。题解：...

** 线性基

2021-02-18

0 614

P4570 [BJWC2011]元素

题目描述：每个矿石有序号和魔力值，每个矿石最多使用一次，且多个矿石序号不能异或为0的前提下，问最多可以得到多少魔力值题解：异或运算的最终结果只和用于运算的数的各位上1的数量有关，与各数字运算的顺序无关所以直接先使用魔力值最大的石头就行按照魔力值从大到小排列，insert成功的就记录魔力值，失败...

线性基

2021-02-18

0 589

树链剖分

@[toc]源自oi-wiki树链剖分思想及能解决的问题树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体的说：将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。树链剖分有重链剖分，长链剖分和用于Link/cut Tree的剖分，大多数情况下（没有特别说明...

树链剖分

2021-02-18

0 632

P3812 【模板】线性基

P3812 【模板】线性基题目描述给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大题解：把所有数insert进入线性基，把线性基中所有元素xor起来 = ans 代码： #include<bits/stdc++.h> typedef long long ...

** 线性基

2021-02-17

0 606

线性基

线性基概念 B成为线性基这个过程其实相当于将S压缩成B 构造线性基线性基满足特殊性质：若a[i]!=0（即主元i存在），则线性基中只有a[i]的第i位是1；且此时a[i]的最高位就是第i位为了实现这个性质需要用特殊的insert方法：（为了确保有主元的一列只有一个1）如果第j位是主元不是自...

** 线性基

2021-02-16

0 501