三木成森
三木成森
全部文章
分类
ac自动机(1)
codeforces(1)
前缀和(2)
后缀(1)
图论(1)
字符串(2)
数据结构(4)
数论(7)
神奇的c++(2)
自动机(1)
归档
标签
去牛客网
登录
/
注册
三木成森的博客
全部文章
(共22篇)
后缀数组-学习
## 后缀数组(suffix array) 求的是每个后缀的排名,我们可以使用倍增法跟DC3,前者时间复杂度O(nlogn),后者O(n) 本文只考虑倍增法 然后我们定义了一些数组 sa[i]: 排名为i的后缀的位置 tp[i]: 第二关键字,性质同sa[i] rak[i]: 第i个后缀的排名 ta...
2019-08-28
0
268
lowbit理解
我们在树状数组中可以遇到lowbit这个函数,他的用处是找最低位1的,一般写成(x & -x)形式。 原理 我们知道在计算机中二进制是以补码存储的。 对于x(x>0),我们知道他的补码就是他的本身,但-x怎么求呢 对于整数x, ...
2019-08-20
0
361
二次剩余-学习
二次剩余 形如: x 2 ≡ d ...
2019-08-19
0
319
Codeforces Round #579 (div3)
Codeforces Round #579 (div3) A 由于数据范围很小,我们可以直接枚举每个点,然后在向两边遍历去匹配 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef un...
2019-08-15
0
429
ac自动机——学习
简介 ac自动机是一种有确定限状态自动机 大众的理解就是在字典树上跑kmp 前置知识点 kmp, 字典树 正题 我们知道kmp是模式串与文本串进行匹配的算法,即两个串之间匹配。那我们思考这样一个问题。如果模式串有多个,文本串有一个,如何算出每个模式串在文本串上的匹配。按原有思维,我们需要对...
2019-08-04
0
459
二分递归求等比数列前n项和
2019河北省大学生程序设计竞赛(重现赛)B 我们假设有一个等比数列: a[n] = q ^ n 那么 S[n] = q ^ 1 + q ^ 2 + q ^ 3 …… + q ^ n 正常情况我们有 S[n] = q * (1 - q ^ n) / (1 - q) 若我们需要求的是 S[n] % m...
2019-05-25
0
459
std::lower_bound与std::set::lower_bound
在使用set的前提下,std::set::lower_bound更快
2019-05-14
0
325
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
316
函数模板
根据提供的类型返回相应的类型 template<typename T> void o(T x) {cout << x << endl;} C++模板
c++
2019-04-16
0
298
快速幂
理解 一般的我们求a^b可以跑一个for或者pow函数,这种在遇到大的数据范围很浪费时间或者存不下。 这时候就可以使用快速幂进行求解 快速幂 快速幂使用了二进制的思想,假如b=11 二进制 1011 快速幂的作用就是给1与1之间的距离缩短了 int p_pow(int a,int b,int...
数论
2018-11-26
0
345
首页
上一页
1
2
3
下一页
末页