抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

acwing算法

请设置文章作者

发布于：Jan 1, 2000
次浏览

Abstract

Preface

Algo

贪心

  • 区间问题
    • 套路:
      1. 左端点排序或右端点排序
    • 证明套路: ans <= cnt + ans >= cnt => cnt = ans得整算法正确性
  • 区间分组问题
    • 套路:
      1. 左端点排序或右端点排序
      2. 可以使用最小堆等数据结构, 用一个”代表者”代替整个组, 就不用维护整个map
    • 证明套路: ans <= cnt + ans >= cnt => cnt = ans得整算法正确性

搜索与图论

  • 最短路径问题
    • 单源
      • 不存在负权边
        • 朴素dijkstra O(n**2)
        • 堆优化dijkstra O(m*logn)
      • 存在负权边
        • bellman-ford O(mn)
        • spfa 一般O(m), 最坏O(mn)
    • 多源
      • floyd算法

图的邻接表表示

1
2
3
4
5
6
7
8
9
// 添加a->b的链接表, 权值为c
// 这里用数组模拟, idx就相当于内存位置
// h[]是整个"结构体"的如何, 存放编号到内存地址(idx)的映射
void add(int a, int b, int c) {
  e[idx] = b; // 添加新节点
  w[idx] = c; // 添加节点权值
  ne[idx] = h[a]; // 头插链边
  h[a] = idx++;  // 更新头节点
}

bellman-ford

可以处理有负权边的最短路问题

  • algo: 单源负权边最短路问题, 多次遍历所有边即可。
    • TODO: 待证明
  • 更新只用上一次的结果, 防止使用修改的后的进行计算
  • 三角不等式
  • 之所以可以解决负边问题是因为循环次数有限

spfa算法

  • 同样是解决存在负权边的最短路径问题。
  • 是对bellman-ford的优化, bellman不假思索遍历所有, 但实际上如果dist没变那依赖它跳转的后续就不会改变
    • 所以只需要在dist缩小时才将它加入队列

举个例子, bellman-ford算法伪代码如下:

1
2
3
for 所有点k(每个点都可能称为中介跳转):
	for 所有点i(枚举所有起点, 使用中介点k relax):
		relax(dist)

spfa伪代码如下

1
2
3
4
5
6
exist[1] = true; 	// 是否存在队列中
for 所有有在队列q中的点k: 	// 使用一个队列保存dist缩小后的点
	exist[k] = false; 	// 清除记录, 后续必要时会重新添加
	for 所有k的邻接点i(枚举所有起点, 使用中介点k relax):
		if 更新:
			if !exist[j] q <- j; // 如果已经在组列中就不如

spfa判断负环

原理:

  1. n个点不存在环的话只有n-1条边, 所以如果cnt[x] >= n则说明存在环路。cnt[x]表示走到x所需的边数。cnt[x] = cnt[prev(x)] + 1, 一次走一步加一边。
  2. 因为负环会让路径变小, 所以会被检测到

Floyd

解决多源最短路径问题

使用三重循环, 最外层是中间点k的枚举。

朴素Prim

求最小生成树问题。关键在于怎么求点到集合的距离, 可以通过边的两个端点判断。

TODO: https://www.acwing.com/video/287/

动态规划(dp)

01背包

01背包, 每件物品只能0次或1次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// dp[i][j] 前i个, j重量, 价值最大

// 状态表示
// 	集合: 前i件物品, 体积不超过j
// 	属性: max
// 状态计算: 不重不漏
// 	集合划分(状态转移): f[i][j] = 
// 		不选第i个 dp[i][j] = dp[i-1][j]
// 		选第i个 dp[i][j] = dp[i-1][j-w[i]] + v[i]
//
//
//
// 优化分析
// 	1. 状态转移只依赖于i-1, 所以可以滚动更新，没覆盖时就是i-1
// 	2. 因为状态转移还依赖j-v[i], 如果j从小到大那所依赖的j-v[i]历史就可能已经被覆盖

