ACM个人知识点记录

数论

链接

A*算法入门

启发式搜索

链接

康托展开

数码问题，全排列，hash问题

链接

并查集

建一个数组，里面存的是爸爸值，当爸爸值是自己时，就是祖宗。

路径压缩，每次新建几个，通过爸爸找到祖宗，直接存祖宗值。

单调栈

利用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置

链接

线性动态规划

####1.lcs问题
######dp[i][j]=min( dp[i-1][j-1]+? ,dp[i][j-1]+k, dp[i-1][j]+k)
####2.双塔问题
#####dp[i][j]表示前i个形成的差值为j的双塔中较矮塔的高度。
####3.lis问题（最长上升子序列）
#####应用单调栈解决
####4.状态压缩
#####用二进制表示选与不选的问题
#####存在无用状态时想办法进行等价消除减小复杂度
####5.插头dp
#####解决联通性的棋盘dp的问题
#####特点是从一个格子推到下一个格子，利用只有六种状态的插头进行状态转移
#####链接
####6.vijos p1616
将两个任意交换的换成 j变成z和z变成j两个过程 f[i][j][k]表示第i个元素转换j的次数为j，转换z的次数为k的最大值
##网格动态规划
#####1.记忆化搜索
#####2.多线程dp
##树形动态规划
#####1.二叉树（选课）
dp[i][j]表示第i个节点分配j个元素，状态转移方程dp[i][j]=max(dp[i][k],dp[i][j-k])
k=0~j
#####2.多叉树可以转化为二叉树状态方程与上面类似
##splay伸展树
特点：有6种旋转情况，都不改变中序遍历，可以用中序遍历表示序列。
旋转操作的主要目的是实现伸展(splay)，将任意一个知道位置的元素移到树顶部
#####1.单点操作（宠物收养所）
1.普通的二叉排序树共有的查找结点功能
寻找第k号元素 （k表示在序列中排第几号元素）。
建树保证了左子树的序列号小于根，右子树序列号大于根，直接二分查找即可。
2.普通的二叉排序树共有的插入结点功能
3.将一个节点删除通过splay操作移到顶部再删除，
删除时寻找根的左子树的最右边的节点移到顶部的位置替换根节点
4.寻找节点的前驱后驱，将目标节点splay到顶部，
左子树的最右节点即为前驱，右子树的最左节点即为后驱 #####2.区间操作（Robotic Sort ）
1.寻找闭区间**[l,r]，
通过寻找第l-1号元素并spaly到根节点，寻找第l-1号元素并spaly到根节点的左节点。
因为splay操作不改变节点的顺序（中序遍历不改变），
所以根节点的左节点的右子树即为需要操作部分[l,r]*区间。
2.对区间的翻转操作
将表示区间的子树的所以左右节点交换即可。
还可以通过懒惰标记，将当前节点进行操作后，将标记下传到子树。
如果有操作需要经过子树，则先下传子树的标记再遍历。
维护序列的k号元素，即翻转后造成了区间中元素位置的变化请移步
3.对区间的值的更改 请移步
##块状链表
##N!分解质因数
链接
##原根
1.有原根的数只有2,4,pn,2pn(p为质数,n为正整数)。
2.一个数的最小原根的大小是O(n0.25)的。
3.如果g为n的原根，则gd为m的原根的充要条件是(d,φ(n))=1；
4.如果n有原根，它的原根个数为φ(φ(n))。
5.一个数n的全体原根乘积模n余1
6.一个数n的全体原根总和模n余μ(n-1)(莫比乌斯函数)
##欧拉函数
#####线性筛求欧拉函数
链接
##威佐夫博弈
#####a=floor(k(1+sqrt(5))/2)

b=a+k;

##nim博弈
#####a[1]a[2]a[3]^a[4]…a[n]=0先手败
#####a[1]a[2]a[3]^a[4]…a[n]！=0先手胜