baekjoon 仓库分治算法题单深度解析：以 Divide and Conquer 分类为骨架的 백준 刷题实战指南

• 示例工程

本篇文章以当前仓库 algorithms/divide_and_conquer/list.md 中的分治算法（Divide and Conquer，분할정복）题单为绝对主体，结合 solution/divide_and_conquer 下的真实题解源码，逐题拆解分治思想在 백준（Baekjoon Online Judge）题目中的落地方式。读完本文，你将掌握分治算法的"分—治—合"三段式思维框架，理解四等分、三分、二维递归定位、树形递归等核心模式，并能够对照仓库源码独立完成这 18 道题中的任意一道。

题单速览：18 道分治题目全貌

list.md 采用"推荐题 + 难度混合题"的组织方式：带:heavy_check_mark:标记的 8 道为推荐必刷题（对应 CSV 首列为1），其余 10 道为进阶补充题（首列为空），整体按难度从低到高排列。下表完整继承原文档的题目清单，并将题解链接转换为当前仓库内的相对路径：

原文档 README.md 同时指出两点刷题纪律：不必严格按照题号顺序刷题，可按自己当前水平跳跃选择；推荐题之外的非推荐题是"难度混合"的补充训练，用于检验分治思想在不同复杂度问题上的迁移能力。

分治算法的核心思维框架

在进入源码之前，先建立统一的思维模型。分治算法遵循经典三段式：

1. Divide（分）：将规模为n的问题拆成若干个规模更小、结构相同的子问题。从本仓库题单看，常见的切分因子是2（四等分、二分定位）或3（九等分、三段式），对应问题 2630/1992/1074 与 2447/1780/4779。
2. Conquer（治）：对子问题递归求解，直至到达递归基（base case）——本仓库中常见的递归基是size == 1、size == 2或size == 3。
3. Combine（合）：把子问题的解合并成原问题的解，这一步决定题目形态：可能是统计（2630 数颜色）、拼接（1992 拼编码串）、累加（1074 累偏移量），也可能是二次递归筛选（17829 逐层池化）。

本仓库所有题解都遵循"递归函数接收坐标与尺寸"的统一签名风格，例如 2630 与 1992 都是solve(int y, int x, int size)——(y, x)为当前子矩阵左上角，size为边长。这个签名是阅读全部源码的钥匙。

推荐题源码精讲（8 道必刷）

1. 2630 색종이 만들기：最纯正的四等分判定

这是分治入门第一题，任务是统计整张彩色纸最终被切成多少张全白（0）与全蓝（1）的纸。仓库解法 main.cpp 的思路：

void solve(int y, int x, int size) { bool flag = true; for(int i=0;i<size;i++) for(int j=0;j<size;j++) if(arr[y][x] != arr[y + i][x + j]) flag = false; if(flag) answer[arr[y][x]] ++; else { size /= 2; solve(y , x , size); solve(y + size, x , size); solve(y , x + size, size); solve(y + size, x + size, size); } }

关键设计：先扫后分。每次进入子问题先整块扫描，若整块同色则直接计数（flag == true），否则一分为四递归。answer[arr[y][x]]++巧妙利用0/1作为下标，白纸进answer[0]、蓝纸进answer[1]。时间复杂度为O(N²)级别的摊还分析：同色大块在顶层就被剪枝，只有颜色变化处才会继续下探。

2. 17829 222-풀링：递归基是 2×2 的"池化"

题目要求对N×N（N=2^k）矩阵反复执行 2×2 池化（取每块第二大的值），直到缩成单个数。仓库解法 main.cpp 把递归基直接设在size == 2，一改常规"分到 1×1"的写法：

