一、CDQ 分治
因为时间的关系，我也不确定我理解的这个套路是否是所谓的 “CDQ 分治”，还是只是一种具有二维偏序特征的模板。
在这种题目中，我们一般会对于一个二维结构体去排序，比如说
struct Node
{
int x;
int y;
};而且排序一般会发生两次，第一次是在开始前先对某个维度进行一遍排序，然后在分治过程中，利用归并排序的思想，在二分的过程中对于另一个维度再次进行排序。也就是如下模板
算法设计-搜索
一、BFS 模板
如下所示
set<Node> visited;
bool check(Node son);
int bfs(Node start)
{
// init
queue<Node> q;
q.push(start);
visited.insert(start);
while (!q.empty())
{
Node front = q.front();
q.pop();
for (son : q.neigbour)
{
// prune
if (check(son))
{
q.push(son);
visited.insert(son);
// son is the correct answer
if (ac(son))
{
return son.info();
}
}
}
}
return -1;
}
int main()
{
//...
int ans = bfs();
//...
return 0;
}其中有几部分需要一一强调，第一个是 check() 函数用于进行减枝，只有经过 check 的子节点会被加入队列。
bool check(Node son);
