三木成森
三木成森
全部文章
数据结构
ac自动机(1)
codeforces(1)
前缀和(2)
后缀(1)
图论(1)
字符串(2)
数论(7)
神奇的c++(2)
自动机(1)
归档
标签
去牛客网
登录
/
注册
三木成森的博客
全部文章
/ 数据结构
(共4篇)
2019 icpc 沈阳网络赛 B Dudu's maze 并查集
题意 我们已知n个点,m条边,k个标记。可能存在重边,无自环(就是不存在 a->a,但存在环) 除了k个被标记的点,其他点都有一个糖果,并且这些点是可以任意的选择道路。被标记的点只能随机的被安排道路(只能被安排一次,下次遇到就结束)。先要求从1号屋开始,最多能拿多少糖果 分析 首先我们看...
2019-09-15
0
396
2019 ccpc 网络赛——hdu-6704-K-th occurrence
hdu-6704 题意 首先给了我们一个字符串,姑且命名为文本串,然后有q个查询,对于每个查询,包含两个数l,r 询问在文本串l到r这段子串在文本串中第k次出现的首字母的位置,不满足输出-1 分析 我们首先可以想到用ac自动机,对所有查询建立一个ac自动机,然后把文本串放上面跑。可是现实打击...
2019-09-06
0
471
lowbit理解
我们在树状数组中可以遇到lowbit这个函数,他的用处是找最低位1的,一般写成(x & -x)形式。 原理 我们知道在计算机中二进制是以补码存储的。 对于x(x>0),我们知道他的补码就是他的本身,但-x怎么求呢 对于整数x, ...
2019-08-20
0
473
2019南昌网络赛 J. Distance on the tree
我们对于每个节点建立到根节点的线段树,即我们建立一颗主席树来维护 对于每个查询,答案是query(1, x) + query(1, y) - 2 * query(1, lca(x, y)) #include <bits/stdc++.h> using namespace std; ty...
2019-04-25
0
398