题目描述 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 he can't predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality. To perform a rigorous study,...

题目描述 Farmer John 打算带领 NN（1 \leq N \leq 5 \times 10^51≤N≤5×105 ）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。 今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。 FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。 他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队...

题目描述 喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。 例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？ 输入格式输入...

@[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 = 后缀suf(i)的排名r = 后缀suf(j)的排名结论：lcp(suf(i),suf(j)) = min(Height[l+1]...Height[r] )即两个后缀的lcp = 它们排名区间中Height的最小值维护rmq 求Height数组 暴力求O(N^2^) for i =1-N l =ran...

子串：从原串中选取连续的一段，即子串空串也是子串后缀：suf(k)为s(k....n)构成的子串任何子串都是某个后缀的前缀最长公共前缀 lcp(suf(i),suf(j)) 问题： 将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序 暴力sort N^2^ logN二分+hash :Nlog^2^Ncmp函数中二分suf(i)和suf(j)的lcpreturn s[i+|lcp|] < s[j+|lcp|]------- 以上为暴力做法进入正文：SA[1]排序第1的后缀的开始位置Rank[i]=后缀suf(i)的排名Rank[sa[l]] = lsa[Rank[i]...

今天一下午都在研究约数的各种性质。。。求约数个数的和可以用线性筛的方式，线性求解的方式，这应该是最快的[数论]线性筛——约数个数与约数和除此之外还有代码更简便方法：对应的例题 方法一： #include <iostream> using namespace std; int OneToNumGcdCount(int num) { int ans = 0; for (int i = 1; i <= num; i++) { ans += num / i; } return ans; } int main() { int t1, t2, t; cin >> t1 &gt...

参考博客参考博客参考博客预备知识点：大于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]; int cnt; void initial() { cnt=0; for (int i=2 ; i<N ; ++i) { if (!mark[i]) prim[cnt++]=i;//存放素数 for (int j=0 ; j<cnt && i*prim[j]<N ;...

来源：牛客网： 题目描述 珂朵莉给你一个长为n的序列，有m次查询 每次查询给两个数l,r 设s为区间[l,r]内所有数的乘积 求s的约数个数mod 1000000007 输入描述:第一行两个正整数n,m第二行一个长为n的序列之后m行每行两个数l和r输出描述:对于每个询问，输出一个整数表示答案示例1输入复制 5 5 64 2 18 9 100 1 5 2 4 2 3 1 4 3 4 输出复制 165 15 9 45 10 备注:对于100%的数据，有n , m <= 100000 , a[i] <= 1000000 题解： 莫队+数论（约数个数）很容易看出是莫队的题，个人认为难点在于...

数列互质 题目描述  给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] ,r[i] , k[i])。 求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i]互质（最大公约数为1）。  输入描述:第一行，两个正整数 n , m (1 ≤ n, m ≤ 50000)。第二行，n 个正整数 a[i] (1 ≤ a[i] ≤ n)描述这个数列。接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 ≤ l[i] ≤ r[i] ≤ n, 1 ≤ k[i] ≤ n)，...

数据结构题 题目： 问在区间[l,r]和[l1,r1]内x的出现次数的乘积是多少？ 题解： 莫队算法的模板题关于莫队算法你可以参考这个我这里简单的说说我对莫队的理解：莫队是一个优雅的暴力，就是将原本复杂度不能过的程序进行优化，莫队是通过分块来实现如果暴力做这个题，查询区间[l,r]内x的数量我们可能就从头开始搜查，按照题目给的数据来搜查，但其实我们可以这样优化,比如题目给的查询区间[3,4],[2,4],[1,5],我们可以先查询[1,5],然后顺势查询[2,4],最后[3,4]，而非从头开始，这样就省了不少时间。那如何实现这个？我们可以对整体进行分块，然后按照所分的快进行排序，尽可能实现查询...

之前就学过一点java，但太久没用知识点早就还给书本，之前在实验室搞到一本java的书，今天来重新温习一下java的语法大部分和c++语言是一样的，入门非常快，所以在这里基础语句的用法就省略了输出： System.out.println() 输出信息后追加一个换行 System.out.print()输出之后不追加换行 string： str.IndexOf()//返回搜索的字符或字符串首次出现的位置 str.lastIndexOf()//返回搜索的字符或字符串最后一次的位置 charAt()//可将指定索引处的字符返回 trim()//返回字符串的副本，忽略前导空格和尾部空格 startsW...

来源：牛客网： 题目描述 珂朵莉给了你一个序列，有n×(n+1)/2​ 个子区间，求出她们各自的逆序对个数，然后加起来输出输入描述:第一行一个数 n 表示这个序列 a 的长度 之后一行 n 个数，第i个数表示ai 输出描述:输出一行一个数表示答案示例1输入复制 10 1 10 8 5 6 2 3 9 4 7 输出复制 270 示例2输入复制 20 6 0 4 5 8 8 0 6 6 1 0 4 6 6 0 0 7 2 0 5 输出复制 3481 备注:  对于100%的数据，n <= 1000000 ,0 <= 序列中每个数 <= 1000000000  题解：  如果一个逆...

来源：牛客网： 题目描述 一个只含数字的字符串，q次操作，每次操作将第i位数字改为x，每次操作后，统计长度在[l, r]之间且首数字大于尾数字的子串的个数。 输入描述:第一行一个只含数字的字符串；第二行3个整数q, l, r；接下来q行，每行两个整数i, x。输出描述:输出q行，每行一个整数，表示长度在[l, r]之间且首数字大于尾数字的子串的个数。示例1输入复制 585605 2 2 4 1 6 4 2 输出复制 7 8 备注:  设字符串长度为n则： 1 <= n <= 100000; 1 <= q <= 100000; 1 <= l <= r <...

take题解参考 题目描述  Kanade has n boxes , the i-th box has p[i] probability to have andiamond of d[i] size. At the beginning , Kanade has a diamond of 0 size. She will open theboxes from 1-st to n-th. When she open a box,if there is a diamond init and it's bigger than the diamond of her , she will replace...