题意： 一个长为n的河，中间有m个木台，每个木台长为ci，你想从河的左岸跳到右岸，每次你可以往前跳的范围为[x + 1, x + d]，你可以移动木台使得可以跳跃，但是木台之间的相对顺序不得改变。 现在问你是否可以跳到右岸？如果不可以输出NO，如果可以输出YES以及河的每个单元所对应的木台序号，如果没有对应木台则为0。   题解： 先将所有木台统一放置到河的最右岸，每个木台之间无空隙，最后一个木台紧贴右岸。 然后判断每一次最大跳跃长度下是否可以成功跳跃（即跳到木台或者右岸上） ok：输出 no：从最左边的木台开始将其移动到单次跳跃可以到达的最远位置 如果木台放置完仍不能到达右岸，那么不可跳到右...

归并排序，简而言之就是将两个内部顺序已经确定的集合进行合并，使得合并后的集合仍然有序 那么对于一个无序集合，就需将其递归到最底层从底开始回归上一层，这样不停地将每个集合内部归并而有序。   那么对于一个集合的逆序对该如何求呢？ 比如集合{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： 1   第三层归并后： 4 5 3 ...

字符串哈希就是将一个字符串映射成一个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]   当求某个子串的哈希值时，由于我们这里看到的是 &qu...

题意: 给你两个数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, b)整除   1...

题意： 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: solego *...

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   c   d   (   a   +   x   ,   m   )    gcd(a, m) = gcd(a + x, m)   gcd(a,m)=gcd(a+x,m)的话，有多少     x    x   x满足这种情况？ 其中      1   ≤   a   ,   m   ≤   1    0   10     1 ≤ a, m≤10^{10}   1≤a,m≤1010，     0   ≤   x   ＜   m    0 ≤ x＜m   0≤x＜m 题解： 令     k   = ...

1.欧拉函数证明 欧拉函数：对于一个正整数n，在1~n中与n互质的数的个数 对于正整数     n    n   n，       p   1    ,    p   2    ,   ⋯    ,    p   k     p_1,p_2, \cdots,p_k   p1​,p2​,⋯,pk​是n的k个质因子 欧拉函数的公式如下：      p   h   i   (   n   )    phi(n)   phi(n) =      n    n   n      ×    \times   × (1 -       1    p   1      \frac{1}{p_1}   p1​1...

思维题果然nb. 题意：给你一个     n   ∗   m    n*m   n∗m矩阵，可以对每一列进行上移，或者对每个元素进行修改 使得最后的矩阵满足     q   [   i   ]   [   j   ]   =   (   i   −   1   )   ∗   m   +   j   ,   1   ≤   i   ≤   n   ,   1   ≤   j   ≤   m    q[i][j] = (i - 1) * m + j, 1 ≤ i ≤ n, 1 ≤ j ≤ m   q[i][j]=(i−1)∗m+j,1≤i≤n,1≤j≤m 每上移一次某列或者修改某个元素后，操作数...

被卡两小时直接自闭，还是想太多了。传送门 题意： 给你一个长度为     n    n   n的序列，共有     n    n   n个人来取数，每次只能在序列当前的首尾取数。你排在第     m    m   m位，同时你有     k    k   k次控制别人选择数的机会，现在问你合理操作后至少可以得到的最大值为多少？ 题解： 到你选择的时候，区间长度为     n   −   m   +   1    n - m + 1   n−m+1，前     m   −   1    m - 1   m−1个人选择数的情况才会对你选择的数有影响，由于控制次数的限制，故最多有效限制次数为    ...

之前遇到矩阵斐波拉契没了解过，现在算是稍微理解了点。 前置知识：  斐波拉契通项：      f   [   n   ]   =   f   [   n   −   1   ]   +   f   [   n   −   2   ]   ,   n   ≥   3    f[n] = f[n - 1] + f[n - 2], n ≥3   f[n]=f[n−1]+f[n−2],n≥3 斐波拉契——矩阵形式 由于：       [     <mstyle displaystyle="false" scriptlevel="0">   f   [...

A: 题意： A和B猜拳，问A获胜次数 题解： 求获胜次数，只需关心获胜次数，依次判断A出石头剪刀布的获胜次数即可，注意     3   e   9    3e9   3e9爆     i   n   t    int   int 代码： #include<bits/stdc++.h> using namespace std; int main() { int a, b, c, x, y, z; cin >> a >> b >> c >> x >> y >> z; long long sum = 0; if(a...

LCS的输出： 一、对于     O   (    n   2    )    O(n^2)   O(n2)暴力，记录一下子序列中，每个元素的前置元素，然后逆序得到答案。 二、对于     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn)二分，要注意的是我们维护的递增序列只能得到最长上升子序列的值，而不一定能得到正确的子序列，因此要另寻他路。 /* 字典序最小的Lis Author: solego */ #include<cstdio> #include<algorithm> using namespace std...