代码见文末
题目 | 算法 | 题解 |
---|---|---|
机器翻译 | 模拟 | 直接模拟即可 |
乌龟棋 | 动态规划 | 直接四维dp即可 |
关押罪犯 | 并查集 二分图 贪心 | 并查集做法更为方便,记录敌人并查集,从大到小添加边直到出现矛盾(详见代码) |
引水入城 | 记忆化搜索 bfs 贪心 | 记忆化 |
分块是一种非常好用的根号算法,本质上是暴力优化技巧
原理是将序列分成
块,预处理出每个块的结果,在查询时只需要在完整块的基础上枚举散块更新答案即可
复杂度
SAT
指Satisfiability(可满足性问题)
k-SAT
指每个限制有
个条件,而当
时该问题为NP完全的,只能暴力
有
个布尔变量
n ,另有
x_1,x_2,\dots,x_n 个需要满足的条件,每个条件的形式都是「
m 为
x_i true
/false
或x_j
为true
/false
」.比如「
为
x_1 true
或为
x_3 false
」、「为
x_7 false
或为
x_2 false
」。
2-SAT
问题的目标是给每个变量赋值使得所有条件得到满足。
这是一种将带标号的树用一个唯一的整数序列表示的方法.
很多与度数有关的树上计数问题,都可以用它以及它的性质来解决
虚树是一种统计树上信息的技术
如果树的点数很少,可以直接树上dp
可以发现
我们可以每次都把提供
前置知识:
迭代加深搜索是一种每次限制搜索深度的深度优先搜索。
首先设定一个较小的深度作为全局变量,进行DFS
。
每进入一次DFS
,将当前深度加一,当发现大于设定的深度就返回。
如果在搜索的途中发现了答案就可以回溯
定义详见数学课本
指
发生的前提下,
发生的可能性
设$\forall i