发表于 
1
2
3
4
5
序列自动机就是dp。。
记录next[i][26]，O(26n)的预处理，从n到1，每次a[26]记录最后出现的位置，然后复制给next就可以了（next是dag）
状压加手算优化（大于21就无解我也不会证）
可以看第一道魔改题
构造出n^2-2n+4的数列（所以可以卡22）
阅读全文 »

发表于

6.6
不要在学校里面打印啊啊啊
0.8元一张超贵的
在家打一份到学校复印0.15元一张

6.14
发现问题才是最困难的啊
懵懵懂懂连问题都问不出来说明是真的没理解
发现问题起码说明思路是清晰的（可能不对？）

发表于 
1
2
3
4
5
6
7
8
9
单hash被卡我也很无奈（明明很正常好吗）
但是rk1居然是单hash。。
233无敌啊
不过我233就a不了
挺简单的就是要双hash
hzw的做法也挺强的
前后各一边hash，每次底数不一样
反正不要让删掉的那一位有贡献就行
怎么做你开心就好
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
因为单词数比较少
不要一个字符一个字符考虑
考虑一个单词到一个单词的转移
求出i到j的转移（用hash，复杂度是O(sum(len)*n))
题目变成求出在n个点的图上走k步最少的边权和
k小的话可以O(nk)dp
k大的话考虑dp优化，矩阵+倍增，预处理出走2的幂步的最小边权和
犯了一堆错：
i/j打错
mi[0]没有初始化
少break，break后不执行++i!
数组开小了
hash和mi要求同类型
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
hash
1.自然溢出，ll或ull都可以，不需要模数，快，可能会被卡
2.取模，注意永远不要变成负值，值域控制在[0,p)，因为变成负值相当于一种取模
3.双hash：hash1+hash2，可能会被卡常
判断一个字符串的循环节：
枚举len（len整除|s|)
然后判断前|s|-len和后|s|-len个的hash值是否相同
对每个询问，不断除以长度的质因数并判断
总复杂度是O(n+qlogn)
先线性筛求出每个数的最小质因数，然后可以在O(总因数个数)内求出1到n的因数个数
阅读全文 »

发表于 
1
2
3
4
5
6
在ac自动机上dp
f[i][j]表示匹配串到第i位，在ac自动机上跑到j位置的最小修改次数
ac自动机上每个点要或上fail树上的每一个祖先
可以在求fail指针之后求出
多测注意情况数组和变量（变量变量变量）
sz没清空然后re好久
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
也是神题了
字符串综合题
各种做法
ac自动机暴力过不了？
假的
zyz的暴力跑得飞快
而且很难卡（我想了半天也构造不出来）
一个有复杂度保证的做法
Q1就是fail树中一个点的子树中有多少个不同的标记
对于同一个名字
将它在fail树中所有的点按dfn排序，在dfs序上打标记
每个点自身+1，和前一个点的lca处-1，这样可以保证每个名字在一颗子树中只产生1的贡献
Q2就是问一个点到根有多少点名串
在in的地方+1，out+1的地方-1，这样可以保证每个名字只会考虑在它的根的路径上的点
还是要减掉lca
阅读全文 »

发表于

Griffin

Description

狮鹫是联盟的主要交通工具，在艾泽拉斯的土地上散布着n个狮鹫站点，有m条有向的飞行线路，也就是构成了一张n个点m条边的有向图。这m条线路被分成了c种等级，对于其中的第i种等级，只有声望达到了wi才能乘坐狮鹫飞过这条线路。小C现在在暴风城（1号点），他要赶到暗月马戏团（n号点）参加他学长的电音表演。作为一个喜欢藏锋的健美先生，初始时他声望为0。但他实在是太健美了，以至于他每乘坐一次狮鹫（即经过一条边）就能使他的声望 +1 。为了更好地藏锋，小C不会通过其他方法来提升声望。 小C不喜欢步行，也不会开传送门，所以他不会通过除乘坐狮鹫以外的其他方法来到达另一个站点。现在他想知道是否能到达，如果能，他还想知道他最少要经过多少条边才能到达。

阅读全文 »