三木成森
三木成森
全部文章
分类
ac自动机(1)
codeforces(1)
前缀和(2)
后缀(1)
图论(1)
字符串(2)
数据结构(4)
数论(7)
神奇的c++(2)
自动机(1)
归档
标签
去牛客网
登录
/
注册
三木成森的博客
全部文章
(共22篇)
斐波那契自卷积
牛客挑战赛32 C 不会推导,贴一个oeis链接https://oeis.org/A001629通过链接我们知道: 这样我们就可以通过矩阵快速幂求解 代码 #include <bits/stdc++.h> using namespace std; typedef long long l...
2019-09-21
0
387
数论分块——学习
引子 现有一公式,求 a n s = ...
2019-09-18
0
398
2019 icpc 沈阳网络赛 B Dudu's maze 并查集
题意 我们已知n个点,m条边,k个标记。可能存在重边,无自环(就是不存在 a->a,但存在环) 除了k个被标记的点,其他点都有一个糖果,并且这些点是可以任意的选择道路。被标记的点只能随机的被安排道路(只能被安排一次,下次遇到就结束)。先要求从1号屋开始,最多能拿多少糖果 分析 首先我们看...
2019-09-15
0
294
2019icpc上海网络赛-B Light bulbs 一维差分+离散化
一维差分 对于区间[l, r],我们有 num[l] ++;num[r + 1] --;//差分 for(int i = 1; i <= n; i ++) num[i] += num[i - 1];//做前缀和 题意 有n个灯,m次操作,每次操作有两个参数l,r,其意义是对区间[l...
2019-09-15
0
493
hdu 6599 I Love Palindrome String hash+PAM
题意 给一个字符串,让我们找每个长度的子串中,是super串的个数。(类似双倍回文) 分析 我们对原串建立一个PAM,这样我们可以统计每种回文串出现次数,在用hash判断是不是super串 最后在统计一下就ok #include <bits/stdc++.h> using nam...
2019-09-13
0
339
PAM-回文自动机-模板
个人理解 回文自动机顾名思义,是解决回文串相关问题的。其又称回文树。树上的每个节点对应串中的一个回文串。树根有两个,分别为0和1。0是所有偶回文的树根,1是所有奇回文的树根。在树上父子之间长度差2。类似ac自动机,回文自动机也有相应的fail指针。其指向当前编号的最长回文后缀。 #include...
2019-09-11
0
413
manacher ——学习
回文串 形如aaa,aa,aba之类的就是回文串,字符串关于某个位置中心对称。反之,abcd不为回文串 对于字符串str,现有个O(n)范围求出以每个位置为中心的最长回文半径——manacher manacher 正常的求每个位置的最长回文半径,我们用暴力,复杂度是O( ...
2019-09-10
0
339
队列优化dijstra---板子
留个板子 2019 南昌网络赛B 题意 v个点,e条边(可能重边,无影响),救火英雄在s点,剩下的k个救援队在k个位置,现在要求救火英雄对所有点的最短路的最大值乘1/c与k个救援队对所有点的最短路,取最小值输出(救火英雄要输出没乘1/c之前的) 分析 我们直接跑两边dijstra就行了,第一...
2019-09-09
0
371
2019 ccpc 网络赛——hdu-6704-K-th occurrence
hdu-6704 题意 首先给了我们一个字符串,姑且命名为文本串,然后有q个查询,对于每个查询,包含两个数l,r 询问在文本串l到r这段子串在文本串中第k次出现的首字母的位置,不满足输出-1 分析 我们首先可以想到用ac自动机,对所有查询建立一个ac自动机,然后把文本串放上面跑。可是现实打击...
2019-09-06
0
390
对二维前缀和的离线处理——2019南京网络赛A
二维前缀和 正常来说,我们处理二维前缀和需要开一个二维数组a[N][N],然后对于覆盖区间(x1, y1)(左下角)到(x2, y2)(右上角) a [ ...
2019-09-04
0
295
首页
上一页
1
2
3
下一页
末页