P5829 【模板】失配树 题目：  题解： 参考题解我们先想一个问题：如何求出一个字符串的所有border？如果一个字符串既是 S的前缀又是 S 的后缀，那么我们把 SS 自己平移一下就可以前后重合，然后我们就可以继续匹。。。。。这不就是KMP吗求两个前缀的最长公共border，先对原串进行KMP，通过跳两个前缀的next求到两个前缀的所有border我们通过next数组构建一棵树（发现这就是只有一个字符串的AC自动机的fail树，所有我们也叫它fail树），容易发现两个前缀的最长公共border就是他们在fail树上的LCA 综上所述：  对原串KMP一遍，求的next数组 构建fail树...

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

题目描述： 给N个整数向量，每个向量带权值，求权值和最小的线性基 题解： 按权值v从小->大排序，依次插入线性基。整数线性基的思想类似，只是此时“消去”不能直接xor完成，需要类似高斯消元一样for一遍 代码： #include<bits/stdc++.h> #define eps 1e-5 using namespace std; struct node{ double a[510]; int w; bool operator <(const node x) const{ return w<x.w; } }; node q[510]; int p[510],n,...

题目： Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 N个独立的灯泡构成的，并且有 MM 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 2^N^个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？ 注： 开始时所有彩灯都是不亮的状态。 题解： 线性基裸题，把n个数插入线性基，ans=(1<&...

【acwing210 异或运算】 题意： 给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，问所有能得到的不同的结果中第k小的结果是多少。 题解： 把所有数插入线性基，把k二进制分解然后把1对应的位置xor起来；注意这样是从第0小=0开始数，需要特判0是否能够被xor出来（insert失败），可以的话需要--k。 代码：  #include<bits/stdc++.h> #define reg register using namespace std; typedef long long ll; const int MN=60; ll a[61]...

P4301 [CQOI2013] 新Nim游戏 题目： 在传统的Nim游戏基础上加一步，在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。 题解： 传统的Nim游戏策略：非空石子数量xor和等于0，则必败A的目的是：不论B怎么拿，都无法剩下一个xor和等于0的子集。也就是A拿完后剩下一个线性基即可，因为线性基是线性无关的，肯定不为0，题目又要求A拿走尽量少的石头，先按照从大->小排序，求最大的线性基 代码： #include<bi...

题目描述： 每个矿石有序号和魔力值，每个矿石最多使用一次，且多个矿石序号不能异或为0的前提下，问最多可以得到多少魔力值 题解： 异或运算的最终结果只和用于运算的数的各位上1的数量有关，与各数字运算的顺序无关所以直接先使用魔力值最大的石头就行按照魔力值从大到小排列，insert成功的就记录魔力值，失败的就跳过 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||...

@[toc]源自oi-wiki树链剖分 思想及能解决的问题 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。具体的说：将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。 树链剖分有重链剖分，长链剖分和用于Link/cut Tree的剖分，大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分” 解决的问题  修改 树上两点之间的路径上 所有点的值。 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。重链剖分 定义： 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子...

P3812 【模板】线性基 题目描述 给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大 题解： 把所有数insert进入线性基，把线性基中所有元素xor起来 = ans 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0...

线性基概念 B成为线性基这个过程其实相当于将S压缩成B 构造线性基 线性基满足特殊性质：  若a[i]!=0（即主元i存在），则线性基中只有a[i]的第i位是1；且此时a[i]的最高位就是第i位  为了实现这个性质需要用特殊的insert方法：（为了确保有主元的一列只有一个1）如果第j位是主元不是自由元，那么要始终保持第j列只有第j行中的一个1:对于插入的x，最高位1是第j位，查看第j-1位到第0位是否已经有1存在，如果存在就将x的该位异或。还要将其他行的第j位异或掉详细过程见下图 代码： bool insert(ll x){ for(int j=L;j>=0;--j){//从最高位开始...

acwing221 龙哥的问题@[toc] 题目：  题解：  代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; int phi(int x) { int ans=x; for(int i=2;(ll)i*i<=x;++i) if(x%i==0) { ans=(ll)ans*(i-1)/i; while(x%i==0) x/=i; } if(x>1) ans=(ll)ans*(x-1)/x; return ans; } int main() { int n; scanf("%d...

@[toc] 题目： 给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。GCD(x,y)即求x，y的最大公约数。 题解： 列出公式推导即可  代码： #include<bits/stdc++.h> #define MAXN 10000011 typedef long long ll; using namespace std; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();...

题目： n*m个网格，有平原，有山地，平原可以放部队，部队攻击范围如图（不受地形影响）（H为山地，P为平原） 题解： 确定状态：因为每个炮可以打到两行，所以每一行放置方式与他放置的情况有关dp[i][j][k]表示第i行为状态j，第i-1行为状态k时所用的最大炮兵数也就是同时记录两行状态，根据已知的两行状态推下一行状态转移：dp[i][j][p]=max(dp[i][j][p],dp[i-1][p][q]+num[j])q被枚举第i行状态：j第i-1行状态：p第i-2行状态：qj，p，q不能发生冲突任意1左右两边两位都不是1((i&(i>>1))==0) &&amp...

P1896 [SCOI2005]互不侵犯  题目： 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 题解： 需要知道前一行的情况，所以一行一行的放车记录每行的情况在本题中，不能存在相邻的1对于一行x：(x&(x<<1))==0----->可以判断左右是否有相邻的1对于上一行x，下一行y：(x&y）= = 0(x&(y<<1)) = =0(x&(y>>1)) = = 0上下，左下，右下都不为0dp[i][j][k]表示第...