示例工程【免费下载链接】baekjoon코딩테스트 대비 문제집(Baekjoon Online Judge)项目地址https://gitcode.com/gh_mirrors/ba/baekjoon点击查看免费下载本篇文章以当前仓库 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 道为进阶补充题首列为空整体按难度从低到高排列。下表完整继承原文档的题目清单并将题解链接转换为当前仓库内的相对路径순번推荐题号题目난이도(Lv)仓库题解000✅17829222-풀링222-池化8solution/divide_and_conquer/17829/main.cpp001✅18222투에-모스 문자열Thue-Morse 串9solution/divide_and_conquer/18222/main.cpp002✅2630색종이 만들기彩色纸9solution/divide_and_conquer/2630/main.cpp003✅1992쿼드트리四叉树10solution/divide_and_conquer/1992/main.cpp004✅1074Z11solution/divide_and_conquer/1074/main.cpp005✅2447별 찍기 - 10星形 1011solution/divide_and_conquer/2447/main.cpp006✅2448별 찍기 - 11星形 1112solution/divide_and_conquer/2448/main.cpp007✅4256트리树14solution/divide_and_conquer/4256/main.cpp0084779칸토어 집합康托集8solution/divide_and_conquer/4779/main.cpp0091780종이의 개수纸的个数9—0101802종이 접기折纸10solution/divide_and_conquer/1802/main.py01114600샤워실 바닥 깔기 (Small)浴池铺砖·小10—0125904Moo 게임Moo 游戏11—0132374같은 수로 만들기变成同数12—01416438원숭이 스포츠猴子运动13—0151030프렉탈 평면分形平面13—0161493박스 채우기填箱子14—01714601샤워실 바닥 깔기 (Large)浴池铺砖·大16—原文档 README.md 同时指出两点刷题纪律不必严格按照题号顺序刷题可按自己当前水平跳跃选择推荐题之外的非推荐题是难度混合的补充训练用于检验分治思想在不同复杂度问题上的迁移能力。分治算法的核心思维框架在进入源码之前先建立统一的思维模型。分治算法遵循经典三段式Divide分将规模为n的问题拆成若干个规模更小、结构相同的子问题。从本仓库题单看常见的切分因子是2四等分、二分定位或3九等分、三段式对应问题 2630/1992/1074 与 2447/1780/4779。Conquer治对子问题递归求解直至到达递归基base case——本仓库中常见的递归基是size 1、size 2或size 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 i0;isize;i) for(int j0;jsize;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×NN2^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 i0;i2;i) for(int j0;j2;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矩阵内存必然爆炸优雅得多。递归基s2时的2*yx是 Z 字形编号的最小单元公式务必自行推导一遍。6. 2447 별 찍기 - 10九等分中空分形经典的 3×3 分形N 3^k的星图由 8 个N/3大小的子图拼成正中心留空。仓库解法 main.cpp 用布尔二维数组预填充再输出if(size 3) { for(int i0;i3;i) for(int j0;j3;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 i0;i3;i) for(int j0;j5;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]与右段[idx1, R2]合体现在cout放在两次递归之后——这正是后序遍历的定义。本题的区间指针计算L idx - L2容易写错建议画一棵 4 节点树完整走一遍递归栈。进阶补充题10 道难度混合的迁移训练非推荐题同样值得刷它们是检验分治思维能否泛化的试金石4779 칸토어 집합Lv.8仓库解法 main.cpp 展示了从两端递归、中间留空的三段式变体dfs(L, dis)中dis / 3后只递归[L, Ldis)与[L2dis, ...)中间段天然保留为空格是理解三分递归最直观的样例。1780 종이의 개수Lv.92630 的九等分版——3 个颜色统计递归基变为整块同色判定四等分变九等分适合验证把 2 改成 3的分治迁移力。1802 종이 접기Lv.10仓库解法 main.py 用区间二分验证对称性mid (startend)/2后检查status[i] ! status[end-i]的镜像约束再递归两侧区间。这是分治判定而非分治构造的典型代表。14600 / 14601 샤워실 바닥 깔기Lv.10 / Lv.16L 形瓷砖铺满问题递归基处理 L 形骨牌放置方向Large 版要求输出每个骨牌编号是四等分 手工构造结合的高阶题。5904 Moo 게임Lv.11S(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 揭示了这个数据流的完整闭环从源码结构看ProblemByTag.__init__读取algorithms/{tag}/list.md按,切分每行并解析为ProblemListType(recommend, problemId, solution_path)其中line[0] 1决定推荐标记随后从Database对应 database.py 中的题元数据库拉取每题难度与题名problem_data.update(...)合并后按难度sortmake_table()按[순번, 추천 문제, 문제 번호, 문제 이름, 난이도, 풀이 링크]六列生成 Markdown 表格其中推荐列输出:heavy_check_mark:题号与题名通过get_problem_url超链接难度列通过make_level_image渲染 solved.ac 徽章。这告诉我们一件重要的事你看到的 README 表格是渲染产物list.md才是权威数据源。如果需要在仓库基础上维护自己的分治刷题清单只需编辑algorithms/divide_and_conquer/list.md的 CSV 行修改推荐标记或追加新题行,题号,题解路径再运行生成逻辑即可刷新 README 表格。学习路径与自检清单建议按如下路线完成本目录顺序不必与题号一致但推荐题优先入门2630四等分 判定剪枝→ 17829递归基设大 缩格→ 4779三分 留空进阶1992括号拼接→ 1074纯数学定位→ 1802对称二分判定分形2447九等分方形分形→ 2448三角错位分形→ 1030分形点查询树上分治4256遍历区间重建→ 5904自引用串定位综合构造1780九等分统计→ 14600/14601L 形骨牌→ 1493分治贪心→ 16438构造分组。每做完一题对照仓库 solution/divide_and_conquer 中同名题解自查三个问题我的递归基设得对吗子问题切分与题目定义一致吗Combine 是否严格符合输出格式若能清晰回答分治模块即告通关——这套分—治—合框架将直接迁移到后续的归并排序、快速排序、线段树、点分治等高阶算法学习中。赞分享示例工程【免费下载链接】baekjoon코딩테스트 대비 문제집(Baekjoon Online Judge)项目地址https://gitcode.com/gh_mirrors/ba/baekjoon点击查看免费下载相关推荐Baekjoon 分治Divide and Conquer题单全解析从 Z 遍历到 222-풀링 的实战指南Baekjoon 分治Divide and Conquer题单全解析从 Z 遍历到 222 풀링 的实战指南 分治Divide and Conquer示例工程Baekjoon 分治算法Divide and Conquer问题集实战指南推荐题目路线与 C 源码剖析Baekjoon 分治算法Divide and Conquer问题集实战指南推荐题目路线与 C 源码剖析 本指南围绕本仓库「코딩테스트 대비 문제집示例工程分治算法Divide and Conquer深度解析基于 Hello Algo 仓库的分治思想、复杂度优化与应用全景分治算法Divide and Conquer深度解析基于 Hello Algo 仓库的分治思想、复杂度优化与应用全景 分治Divide and Conq教程文档示例工程教育上一篇三月七小助手每天为你节省2小时游戏时间的崩坏星穹铁道自动化工具下一篇使用 AWS SDK for .NET (v4) 操作 Amazon Cognito Identity Provider用户注册、TOTP 多因素认证与用户池管理实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考