区间
选择不相交区间
区间选点问题
区间覆盖问题(对end的判断一定要放在while循环内部!) 2022.2.2
- 构造哈夫曼树
- 非递归方式求编码的两种方式:从根节点顺向求，从叶子节点逆向求
- 递归方式求编码的两种方式：从根节点顺向，从叶子节点逆向
- 根据给定的编码，解码对应的字符，这里直接用权值代替字符
- 总结：
对于非递归方式顺向求编码的方式类似于后序遍历二叉树，设置一个状态变量flag来记录节点的子节点是否都访问过了，以便回溯，访问该节点的父节点。
数论
发表于
|
更新于:
a,b的最小公倍数和最大公因数
- 分块筛法，将要筛选的区间进行分块，对每个块进行处理，这样就不用一直保存整个范围的vis数组，利于cpu更好地处理缓存.
- 减少内存的占用,采用
位级压缩，但这种压缩方法会使这些位的操作复杂化。任何位上的读写操作都需要多次算术运算。这是一种以降低内存占用，从而降低执行效率的方法 - 只筛选奇数.
Euler筛
扩展欧几里得定理
- ax+by=gcd(a,b) 归纳法证明？
- 二进制求最大公因数(校赛)
- 倒水问题(贝祖定理)
比赛数论例题
洛谷100月赛 Q1
- 思路：如果一个数的因子有K个,那么使得这个数最小的方案是2^k,也就是全是2.首先想到两个特殊值4,9。
- 先说4，可以因式分解为2x2.再说9，可以分解为3*3.
- 归纳出，如果一个数的质因子大于5小于9，那么一定存在一个数小于他，并且因子大于他，因为大于5小于9的这个因子可以写成2x2.举个例子，14=2x7,一定存在一个数,2x2x2=8.
- 如果一个数的质因子大于等于9，那么一定存在一个数小于他，并且因子数大于他，因为这个质因子肯定没有2x2x2这个因子数多。举个例子，18这个数可以写成3x3x2,3x3可以优化成2x2x2，那么这个数就是2x2x2x2=16.
CodeForce 767 Q2
- [l,r]的连续整型数组，最多操作k次，每次将数组中两个数字相乘，问是否最终存在一个数组，整个数组的gcd大于1.
- 思路：可以假设最终的数组的gcd是多少。经过找规律可以发现，如果最终的gcd是x，最终长度为N的数组剩下的数字的个数为N/x(素数筛的原理)，可以发现当最终数组的x=2时，可以使得数组剩下的数更多，需要的k更小。
ACM校赛Q1
- 思路：找素数的规律(素数的定义)
AcM校赛QL
- 思路：根据题设条件变形，再根据a/gcd(a,b)+b/gcd(a,b)=2k，两个数为奇数，而且因子2的个数相同(否则不可能为奇数)。
一道有意思的欧拉筛题 牛客KY7
- 尽管题设条件给的是[1,1e9],但是并不用将欧拉筛的取值范围设置为1e9,因为题设并没有要求我们找出1e9以内的所有质数，只用找出质因子的个数即可。
- 那为什么是1e6呢？因为就算一个数存在两个质数1e6*1e6,已经超过了1e9的范围。例如，夸张一点假设，如果将primes[]数组大小改为1e1,此时就不成立了，存在一个数字有两个因子17x17=289，这样就筛不出正确的因子个数了。
- 测试用例举例：799043235，分解因式3x5x5x29x1259x1459.如果此时将N设置为1e3,很明显会出错.
欧拉函数
- 实现过程：在分解质因数的过程中求出欧拉函数
递推
卡特兰数
- 通过两种思路得到的递推方式得到一个更为简洁的递推公式：f(n+1)=(4n-6)/f(n).
组合数与杨辉三角
- 根据杨辉三角的性质得出递推式: C[i][j]=C[i-1][j]+C[i-1][j-1]
- 凡是需要提前求出C(n,i)值，都可以利用杨辉三角
UVa12034
- 两种思路：第一种先确定第一名，依次第二名…第n名。
- 第二种思路，dp[i][j]:i匹马，j个名次的所有方案=(dp[i-1][j-1]+dp[i-1][j])*j.也有点类似杨辉三角.i-1匹马形成j-1个名词，再来一匹马，与之前的马混用名次，j种方案。其次，i-1匹马形成j-1个名次，再来一匹马，新形成一个名次，也是j种方案。