void f(int y, int x, int s) { if(s == 2) { int value[4] = { 0 }; for(int i=0;i<2;i++) for(int j=0;j<2;j++) value[i * 2 + j] = arr[y + i][x + j]; sort(value, value + 4); tmp[y / 2][x / 2] = value[2]; // 第二大的数 return; } s /= 2; f(y , x , s); f(y + s, x , s); f(y , x + s, s); f(y + s, x + s, s); }

精髓在于tmp[y/2][x/2] = value[2]：由于每个 2×2 块处理后都缩放到原坐标的一半，因此可直接按y/2、x/2写入临时数组，天然完成"缩小"动作。main()里用while(N != 1)反复调用f(0,0,N)并N /= 2，每轮把tmp拷回arr，实现了迭代驱动递归的池化循环。

3. 18222 투에-모스 문자열：从递归退化为位运算

Thue-Morse 串第N项的标准定义就是递归的，但仓库解法 main.cpp 展示了分治思想的极致优化——把递归过程压缩成二进制位计数：

ll cnt = 0; while(N) { ll cur = 1; while(cur * 2 < N) cur <<= 1; // 找到不超过 N 的最大 2 的幂 N -= cur; cnt ++; } ll ans = ~cnt & 1; // 奇偶性取反后 &1

每次减去不超过当前值的最大的 2 的幂，等价于在递归树中沿路径跳跃；cnt记录跳了奇数层还是偶数层，~cnt & 1输出对应字符（0/1）。复杂度从递归的O(log N)栈深度进一步降到纯迭代O(log N)，是理解"分治可以退化为数学公式"的绝佳案例。

4. 1992 쿼드트리：括号包裹的递归拼接

与 2630 几乎同构，但输出从"计数"变为四叉树编码串：同色输出0/1，异色则输出(+ 四个子块递归结果 +)。仓库解法 main.cpp 的顺序是左上→右上→左下→右下：

answer += "("; solve(y , x , s); solve(y , x + s, s); solve(y + s, x , s); solve(y + s, x + s, s); answer += ")";

注意与 2630 子块顺序的差异：2630 是"左上→左下→右上→右下"，而 1992 按四叉树编码规则是"左上→右上→左下→右下"。这种顺序敏感性提醒我们，分治题的 Combine 阶段必须严格符合题目输出约定。建议把这两题对照着写，一次掌握"判定剪枝"与"结构拼接"两种合流方式。

5. 1074 Z：不建矩阵，直接算答案

Z是分治思想的标志性题目：按 Z 字形给2^N × 2^N矩阵编号，查询(R, C)的编号。仓库解法 main.cpp 的亮点是完全不做标记，纯数学定位：

int solve(int y, int x, int s) { if(s == 2) return 2 * y + x; // 递归基：2×2 内直接编号 s >>= 1; int ny = y / s, nx = x / s; // 判断点落在哪个 1/4 象限 int nxt = ny * 2 + nx; // 象限编号 0~3 return s * s * nxt + solve(y - ny * s, x - nx * s, s); }

每次递归先定位当前点属于第几个象限，累加"该象限起点偏移量s*s*nxt"，再进入子象限递归。整个递归深度为N（因为s每次右移一位），复杂度O(N)，空间O(N)栈深——这比直接构造2^N矩阵（内存必然爆炸）优雅得多。递归基s==2时的2*y+x是 Z 字形编号的最小单元公式，务必自行推导一遍。

6. 2447 별 찍기 - 10：九等分中空分形

经典的 3×3 分形：N = 3^k的星图由 8 个N/3大小的子图拼成，正中心留空。仓库解法 main.cpp 用布尔二维数组预填充再输出：

if(size == 3) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(i == 1 && j == 1) continue; // 中心留空 else arr[y + i][x + j] = true; return; } size /= 3; solve(y + 0*size, x + 0*size, size); ... // 8 个非中心子块递归

递归基为3×3，跳过中心(1,1)后把其余 8 格置真。上层递归明确跳过(y + 1*size, x + 1*size)即 9 块中的正中心块，只调用其余 8 块。最终遍历输出时按arr[i][j]打*或空格。空间O(N²)，时间同样O(N²)。

7. 2448 별 찍기 - 11：三角形的分形拼贴

比 2447 更难的地方在于子三角形不按方形网格对齐：每个大三角形由 3 个N/2的小三角形组成，位置偏移是3*s与6*s（三角形行列坐标非对称）。仓库解法 main.cpp 预先定义最小单元图案：

char DB[3][6] = { " * ", " * * ", "*****" }; void solve(int y, int x, int s) { if(s == 1) { // 拷贝 3×5 基本单元 for(int i=0;i<3;i++) for(int j=0;j<5;j++) stars[y + i][x + j] = DB[i][j]; return; } s /= 2; solve(y , x + 3 * s, s); // 顶部 solve(y + 3 * s, x , s); // 左下 solve(y + 3 * s, x + 6 * s, s); // 右下 }

注意main中以n / 3作为递归初始s，即把输入n（必须为 6 的倍数）转换为"多少个基本单元"。这是分形题的通用技巧：先定义最小可复制单元，再定义单元之间的偏移关系。读者可对比 2447 与 2448，体会"方形网格分形"与"三角错位分形"的偏移计算差异。

8. 4256 트리：用前序+中序分治重建二叉树

本题把分治思想迁移到树上：给定前序、中序遍历，要求输出后序遍历。仓库解法 main.cpp 用区间参数递归：

void solve(int L, int R, int L2, int R2) { if(L > R || L2 > R2) return; int root = preorder[L]; // 前序第一个元素必为根 int idx = L2; while(inorder[idx] != root) idx++; // 在中序中定位根，切分左右子树 solve(L + 1, L + idx - L2, L2, idx - 1); // 左子树 solve(L + idx - L2 + 1, R, idx + 1, R2); // 右子树 cout << root << ' '; // 后序输出：左→右→根 }

分治的"分"体现在while扫描中序找到根的位置idx，从而把中序切成左段[L2, idx-1]与右段[idx+1, R2]；"合"体现在cout放在两次递归之后——这正是后序遍历的定义。本题的区间指针计算（L + idx - L2）容易写错，建议画一棵 4 节点树完整走一遍递归栈。

进阶补充题：10 道难度混合的迁移训练

非推荐题同样值得刷，它们是检验分治思维能否泛化的试金石：

• 4779 칸토어 집합（Lv.8）：仓库解法 main.cpp 展示了"从两端递归、中间留空"的三段式变体：dfs(L, dis)中dis /= 3后只递归[L, L+dis)与[L+2dis, ...)，中间段天然保留为空格，是理解三分递归最直观的样例。
• 1780 종이의 개수（Lv.9）：2630 的九等分版——3 个颜色统计，递归基变为整块同色判定，四等分变九等分，适合验证"把 2 改成 3"的分治迁移力。
• 1802 종이 접기（Lv.10）：仓库解法 main.py 用区间二分验证对称性：mid = (start+end)/2后检查status[i] != status[end-i]的镜像约束，再递归两侧区间。这是"分治判定"而非"分治构造"的典型代表。
• 14600 / 14601 샤워실 바닥 깔기（Lv.10 / Lv.16）：L 形瓷砖铺满问题，递归基处理 L 形骨牌放置方向，Large 版要求输出每个骨牌编号，是四等分 + 手工构造结合的高阶题。
• 5904 Moo 게임（Lv.11）：S(k) = S(k-1) + "moo..." + S(k-1) 的自引用递归，需要先二分定位第 N 个字符属于前段还是后段，与 1074 的"定位 + 偏移"同源。
• 2374 같은 수로 만들기（Lv.12）：把数列中一个连续子段同时加 1，最少次数使其全部相等；分治配合最小值切割可解。
• 16438 원숭이 스포츠（Lv.13）：构造 7 天 × 20 人的分组方案，递归构造要求任意两人分属不同组，验证"分治 + 构造"能力。
• 1030 프렉탈 평면（Lv.13）：分形平面的局部查询，递归判定某点是否落在染色块内，与 1074 共享"点定位"模式。
• 1493 박스 채우기（Lv.14）：按 2 的幂分治贪心填充大箱子，Combine 阶段是体积换算与回溯。

题单的数据格式与自动化生成机制

list.md不只是给人看的表格，更是机器可读的数据源。其原始 CSV 格式为每行recommend,problemId,solution_url，首列为1表示推荐题：

1,2630,https://.../solutions/baekjoon/2630 1,17829,https://... ,4779,https://...

仓库中的 baekjoon_utils/baekjoon_utils/docs/problem.py 揭示了这个数据流的完整闭环（从源码结构看）：

1. ProblemByTag.__init__读取algorithms/{tag}/list.md，按,切分每行并解析为ProblemListType(recommend, problemId, solution_path)，其中line[0] == '1'决定推荐标记；
2. 随后从Database（对应 database.py 中的题元数据库）拉取每题难度与题名，problem_data.update(...)合并后按难度sort；
3. make_table()按["순번", "추천 문제", "문제 번호", "문제 이름", "난이도", "풀이 링크"]六列生成 Markdown 表格，其中推荐列输出:heavy_check_mark:，题号与题名通过get_problem_url超链接，难度列通过make_level_image渲染 solved.ac 徽章。

这告诉我们一件重要的事：你看到的 README 表格是"渲染产物"，list.md才是权威数据源。如果需要在仓库基础上维护自己的分治刷题清单，只需编辑algorithms/divide_and_conquer/list.md的 CSV 行（修改推荐标记或追加新题行,题号,题解路径），再运行生成逻辑即可刷新 README 表格。

学习路径与自检清单

建议按如下路线完成本目录（顺序不必与题号一致，但推荐题优先）：

1. 入门：2630（四等分 + 判定剪枝）→ 17829（递归基设大 + 缩格）→ 4779（三分 + 留空）；
2. 进阶：1992（括号拼接）→ 1074（纯数学定位）→ 1802（对称二分判定）；
3. 分形：2447（九等分方形分形）→ 2448（三角错位分形）→ 1030（分形点查询）；
4. 树上分治：4256（遍历区间重建）→ 5904（自引用串定位）；
5. 综合构造：1780（九等分统计）→ 14600/14601（L 形骨牌）→ 1493（分治贪心）→ 16438（构造分组）。

每做完一题，对照仓库 solution/divide_and_conquer 中同名题解自查三个问题：我的递归基设得对吗？子问题切分与题目定义一致吗？Combine 是否严格符合输出格式？若能清晰回答，分治模块即告通关——这套"分—治—合"框架将直接迁移到后续的归并排序、快速排序、线段树、点分治等高阶算法学习中。

• 示例工程