完全背包

  • 完全背包问题, 物品个数不限
  • dp[i][j], 前i, 容量刚好j
    • dp[i][j] = dp[i-1][j] + ... dp[i-1][j-n], 用0个j到用n个j的情况

最短子序列

  • dp[i][j]str1前i和str2前j比较
    • s[i] == s[j]匹配时, 可以增加dp[i-1][j-1]+1
    • s[i] != s[j]不匹配时, 继承前人状态max(dp[i-1][j], dp[i][j-1])跳过i或j

最短编辑距离: 增删改的最小次数

  • dp[i][j], str1前i编辑成str2前j所需
  • 初始
    • dp[0][i]=i不断插入, dp[i][0]=i不断删除
  • 增: i处插入dp[i-1][j]+1
  • 删: i处删除dp[i][j-1]+1
  • 改: dp[i-1][j-1]+1
  • 无: s[i]==s[j]继承dp[i-1][j-1]

上述操作取最小

石子合并

  • 自底向上
    • 最终总是右量堆石子合并
    • 而用于合并的两堆石子也是由更小的两堆合并
    • 因此从len=2开始枚举合并情况, 然后选取min/max的结果
  • “类哈夫曼问题”, 结果是区间累加

最短hamilton路径

  • 三角不等式
    • 枚举中转k, relax所有起点终点(i, j)
  • 使用bitmap判断有效
  • dp[i][state]当前再i, 节点使用情况state, 最短路径
    • 如果节点使用情况相同, 那必然要走相同的路线(因为最小)

蒙德里安的梦

  • 逐步扩展
    • 先摆横再摆竖
    • dp[i][state], 扩展到当前列i时, 状态为state时的有效摆放数
  • 状态就是整个bitmap值域的枚举
  • 预处理
    • 一个”互补表”, 枚举state1, 可以有的合法情况state2
    • 排除奇数个连续的情况

滑雪

dp + dfs

题意就是滑雪从高海拔到低海拔, 4个方向选哪个走得更远。显然, dfs, 然后一个方向就有了记录, 下次到达这点时直接用记录不dfs即可。

没有上司的舞会

树形dp, 类似小偷偷房子问题

dfs, 从根节点开始递归, 取直接孩子或不取, 每个子树都是一个”dp记录”, 所以dfs后就能动态生成记录。

dp[i][0]以i为根不选i的情况, dp[i][1]以i为根选i的情况。当前根为u, 选了u就不能选直接孩子; 没选u, 可以看max(dp[i][0], d[i][1])

数学

求约数

枚举一半, 算另一半。e.g. 枚举i那另一约数就是n/i, 注意i == n/i是只算一个

求质数

  • 质除法
    • i <= x/i
1
2
3
4
5
6
7
8
bool is_prime(int x) {
	if (x < 2) return false; 
	for (int i = 2; i <= x/i; i++)
		if (x % i == 0)  {
			return false;
		}
	return true;
}
  • 朴素筛法: 2到n枚举, 筛倍数(j += i): $n/2 + n/3 + … + n/n => O(lnn) < O(logn)$
  • 埃氏筛法: 优化朴素筛, 只筛质数的倍数就可以了。复杂度: 质数定理, 1..n中有n/lnn个质数
  • 线性筛法: 同样筛倍数，但只用最小质因子筛: 枚举质数, 是质因子就可以提前break

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
 for (int i=2; i <= n; i++) {
// 枚举所有质数, 删倍数
if (!st[i]) {
     // 存质数
  prime[cnt++] = i;
}
for (int j=0; prime[j] <= n/i; j++) {
  st[prime[j] * i] = true;
  // 如果prime[j]是因数, 因为我们从小到大枚举的，那就一定是最小质因数
  if (i % prime[j] == 0) break;
}
 }

快速幂

