归并排序，简而言之就是将两个内部顺序已经确定的集合进行合并，使得合并后的集合仍然有序 那么对于一个无序集合，就需将其递归到最底层从底开始回归上一层，这样不停地将每个集合内部归并而有序。   那么对于一个集合的逆序对该如何求呢？ 比如集合{5,4,3,2,1}逆序对为4+3+2+1 = 10 那么对于归并排序的求解过程：第一层： 1.1：5 4 3 1.2：2 1 第二层： 2.1.1： 5 4 2.1.2： 3 2.2.1： 2  2.2.2： 1   第三层： 3.1.1.1 ：5 3.1.1.2 ：4 3.1.2： 3 3.2.1： 2  3.2.2：...

字符串哈希就是将一个字符串映射成一个P进制的数，然后用前缀记录下来，当你查询某个字符串的哈希值时，只要用前缀相减就可以了。通常P取131或者13331来尽可能减少冲突，同时用unsigned long long值过大自动溢出避免手动取模 eg：s[] = "ABACBDAB"， h是前缀和，v是字符的值 h[1] = v[A]， h[2] = h[1] * P + v[B]，h[3] = h[2] * P + v[A] ... h[7] = h[6] * P + v[A]，h[8] = h[7] * P + v[B]   当求某个子串的哈希值时，由于我们这里看到的是...

题意: 给你两个数a和b(1 <= a, b <= 1e4)，i-a>=0 且i-a为白，则i为白，i-b>=0且i-b为白，则i为白， 否则为黑。 其中初始化0为白。 问你是否有无穷个黑。 题解： 对这个问题，我们只需要简化： 如果并没有无限个黑，必然是存在某个数后，之后的所有数都是白色 那么必然有一个长度为b - a + 1的区间，区间中的所有数都是白色，那么之后的所有数都是白色 同时，对于任意一个白色的数c，其必然满足：ax + by = c ，gcd(a,b) | c 所以这就要求这个b - a + 1长度的区间内的数必须全部可以被gcd(a...

题意： n点m边无向图，无自环，无重边 给定的图可以断开连接 下面我们有一个定义：让v1和v2为两个不连通的顶点非空子集 函数f(v1, v2)为真当且仅当下面所有情况否满足： 1. 顶点集v1中的两点无边连接 2.顶点集v2中的两点无边连接 3.对任意在v1中的点和v2中的点，两点间有一条边 创造三个顶点集v1，v2，v3满足如下条件 1.所有顶点集不空 2.每个顶点只能在一个顶点集中 3.f(v1, v2) f(v2, v3) f(v3, v4)都为真 有可能创造这个顶点集吗，如果可能，请打印每个顶点的匹配顶点集 简而言之：就是创建一个三分图。   思路： 存边的时候，注意下可...

一、O(n^2)暴力，对于第i个元素，找到前i-1个元素中小于第i个元素的当前最长上升子序列。 二、O(nlogn)二分，维护一个递增序列，对于第i个元素，如果其大于这个递增序列的最大值，将其加入序列末尾 否则用第i个元素置换掉递增序列中最小的大于第i个元素的元素   最长上升子序列的输出： 一、对于O(n^2)暴力，记录一下子序列中，每个元素的前置元素，然后逆序得到答案。 二、对于O(nlogn)二分，要注意的是我们维护的递增序列只能得到最长上升子序列的值，而不一定能得到正确的子序列，因此要另寻他路。   给出两者的综合代码：   /* 字典序最小的Lis Author: ...

1. 范围较小. 求 ，共n组询问。 1 ≤ n ≤ 10000, 1 ≤ b ≤ a ≤ 2000 暴力使用杨辉三角即可。f[i][j] = f[i - 1][j - 1] + f[i - 1][j]   2. 仍求第一问的值，但是1 ≤ b ≤ a ≤ ，预处理出的逆元和阶乘展开即可。   3. ，共n组询问。1 ≤ n ≤ 20, 1 ≤ b ≤ a ≤ ，1 ≤ p ≤  （eg：hdu3944） Lucas定理 ： 故时间复杂度为 (1)为递归次 (2)为计算每次组合数的时候最多P次 (3)为每次快速幂的次数

题意： 问你 g c d ( a , m ) = g ...

1.欧拉函数证明 欧拉函数：对于一个正整数n，在1~n中与n互质的数的个数 对于正整数 n n n， p 1 , p ...

思维题果然nb. 题意：给你一个 n ∗ m n*m n∗m矩阵，可以对每一列进行上移，或者对每个元素进行修改 使得最后的矩阵满足 q [ i ...

被卡两小时直接自闭，还是想太多了。传送门 题意： 给你一个长度为 n n n的序列，共有 n n n个人来取数，每次只能在序列当前的首尾取数。你排在第 m ...

之前遇到矩阵斐波拉契没了解过，现在算是稍微理解了点。 前置知识： 斐波拉契通项： f [ n ] = f [ n ...

A: 题意： A和B猜拳，问A获胜次数 题解： 求获胜次数，只需关心获胜次数，依次判断A出石头剪刀布的获胜次数即可，注意 3 e 9 3e9 3e9爆 i n t ...

LCS的输出： 一、对于 O ( n 2 ) O(n^2) O(n2)暴力，记录一下子序列中，每个元素的前置元素，然后逆序得到答案。 二、对于 ...

线性基计数题. 题意： 给定一个序列， q q q次询问中每次给定 l l l和 x x x，问你在序列 ...