学长的代码 当模板使了
这个hash是这么算得:
所以字符串第几位到第几位可以通过公式求出来
其中x就是seed 本代码为 13331
代码中的buf就是seed的i次方
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>b;i--)
#define lson num<<1
#define rson num&...
阅读全文
Longest Common Substring
坑死了 p什么的np什么的q什么的nq什么的 - -
都注意了构造还是写错了TAT
利用后缀自动机的性质:能接受所有子串
也就是说能接受的就一定是该串的子串
失配时要沿父亲走 原理同AC自动机
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NODE = 250010<<1,CH = 26,root=1;
int ch[NODE][CH],val[NODE],par[NODE],sz,last;
...
阅读全文
没注意只有一个case 不知道怎么就错了 - -
带权并查集的"权"表示该节点与爸爸的关系
这题的关系有
0.儿子与爸爸是同类
1.儿子被爸爸是吃 - -
2.儿子吃爸爸 = =
为什么权要这样设?待会解释
所以每个节点多一个变量记录权
那两个不是父子关系的点之间的关系怎么表示呢?
为了解决这个问题 我们把每条指向父亲的边都看作向量!
eg:假如现在UFS是这样的
(节点,权) (1,0)->(2,1)->(3,2)->(4,0)
那么可...
阅读全文
主席树的应用 若该位置的数出现过就把该版本的之前的位置-1 再把该版本的该位置+1,否则直接+1
查询的时候 有点像zkw线段树那种 - -
(哎呀..遭不住了啊..手真是贱啊..总是写错..花了一个小时debug真是菜啊TAT)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson st[num].ls
#define rson st[num].rs
using namespace std;
const int MAXN = 30100;
struct node
{
int ls,...
阅读全文
粗心了点，就一个强连通缩点，忘了出栈后要标记，找了一天的bug，，，
题意有点难懂，飞鼠想给大家发礼物，收到礼物后大家给飞鼠的满足程度都已数量化。每个人都住一个房间，房间之间的路是单向的，飞鼠可以选任一个点为起点，路可以重复走，房间不能重复访问，但可以经过而不访问。现在问飞鼠得到的满足程度最大会是多少？，有负值，，如果图不形成环，直接求就可以，看了样例可能形成环，所以用Tarjan缩点，，，
#inclu...
阅读全文
![[bzoj 1026]windy数[数位DP]](https://admin.xuebuyuan.com/wp-content/themes/HotNewspro/images/random/19.jpg)
windy数的定义:
相邻两数位之间的差不小于2.
这个定义表明windy数的一部分一也是windy数.
较长的windy数与较短的windy数之间的关系:
当较短的数是windy数时,只要考虑加的那一位和最高位之间的差是否大于1.
最高位.
于是可设计状态:
dp[i][j]----有i位的数中,最高位为j的windy数的个数.
状态转移方程:
dp[i][j] += dp[i-1][k]( k = 0..9 && |j-k| < 2)
预处理是考虑首位为0的情况的,因为用它的时候它常常不是首位...
阅读全文
![[poj 2978]Colored Stones[状态压缩DP]](https://admin.xuebuyuan.com/wp-content/themes/HotNewspro/images/random/6.jpg)
题意:
给出n个石子,一共m种颜色.问最少去掉几个石子使得同种颜色全连续.
思路见注释.
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int kMAX=105;
/// dp[x][y][z]，x指的是[到达第x个石子，包含(意思是参与讨论,并不是说一定留下)第x个石子]的情况下，颜色组合为y（每种颜色占一位），
/// 最后一颗石子的颜色为z的最多剩余石子数，因为[第x颗石子去留不一定...
阅读全文
题意：在一组数中执行两种操作
"C a b c" means adding c to each of
Aa, Aa+1, ... ,
Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of
Aa, Aa+1, ... ,
Ab.
思路：很典型的线段树 开始我用普通的线段树做 updata 操作是每一对应的区间都加上w 结果TLE
问了一下zcube 说用什么 线段树遗传（不明白这是个什么？？） 上网看了一下别人的解题报告 updata
操作的复杂度太高了（因为我要遍历所有要更新的点 时间复...
阅读全文
题意：求一个区间A到B内牛的最大高度差？
思路：又是一道经典的线段树 比前面的两道要简单，没有更新操作
//2416K
1579MS
#include <stdio.h>
#define M 50005
struct data
{
int
l,r;
int
tall,shor;
}line[3*M];
int num[M];
int min (int a,int b)
{
return a
> b?b:a;
}
int max (int a,int b)
{
return a
> b?a:b;
}
int low,hei;
void BuildTree(int left,int right,int u)
{
li...
阅读全文
题意：bessie 有间旅店有N个房间 每次有一组人来住宿，他们需要连续的房间 。bessie要求你帮他个忙，有以下操作
op a ：如果op == 1 表示有a个人要住宿 要求你找出a个连续的房间 起始房间的号数要求最小，如果没有返回0
op a b ：op == 2 表示从a号房起有b个人有退房 即 a到a+b-1 的房间将置空。
思路：超经典的线段树 这道题跟上一道Hotel很像，但稍微复杂点。具体见代码说明。
#include <stdio.h>
#define M 50050...
阅读全文