任何数都可以写成二进制的形式, 当然也包括指数。当写成二进制时既可以方便的利用”翻倍迭代”来求。

比如$a ^ k$, k = 5 = 0b0101, 遇到0时只翻倍, 遇到1只即翻倍有相加。

基础算法

二分

  • [left, mid], [mid+1, right]时, mid = (l+r)/2
  • [left, mid-1], [mid, right]时, mid = (l+r+1)/2
  • 当然可以用自省的算法: l + 1 == r时特判

模拟哈希表

  • 开放寻址
  • 链表

单调栈

use case: 求每个数左边最近的比它小的数

  • 思考怎么从暴力过渡到单调栈:
    • 暴力for i, for i左边找最小, i是一点点增加的, i的左边也是，可不可以就维护点结构
    • 分析一下发现如果ax > ay且x < y那么ax一定不会用到, 因为后面的i只会越走越右。所以可以把这样的ax全都删掉

滑动窗口

一个滑动窗口, 每次滑一位, 每次都要输出最大最小值。

两个单独栈, 然后注意处理已经脱离窗口的元素即可。

小根堆

每个点都小于左右孩子

  • 存储: 数组存, 下标从1开始
    • 2x左儿子, 2x+1右儿子
  • 由两基本操作组成: down, up
    • down(x): 上层节点变大了要下压。x跟最小的孩子换
    • up(x): 下层节点变小了要上提。跟父节点比, 判断是否向上
  • 建: O(n)建堆法: 从尾到头down for i in n/2 .. =1 down(i)
    • 证明: 1/2 * 1/2展开分析
  • 插: 末尾插入, 不断up() down()
  • 弹: 最后元素和根节点交换, 然后弹出尾, 新根下沉
  • 改k: 改后down + up
  • 复杂度: 插入删除O(logn), 求最小O(1), 排序O(nlogn)

top k

对于快速排序, 我们并不需要整序列有序

  • 快速选择
    • 魔改快速排序, 只递归我们目标所在的那块区域
    • 复杂度: O(n), 每层都只用管一半, 所以是n + n/2 + n/4 … <= 2n
    • 注意分隔点: sl = j - l + 1; +1是因为top k的k是1 base

归并排序

dfs然后合并两个有序序列

  • dfs最终会得到两个只有一个元素的有序序列
  • 合并操作: 双指针 + aux数组迁移

离散化

数的范围很大, 但是实体比较稀疏, 我们可以直接用hashmap, 但是没必要。通过离散化后就可以比较方便的用大数组做hashmap

基本方法: 使用有序 + 二分做索引

  • 去重erase(unique(), it.end()) + 排序sort
  • get方法就是用二分取查找

misc

差分

  • 一个数组a, ai表示i往后个数加a[i]
  • 如果a[i] = c, a[i+k+1] = -c, 那么对数组a求前缀和就能实现对一段范围k, 加c的功能

4656. 技能升级

每个技能升级一次收益就减少固定值(等差数列)，求n次升级次数用什么方案升级收益最高。

  • 大数据筛
  • 因为是等差数列, 可以直接根据数学性质计算出数量和sum
  • 二分, 值域二分

二分枚举值域x, 使得大于x的数正好有n个(当然可能因为数值相同, 数会多一点。但是大于x-1就小于n了)。因为等差数列的性质, 我们枚举了x, 数的个数是可以直接计算得出的, 所以二分可行。然后再用等差数列的性质计算加和, 最后删掉重复元素即可。

143. 最大异或对

给一些数, 找那两个数异或的值是最高的

trie tree做索引

根据异或的性质, 当前bit是0, 如果有1的话能够取得更大的值; 如果当前bit是1, 则期望0。所以我们可以用所有数做一个trie tree, 然后查询每个数, 每个数从高位到低位查tree。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://github.com/66ring/2000/01/01/Major/algorithm/acwing/

algorithm

评论