阿哲不是吧

分类

未归档(4) 算法(9) 题解(28)

/ 注册

全部文章（共41篇）

AC自动机

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

AC自动机

2020-10-10

0 354

P2852 [USACO06DEC]Milk Patterns G

题目描述 Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although ...

后缀数组

2020-10-09

0 548

P2870 [USACO07DEC]Best Cow Line G

题目描述 Farmer John 打算带领 NN（1 \leq N \leq 5 \times 10^51≤N≤5×105 ）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。今年，竞赛委员会在接受报名时，采用了一种新的登...

后缀数组

2020-10-08

0 462

[JSOI2007]字符加密

题目描述喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字...

后缀数组

2020-10-08

0 408

后缀数组（后续）

@[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 471

后缀数组

子串：从原串中选取连续的一段，即子串空串也是子串后缀：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 465

求约数个数的和

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

约数

2020-10-07

0 376

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

参考博客参考博客参考博客预备知识点：大于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 734

珂朵莉的约数

来源：牛客网：题目描述珂朵莉给你一个长为n的序列，有m次查询每次查询给两个数l,r 设s为区间[l,r]内所有数的乘积求s的约数个数mod 1000000007 输入描述:第一行两个正整数n,m第二行一个长为n的序列之后m行每行两个数l和r输出描述:对于每个询问，输出一个整数表示答案示例1输...

莫队算法

2020-10-07

1 524

数列互质(莫队算法)

数列互质题目描述给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] ,r[i] , k[i])。求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i]互质（最大公约数为1）。...

莫队算法

2020-10-07

4 665