阿哲不是吧

算法

未归档(4) 题解(28)

/ 注册

全部文章 / 算法（共9篇）

AC自动机

AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的。@[toc] 解决：多模式匹配问题匹配问题：有多个不同的模式串s[1...N]给定长度=M的目标串t，求每个模式串s[i]总共在t中出现了多少次跑N遍kmp 字典树：对所有的模式串s[1...N]构建trie字典树的根...

AC自动机

2020-10-10

0 479

后缀数组（后续）

@[toc] 后缀数组 Height 利用后缀数组快速求出2个后缀的lcp长度lcp:最长公共前缀lcp(suf(i),suf(j))记Height[l] = 排名第(l-1)后缀和排名第l后缀的lcp长度Height[l] = lcp(suf(SA[l-1]),suf(SA[l])) l = 后缀...

后缀数组

2020-10-08

0 593

后缀数组

子串：从原串中选取连续的一段，即子串空串也是子串后缀：suf(k)为s(k....n)构成的子串任何子串都是某个后缀的前缀最长公共前缀 lcp(suf(i),suf(j)) 问题：将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序暴力sort N^2^ logN二分+has...

后缀数组

2020-10-08

0 594

求约数个数的和

今天一下午都在研究约数的各种性质。。。求约数个数的和可以用线性筛的方式，线性求解的方式，这应该是最快的[数论]线性筛——约数个数与约数和除此之外还有代码更简便方法：对应的例题方法一： #include <iostream> using namespace std; int On...

约数

2020-10-07

0 511

[数论]线性筛——约数个数与约数和

参考博客参考博客参考博客预备知识点：大于1的数n可以分解质因数：n=p1^a1^×p2^a2^×p3^a3^…pk^a^n的约数的个数是(a1+1) * (a2+1) * (a3+1)......(ak+1)我们先用线性筛来筛出素数 bool mark[maxn]; int prim[maxn]; ...

约数

2020-10-07

0 910

Java的学习与java大数运算

之前就学过一点java，但太久没用知识点早就还给书本，之前在实验室搞到一本java的书，今天来重新温习一下java的语法大部分和c++语言是一样的，入门非常快，所以在这里基础语句的用法就省略了输出： System.out.println() 输出信息后追加一个换行 System.out.print(...

java大数

2020-10-07

0 568

求树的直径

欢迎来踩本人博客树的直径：就是树上最长路方法：求两边DFS即可步骤：1.从任意一点进行dfs，然后找到一个最长路径，记录最远点u2.然后从u再进行dfs，找最长路径，记录一点v。（u，v）就是树的直径证明：可以看这个视频的第27：00（求树直径的原理和证明） [video(video-iMl9...

树的直径

2020-10-01

0 571

莫比乌斯反演+例题

问题引入：添加链接描述给定N和M和D，求满足1<=x<=N,1<=y<=M且gcd(x,y)=D的点对(x,y)的个数1<=N,M<=1000000 莫比乌斯函数 μμ(n) = 1 , n=1μ(n) = (-1)^k^, n=p1 * p2 * ... ...

莫比乌斯反演

2020-09-29

0 569

序列自动机

介绍子串：串中任意个连续的字符组成的子序列称为该串的子串子序列：子序列中的字符在字符串中不一定是连在一起的，而是删除其中若干个，但子序列一定是单调的简单说就是子序列不连续，子串连续序列自动机可以在复杂度为O（n）下判断一个串是不是另一个串的子序列序列自动机的本质其实就是空间换时间，因为暴力做...

序列自动机

2020-09-26

0 396