《算法竞赛进阶指南》0x02 学习笔记递推、递归与“撤销选择”本文是我学习《算法竞赛进阶指南》0x02「递推与递归」后的整理。教材知识使用自己的话概括文中的 Codeforces 题目是课外练习不是书中例题。一、先弄清楚“当前问题”是什么学这一节时我一开始把“状态空间”理解得有些窄以为它就是所有情况的全排列。后来用数字1、2各自“选或不选”的例子才发现可能的结果其实是{}、{1}、{2}、{1, 2}空集也算一种结果而且这里没有讨论选择顺序。状态空间是问题所有可能状态的集合不一定是排列。递推和递归都要利用状态之间的关系只是走的方向不同递推从已知的小状态出发按顺序算出后面的状态。递归把当前问题交给更小的同类问题等它算完再回来处理当前问题。我目前对递推更顺手。写代码前最好先回答三个问题状态表示什么已知边界是什么当前状态怎样从更小的状态得到二、递归枚举每层究竟在决定什么如果有n个数每个数都可以选或不选就有2n2^n2n种方案。递归时可以让一层只负责一个数处理第 x 个数 ├─ 不选 x → 处理 x1 └─ 选 x → 处理 x1这叫指数型枚举。若要求“恰好选m个”就变成组合型枚举已经选多了或者剩下的数全选也凑不够m可以提前停止这条分支。若每层决定排列的下一个位置、不能重复使用数字则是在枚举排列。这里我曾经卡在“撤销”和“返回”上。假设chosen原来是{1}这层选了2递归结束后要执行pop_back()使它重新变回{1}。撤销是在修复大家共用的容器返回上一层是让上一层继续试还没试过的分支。这是两件不同的事。也不是所有递归都要手动撤销。如果角度这样的变量按值传给子函数子函数拿到的是自己那一份只有修改了共用数组、容器或标记才需要特别注意恢复现场。三、“费解的开关”先枚举再被迫决定书中的“费解的开关”是一张5×55\times55×5的 01 矩阵。按一个位置会翻转自己和上下左右。目标是找到使矩阵全为 0 的最少按法。我当时问过为什么只尝试第一行关键是第一行是自由选择后面的行不是。第一行每个按钮只有按或不按两种选择共25322^5322532种。选定第一行后如果第一行某格还是1就只能按第二行同一列的按钮来修正它。第二行固定后再根据第二行的状态决定第三行依次向下。最后检查第五行是否也全为 0。我还做过 CF275A Lights Out它虽然也是“一个按钮影响自己和四邻”但题目已经告诉我们每格按了几次只要求模拟最终状态。一个是寻找按法一个是已知按法求结果不能看见相同的按钮规则就套同一份程序。四、递推和分治在本节中的例子四柱汉诺塔先用三柱问题作基础。设d[n]是三柱移动n个盘子的步数d[0]0,d[n]2d[n−1]1. d[0]0,\qquad d[n]2d[n-1]1.d[0]0,d[n]2d[n−1]1.设f[n]是四柱问题的步数。把上面i个盘子先移开、用三柱移动剩余的n-i个、再移回上面i个于是枚举分割位置f[n]min1≤in(2f[i]d[n−i]). f[n]\min_{1\le in}\bigl(2f[i]d[n-i]\bigr).f[n]1≤inmin(2f[i]d[n−i]).我现在更想记住的是式子的来源先选一种拆法算它要多少步再在所有拆法中取最小值而不是直接背公式。分治的另一个例子是等比数列求和。直接使用等比数列的除法公式在取模场景下不能随便“除”书里把和拆成更短的和配合快速幂计算。分形街道则把大城市拆成四个小城市先用除法确定“在哪一块”用取模确定“块内第几个”递归得到块内坐标后再按那一块的旋转或翻转规则换成大城市坐标。分形街道的坐标变换我仍需要多拿小数据画图练习理解“块编号”和“块内编号”的区别是目前最明确的一步。五、课外练习CF550B 让我真正看懂maskCF550B Preparing Olympiad 要从n道题里挑一组检查题数、难度总和以及最大最小难度之差。因为n≤15可以枚举所有2n2^n2n个选法。我起初看懂了内层的“二进制位为 1 就选”却没明白外层mask是做什么的。后来才分清整个mask是当前这套选题方案例如mask5。mask的某一位才是这道题选或不选例如三道题时5101₂表示选第 1、3 题。外层把方案从1枚举到2^n-1内层逐位检查当前方案。mask0表示一题都不选本题可以直接跳过。以下是我完成的代码它通过了题面样例检查尚未确认 Codeforces 提交结果#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,l,r,x;cinnlrx;vectorintc(n1);for(inti1;in;i)cinc[i];intans0;for(intmask1;mask(1n);mask){intcnt0,sum0;intmnINT_MAX,mxINT_MIN;for(inti1;in;i){if(mask(1(i-1))){cnt;sumc[i];mnmin(mn,c[i]);mxmax(mx,c[i]);}}if(cnt2lsumsumrmx-mnx){ans;}}coutans\n;}mn从INT_MAX开始是为了保证第一道选中的题能把它更新成真实难度不初始化局部变量则会读到不确定的值。这里先检查cnt 2也避免把不足两题的方案当成合法题集。六、我还需要继续练的地方做 CF189A Cut Ribbon 时我最初想把三种长度排个序再依次切后来发现题目要求恰好切完而且一种长度可以用很多次。它适合定义f[x]为“恰好切出长度x时最多有几段”再枚举最后一段是哪种长度。我主动想到它和以前做的 CF1095C Powers Of Two 都在“把n拆成若干部分”但两题允许的部分和目标不同不能直接照搬方法。这节课目前最值得我反复检查的不是某个函数名而是状态是什么、边界在哪里、每次是否真的把问题缩小以及返回后共用的数据要不要恢复。CF189A 的递推代码和 CF1097B 的 DFS 写法我还可以再尝试不看参考答案独立写一遍。
