分治法

问题描述在一个\({2^k}\times{2^k}(K\geqslant0)\)个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。棋盘覆盖问题要求用图所示的4种不同形状的\(L\)型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个\(L\)型骨牌不得重叠覆盖。问题分析算法设计......

前言因为觉得这个思想很有意思，最近也见到了许多使用根号分治的题目，自己也出了一些用根号分治的题目，所以想总结一下。（下文各种根号分治的名字是我掰出来的，应该有别的称呼）对文章的细节有疑问或是发现错误的欢迎提出。介绍根号分治是一种在对数据规模分类讨论的基础上利用不同算......

P9212看到除法相关容易想到根号分治。先对\(x,y\)进行讨论，不妨令\(0\lex,y<m\)。\(x<y\)时，当满足\(a_i+y<m\)或\(a_i+x\gem\)时，即当\(a_i<m-y\)或\(a_i\gem-x\)满足\((a_i+x)\bmodm<(a_i+y)\bmodm\)，即\(a_i\bmodm\in[0,m-y-1]\bigcup[m-x,m......

专题：CDQ分治本页面将完整介绍CDQ分治。简介CDQ分治是一种思想而不是具体的算法，与动态规划类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：解决和点对有关的问题。1D动态规划的优化与转移。通过CDQ分治，将一些动态问题转化为静态问题。CDQ分治的......

cdq分治的思路仍是处理跨过当前区间中点的贡献，但递归顺序是左子区间、当前区间、右子区间。这仍然满足处理当前区间时两个子区间的相对顺序不变（但左子区间不一定是有序的）从嵌套数据结构的观点看，cdq分治就是树套树外层树的中序遍历，优点是空间少一个\(\log\)且常数更小LG4093......

点分治1.给定一个带边权的树，共有\(m\)个询问，询问距离为\(k\)的点对是否存在做法1：暴力dfs做法2：\(lca\)(时间复杂度\(O(n^2\logn)\)）做法3：点分治(时间复杂度\(O(n\logn)\))思路：1.取一个节点\(u\)2.统计经过\(u\)的链经过\(u\)的链两端点必定在不同子树中记录子节......

递归分治法在快速排序中的应用 分治法的基本思想§分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。 k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求......

起因&介绍8月22号的T3是道黑，但思路却不算太难，就去打了这是第一次接触点分治，其实之前也有过一道点分治题，叫阴阳，但当时没去改，就一拖拖了半年才学点分治类似于树形DP，但在一些地方上处理有不同就比如在跑过根结点（1），进入处理它的子树时，会将其他的一部分视作没有（emmm大概这个意思，子树......

基本技巧——根号分治学习笔记根号分治与其说是一个算法，更不如说是一种思想（trick）。定义根号分治，是一种对数据进行点分治的分治方式，它的作用是优化暴力算法；类似于分块，但应用范围比分块更广。具体来说，对于所进行的操作，按照某个点\(B\)划分，分为大于\(B\)及小于\(B\)两个部......

可撤销并查集按时间顺序用一个栈维护合并信息，撤销时从栈顶弹出合并信息，恢复原状态。并查集查找祖先时不能路径压缩，只能按秩合并。例题：[ABC302Ex]BallCollector容易想到将\(A_i\)和\(B_i\)之间连边。遍历整棵树，用可撤销并查集维护图。为了进一步求得答案，需要注意到该......