体系3.枚举、查找算法讲义

目录

1. 第一部分 · 知识与方法
2. 1.1 枚举算法
3. 1.2 查找算法
4. 1.3 二分答案
5. 第二部分 · 例题精讲
6. 第三部分 · 分类拓展
7. 第四部分 · 总结梳理

壹

第一部分 · 知识与方法

1.1 枚举算法（穷举法 Enumeration）

① 基本思想

枚举就是把问题所有可能的解，按照某种顺序逐一列举出来，再逐个检验是否符合题目条件，从而找到满足要求的答案。它利用了计算机「速度快、不怕重复」的特点，是最朴素、最通用、最不容易出错的方法。

枚举的一般结构：确定枚举对象（枚举什么：数字、方案、位置…）→ 确定枚举范围（从几到几）→ 对每种可能做条件判断（是否符合题意）→ 统计 / 记录答案。做到「不重复、不遗漏」。

for(枚举变量 = 起点; 枚举变量 <= 终点; 枚举变量++){ if(满足题目条件){ 计数 / 记录答案; } }

② 常见枚举类型

简单枚举

单层循环枚举一个量，配合条件判断。如数字统计、鸡兔同笼、评等级。

多重循环枚举

枚举多个变量的组合，如百鸡问题、三连击、火柴棒、统计方形。

数位枚举

枚举整数并拆出每一位（n%10取个位、n/=10去个位），如计数问题、回文数。

排列组合枚举

用 DFS / 回溯枚举所有排列、组合、子集，如全排列、选数、烤鸡。

③ 枚举的优化（重要）

• 缩小范围：利用数学关系减少枚举量。如判质数只需枚举到√n；x+y=S时只枚举 x，y 用S-x算出（把二重循环降为一重）。
• 减少嵌套层数：能用公式直接算的量就不再枚举，即「枚举一部分，计算另一部分」。
• 提前结束 / continue 跳过：明显不可能的情况直接跳过（剪枝思想）。
• 预处理 + 打表：先算出质数表、火柴棒根数表等，枚举时直接查表，避免重复计算。

// 拆出 n 的每一位 int x = n; while(x > 0){ int d = x % 10; /* 处理 d */ x /= 10; } // 判质数：只需试除到 sqrt(n) bool isPrime(int n){ if(n < 2) return false; for(int i=2; (long long)i*i<=n; i++) if(n % i == 0) return false; return true; }

复杂度与可行性：枚举前务必根据数据范围估算循环次数（1 秒约 10⁸ 次）。多重循环 n 太大会超时，此时应换用查找、二分或数学方法优化。

1.2 查找算法（Search）

① 顺序查找

从头到尾逐个比较，适合数据无序或规模小的情形，时间 O(n)。在一组数中判断「某个数是否出现过」常配合布尔数组 / 标记数组实现。

// 顺序查找 x int findX(int a[], int n, int x){ for(int i=0;i<n;i++) if(a[i]==x) return i; return -1; } // 值域有限时用 bool 数组标记是否出现（O(1) 查询） bool exist[1005]; for(...) exist[value] = true;

② 二分查找（Binary Search）

前提：数据有序（单调）。每次取中间元素比较，把搜索范围缩小一半，时间O(log n)，极快。

// 升序 a 中查找 x，返回下标，没有返回 -1 int binarySearch(int a[], int n, int x){ int l = 0, r = n-1; while(l <= r){ int mid = l + (r-l)/2; // 防 l+r 溢出 if(a[mid] == x) return mid; else if(a[mid] < x) l = mid+1; else r = mid-1; } return -1; } // STL 用法 int pos = lower_bound(a, a+n, x) - a; // 第一个 >= x 的下标

二分易错点：① 必须先有序；②mid=l+(r-l)/2防溢出；③l=mid+1 / r=mid-1不要漏 +1/−1，否则死循环。

1.3 二分答案（Binary Search the Answer）

当题目要求「最大的最小值 / 最小的最大值 / 满足条件的临界值」，并且可以对一个候选值写check(mid)判断「是否可行」时，可以直接二分答案，把求解问题变成判定问题。

使用条件：单调性。如果某个答案可行，那么比它「更宽松」的答案也一定可行（或反之），即可行性关于答案是单调的。

bool check(long long mid){ // O(n) 判定：以 mid 为候选答案时是否满足题意 } long long l = 下界, r = 上界, ans = l; while(l <= r){ long long mid = l + (r-l)/2; if(check(mid)){ ans = mid; l = mid+1; } // 可行：尝试更优 else r = mid-1; // 不可行：退回 } cout << ans;

典型题：砍树、跳石头、木材加工、数列分段、借教室、路标设置、一元三次方程（实数二分）。

贰

第二部分 · 例题精讲

下面 11 道例题覆盖枚举与查找的核心套路，建议先自己做，再看分析与代码。

P1046

陶陶摘苹果

入门简单枚举试题描述

陶陶有 10 个苹果，每个苹果到地面的高度已知。陶陶的身高已知，她还有一个 30 厘米的板凳。若苹果高度 ≤ 身高+30 就能摘到。问她一共能摘到几个苹果。

试题分析

只有 10 个苹果，直接顺序枚举每个高度，判断h[i] <= height+30是否成立，成立则计数。典型的「枚举 + 条件计数」。

#include <bits/stdc++.h> using namespace std; int main(){ int h[10]; for(int i=0;i<10;i++) cin >> h[i]; int height, ans = 0; cin >> height; for(int i=0;i<10;i++) if(h[i] <= height + 30) ans++; cout << ans; return 0; }

P1980

计数问题

入门数位枚举试题描述

给定整数 n 和 x（1≤x≤9），试计算在 1 到 n 的所有整数中，数字 x 一共出现了多少次。例如 1~11 中数字 1 出现 4 次（1,10,11）。

试题分析

枚举 1~n 每个数，用%10逐位取出数字，等于 x 就计数，再/10去掉该位。时间 O(n·位数)，对 n≤10⁶ 足够。

#include <bits/stdc++.h> using namespace std; int main(){ int n, x, ans = 0; cin >> n >> x; for(int i=1;i<=n;i++){ int t = i; while(t > 0){ if(t % 10 == x) ans++; t /= 10; } } cout << ans; return 0; }

B3836

百鸡问题

入门多重枚举 / 优化试题描述

公鸡每只 5 元、母鸡每只 3 元、小鸡 3 只 1 元。用 100 元买 100 只鸡，问公鸡、母鸡、小鸡各买多少只？输出所有可行方案。

试题分析

设公鸡 x、母鸡 y、小鸡 z，则 x+y+z=100 且 5x+3y+z/3=100。只需枚举 x、y，z 用100-x-y算出（三重→二重）；判断钱数时注意小鸡按 3 的倍数且总价为 100。也可三重循环，范围都很小。

#include <bits/stdc++.h> using namespace std; int main(){ for(int x=0;x<=20;x++) // 公鸡最多 20 只 for(int y=0;y<=33;y++){ // 母鸡最多 33 只 int z = 100 - x - y; // 小鸡只数直接算 if(z >= 0 && z%3==0 && 5*x+3*y+z/3==100) cout << x << ' ' << y << ' ' << z << '\n'; } return 0; }

P1618

三连击（升级版）

普及-多重枚举 / 数位试题描述

给定比例 A:B:C，找出所有三位数 a，使由 a、b、c 组成的三个三位数满足 a:b:c=A:B:C，并且 a、b、c 合起来的 9 个数字恰好是 1~9 各出现一次。输出每组解。

试题分析

枚举第一个三位数 a（123~987），由比例算出 b=a·B/A、c=a·C/A（要求能整除且均为三位数），再用数组统计三个数 9 个数字是否正好覆盖 1~9。枚举一个量、计算另两个量，是典型优化。

#include <bits/stdc++.h> using namespace std; int main(){ long long A,B,C; cin >> A >> B >> C; bool has = false; for(int a=123;a<=987;a++){ if(a*B%A || a*C%A) continue; // 必须整除 long long b=a*B/A, c=a*C/A; if(b<100||b>999||c<100||c>999) continue; int cnt[10]={0}, t; t=a; while(t){cnt[t%10]++;t/=10;} t=b; while(t){cnt[t%10]++;t/=10;} t=c; while(t){cnt[t%10]++;t/=10;} bool ok=true; for(int d=1;d<=9;d++) if(cnt[d]!=1) ok=false; if(ok){ cout<<a<<' '<<b<<' '<<c<<'\n'; has=true; } } if(!has) cout << "No!!!"; return 0; }

P1706

全排列问题

普及-DFS 枚举排列试题描述

给定整数 n（n≤9），按字典序输出 1~n 的所有排列，每个数字占 5 个字符宽度。

试题分析

用 DFS / 回溯枚举排列：dep 表示已确定的位置，从小到大尝试未使用的数字（保证字典序），used[]标记，递归返回后撤销。也可直接用 STLnext_permutation。

#include <bits/stdc++.h> using namespace std; int n, path[10]; bool used[10]; void dfs(int dep){ if(dep == n){ for(int i=0;i<n;i++) printf("%5d", path[i]); puts(""); return; } for(int x=1;x<=n;x++){ if(used[x]) continue; used[x]=true; path[dep]=x; dfs(dep+1); used[x]=false; // 回溯 } } int main(){ cin>>n; dfs(0); }

P1036

选数（NOIP 2002）

普及-DFS 枚举组合试题描述

已知 n 个整数，从中任选 k 个（不考虑顺序）相加，问有多少种选法使它们的和为质数。

试题分析

用 DFS 枚举组合（为避免重复，每次只从下标大于当前起点的数中选），选出 k 个后判断和是否为质数（试除到 √n）。「起始下标递增」是组合枚举去重的关键。

#include <bits/stdc++.h> using namespace std; int n, k, a[25], ans=0; bool isPrime(int x){ if(x<2) return false; for(int i=2;(long long)i*i<=x;i++) if(x%i==0) return false; return true; } void dfs(int cnt, int start, int sum){ if(cnt == k){ if(isPrime(sum)) ans++; return; } for(int i=start;i<n;i++) dfs(cnt+1, i+1, sum+a[i]); // i+1 保证组合不重复 } int main(){ cin >> n >> k; for(int i=0;i<n;i++) cin >> a[i]; dfs(0,0,0); cout << ans; }

B3750

幸运素数

入门枚举 + 双条件试题描述

一个质数如果它在质数表中的序号也是质数，就称为「幸运素数」。例如第 2 个质数、第 3 个质数等。给定 n，输出不超过 n 的所有幸运素数。

试题分析

按从小到大枚举整数，维护一个「这是第几个质数」的计数器 idx；每遇到质数，若 idx 本身也是质数，则它是幸运素数。本质是枚举质数并记录序号，再对序号做一次质数判断。

#include <bits/stdc++.h> using namespace std; bool isPrime(int x){ if(x<2) return false; for(int i=2;(long long)i*i<=x;i++) if(x%i==0) return false; return true; } int main(){ int n, idx=0; cin >> n; bool first=true; for(int v=2;v<=n;v++){ if(isPrime(v)){ idx++; // v 是第 idx 个质数 if(isPrime(idx)){ if(!first) cout<<' '; cout << v; first=false; } } } if(first) cout << "none"; return 0; }

P2249

查找（深基13·例1）

普及-二分 / lower_bound试题描述

给定 n 个非递减（不严格升序）的整数和 m 次询问，每次询问一个数 q，输出它在序列中第一次出现的位置（从 1 开始），不存在则输出 −1。

试题分析

序列有序、要找「第一次出现」，正是lower_bound的用途：返回第一个 ≥q 的位置，再判断该位置的值是否等于 q。每次询问 O(log n)。手写二分亦可，注意找左边界。

#include <bits/stdc++.h> using namespace std; int a[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; while(m--){ int q; cin >> q; int pos = lower_bound(a+1, a+n+1, q) - a; // 第一个 >= q if(pos<=n && a[pos]==q) cout << pos << ' '; else cout << -1 << ' '; } return 0; }

P1678

烦恼的高考志愿

普及-二分最近值试题描述

有 m 所学校的预估分数线和 n 个学生的估分。每个学生可填报分数线不超过其估分的学校，「不满意程度」=估分与该校分数线之差的绝对值的最小值。求所有学生不满意程度之和。

试题分析

把学校分数线排序。对每个学生的分数 x，用lower_bound找到第一个 ≥x 的位置，那么与 x 最接近的分数线只可能是它或它前一个，比较两者差值取最小。求和用 long long。

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int m,n; cin >> m >> n; vector<long long> line(m); for(int i=0;i<m;i++) cin >> line[i]; sort(line.begin(), line.end()); long long ans=0; for(int i=0;i<n;i++){ long long x; cin >> x; int p = lower_bound(line.begin(),line.end(),x)-line.begin(); long long best = LLONG_MAX; if(p<m) best = min(best, line[p]-x); // 右侧 if(p>0) best = min(best, x-line[p-1]); // 左侧 ans += best; } cout << ans; return 0; }

P1873

EKO / 砍树

普及-二分答案试题描述

有 n 棵树，高度为 h[i]。设定锯片高度 H，每棵超过 H 的部分被砍下（低于 H 不贡献）。要求得到的木材总长度至少为 M，求锯片 H 最大能设多高。

试题分析

H 越高，得到的木材越少——「能否得到 ≥M 的木材」关于 H 单调，故二分 H。check(H) 累加max(0, h[i]-H)（用 long long）判断是否 ≥M。可行就抬高 H，反之降低。

#include <bits/stdc++.h> using namespace std; int n; long long M; vector<long long> h; bool check(long long H){ long long got=0; for(int i=0;i<n;i++) if(h[i]>H) got += h[i]-H; return got >= M; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> M; h.resize(n); long long mx=0; for(int i=0;i<n;i++){cin>>h[i];mx=max(mx,h[i]);} long long l=0,r=mx,ans=0; while(l<=r){ long long mid=l+(r-l)/2; if(check(mid)){ans=mid;l=mid+1;} else r=mid-1; } cout << ans; }

P2678

跳石头（NOIP 2015）

普及/提高-二分答案 · 最大的最小试题描述

起点到终点 L 之间有 n 块岩石，最多可以移走 m 块。选手在岩石间跳跃。求在移走不超过 m 块岩石的前提下，最短跳跃距离的最大值是多少。

试题分析

经典「最大的最小值」，二分最短跳跃距离 d。check(d)：从起点贪心推进，若当前岩石与上一保留位置的距离 <d 就移走它，否则保留；统计移走数是否 ≤m。可行则尝试更大的 d。

#include <bits/stdc++.h> using namespace std; int L,n,m, a[50005]; bool check(int d){ int removed=0, last=0; for(int i=1;i<=n;i++){ if(a[i]-last < d) removed++; // 太近，移走 else last=a[i]; } if(L-last < d) removed++; // 到终点这一跳 return removed <= m; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> L >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; int l=1,r=L,ans=0; while(l<=r){ int mid=l+(r-l)/2; if(check(mid)){ans=mid;l=mid+1;} else r=mid-1; } cout << ans; }

叁

第三部分 · 分类拓展训练

按知识点把题单分为「枚举拓展」4 组与「查找 / 二分答案拓展」1 组，供针对性强化。每题给出题意、分析与参考代码。

A 组 · 基础枚举与模拟

P4325

Modulo

入门题意

读入 10 个整数，求每个数除以 42 的余数，输出其中有多少个不同的余数。

分析

余数只可能 0~41，用 bool 数组标记出现过的余数，最后数标记个数即可。

#include <bits/stdc++.h> using namespace std; int main(){ bool seen[42]={false}; for(int i=0;i<10;i++){int x;cin>>x;seen[x%42]=true;} int ans=0; for(int r=0;r<42;r++) if(seen[r]) ans++; cout<<ans; }

B3754

鸡兔同笼

入门题意

已知笼中鸡和兔的脚总数为 n，求笼中动物总数最少、最多各是多少（若不可能则输出特定提示）。

分析

设鸡 x、兔 y，2x+4y=n。n 必须为偶数；全是鸡时数量最多 n/2，尽量多放兔时数量最少。直接由脚数用公式推出，也可枚举兔的只数。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; if(n%2 || n<2){ cout<<"0 0"; return 0; } int mn=1e9, mx=0; for(int y=0; 4*y<=n; y++){ int rem=n-4*y; if(rem%2==0){ int x=rem/2, total=x+y; mn=min(mn,total); mx=max(mx,total); } } cout<<mn<<' '<<mx; }

P5742

评等级（深基7）

入门题意

n 个学生有文化课成绩与艺术课成绩。按给定规则（总分或艺术分达到线）判断每人是否「优秀」并输出。

分析

逐个枚举学生，按题目给出的两个条件做逻辑或判断即可，无需存储所有人。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; while(n--){ int id,a,b; cin>>id>>a>>b; if(a+b>140 && a*7+b*3>=800) cout<<"Excellent\n"; else cout<<"Not excellent\n"; } }

P1426

小鱼会有危险吗

入门题意

小鱼以初始速度游动并逐渐疲劳减速，前方有探测范围。给定距离、速度等参数，模拟小鱼游动过程，判断它能否安全游过危险区域。

分析

纯过程模拟：一步步更新已游距离和当前速度，判断进入危险区时速度是否已降到安全阈值以下。注意实数用 double 比较。

#include <bits/stdc++.h> using namespace std; int main(){ double s,x; cin>>s>>x; double dist=0, v=7; while(dist < s-x){ dist+=v; v*=0.98; } // 游到危险区边缘前 // 进入危险区这一步若能直接冲过则安全 if(dist+v >= s+x) cout<<"y"; else cout<<"n"; }

P1059

明明的随机数（NOIP 2006）

入门题意

给定若干 1~1000 的随机数，需要去重并从小到大排序，输出个数及结果。

分析

用 bool 数组（或 set）去重，再按值从小到大枚举输出；既去重又天然有序，是最简洁做法。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; bool have[1005]={false}; for(int i=0;i<n;i++){int x;cin>>x;have[x]=true;} int cnt=0; for(int v=1;v<=1000;v++) if(have[v]) cnt++; cout<<cnt<<'\n'; for(int v=1;v<=1000;v++) if(have[v]) cout<<v<<' '; }

P1088

火星人（NOIP 2004）

普及-题意

给出 1~n 的一个排列，求它之后的第 m 个排列（按字典序）并输出。

分析

直接对排列调用 m 次next_permutation即可；本质是按字典序枚举排列。

#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> a(n); for(int i=0;i<n;i++) cin>>a[i]; while(m--) next_permutation(a.begin(),a.end()); for(int i=0;i<n;i++) cout<<a[i]<<' '; }

P3717

cover（AHOI2017初中组）

入门题意

在一个 n×n 的坐标范围里，给定若干个圆形遮挡区域（圆心、半径），判断若干个点是否被覆盖，并统计相关数量。

分析

枚举每个待判点，再枚举每个圆，用「点到圆心距离 ≤ 半径」（平方距离比较避免开根）判断是否被覆盖。坐标范围小，双重枚举即可。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int x[105],y[105],r[105]; // 读入圆（数量按题意），这里以 cnt 个 int cnt=0; // 实际按输入处理 long long ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ bool cover=false; for(int k=0;k<cnt;k++){ long long dx=i-x[k],dy=j-y[k]; if(dx*dx+dy*dy <= (long long)r[k]*r[k]) cover=true; } if(cover) ans++; } cout<<ans; }

P6184

Building A Fence G（USACO）

普及-题意

给定若干块等长木板的长度，需要把木板截成规定高度的围栏板，问有多少种合法的切割/方案（简化描述）。

分析

枚举围栏的目标高度（整数且在可行区间内），对每种高度检查每块木板能否恰好切成所需数量，统计可行高度。枚举 + 判定模型。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> h(n); int mx=0; for(int i=0;i<n;i++){cin>>h[i];mx=max(mx,h[i]);} int ans=0; for(int H=1;H<mx;H++){ bool ok=true; for(int i=0;i<n;i++) if(h[i]<H || h[i]%H!=0){ ok=false; break; } // 规则按原题 if(ok) ans++; } cout<<ans; }

B 组 · 质数与数论枚举

P1075

质因数分解（NOIP 2012）

入门题意

已知正整数 n 是两个不同质数 p、q 的乘积，求其中较大的那个质数。

分析

从小到大枚举因数 d，第一个能整除 n 的 d 就是较小质数，另一个因数 n/d 即较大质数，立即输出。利用了 n 只有两个质因数。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; for(int d=2;d<=n;d++) if(n%d==0){ cout<<n/d; break; } }

P5723

质数口袋（深基4）

入门题意

从 2 开始依次把质数放入口袋，要求所有质数之和不超过 L，问最多能放几个，并输出这些质数。

分析

从小到大枚举整数，是质数就尝试加入，累加和不超过 L 则输出并计数，超过即停止。

#include <bits/stdc++.h> using namespace std; bool isPrime(int x){ if(x<2)return false; for(int i=2;(long long)i*i<=x;i++) if(x%i==0)return false; return true; } int main(){ int L,sum=0,cnt=0; cin>>L; for(int v=2;;v++){ if(isPrime(v) && sum+v<=L){ cout<<v<<'\n'; sum+=v; cnt++; } if(sum+v>L) break; } cout<<cnt; }

P1304

哥德巴赫猜想

入门题意

对 4~n 的每个偶数，找出两个质数，使它们之和等于该偶数（按较小质数尽量小等规则输出）。

分析

先用埃氏筛预处理质数表；对每个偶数枚举较小质数 a，查表判断 n−a 是否也是质数，找到即输出。打表把判断降到 O(1)。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<bool> isP(n+1,true); isP[0]=isP[1]=false; for(int i=2;(long long)i*i<=n;i++) if(isP[i]) for(int j=i*i;j<=n;j+=i) isP[j]=false; for(int even=4;even<=n;even+=2) for(int a=2;a<=even/2;a++) if(isP[a]&&isP[even-a]){ cout<<even<<"="<<a<<"+"<<even-a<<'\n'; break; } }

P1217

回文质数 Prime Palindromes

普及-题意

给定区间 [a,b]，输出其中既是回文数又是质数的所有数。b 可达一亿。

分析

直接枚举区间逐个判断会超时。关键性质：偶数长度的回文数一定是 11 的倍数，故除 11 外，回文质数位数必为奇数，可据此跳过大量数；再结合判质数。也可只枚举一半数字构造回文再判质数。

#include <bits/stdc++.h> using namespace std; bool isPrime(long long x){ if(x<2)return false; for(long long i=2;i*i<=x;i++) if(x%i==0)return false; return true; } bool palin(int x){ int t=x,r=0; while(t){r=r*10+t%10;t/=10;} return r==x; } int digits(int x){int d=0;while(x){d++;x/=10;}return d;} int main(){ int a,b; cin>>a>>b; for(int x=a;x<=b;x++){ int dg=digits(x); if(dg%2==0 && x!=11) continue; // 偶数位非11不可能 if(palin(x)&&isPrime(x)) cout<<x<<'\n'; } }

P2141

珠心算测验（NOIP 2014）

入门题意

给定 n 个不同的正整数，问其中有多少个数，恰好等于集合中另外两个（不同的）数之和。

分析

用 bool 数组标记哪些数在集合中；枚举集合中每个数作为目标，再枚举两个加数（或枚举一对数，标记其和）。注意统计的是「满足条件的数的个数」，每个目标只计一次。

#include <bits/stdc++.h> using namespace std; int main(){ int n,a[105]; cin>>n; bool in[20005]={false}; for(int i=0;i<n;i++){cin>>a[i];in[a[i]]=true;} int ans=0; for(int k=0;k<n;k++){ bool ok=false; for(int i=0;i<n&&!ok;i++) for(int j=i+1;j<n;j++) if(a[i]+a[j]==a[k]) ok=true; if(ok) ans++; } cout<<ans; }

P1029

最大公约数和最小公倍数问题（NOIP 2001）

入门题意

给定 x0、y0，求有多少对正整数 (P,Q) 满足 gcd(P,Q)=x0 且 lcm(P,Q)=y0。

分析

必要条件 x0 整除 y0。枚举 P（为 x0 的倍数且整除 y0），由 lcm 关系 Q=x0·y0/P，再用欧几里得算法验证 gcd 是否等于 x0，统计即可。

#include <bits/stdc++.h> using namespace std; int main(){ long long x0,y0; cin>>x0>>y0; if(y0%x0){cout<<0;return 0;} int ans=0; for(long long P=x0;P<=y0;P++){ if(y0%P) continue; long long Q=x0*y0/P; if(__gcd(P,Q)==x0) ans++; } cout<<ans; }

P1179

数字统计（NOIP 2010）

入门题意

统计区间 [L,R] 内所有整数中，数字 2 出现的总次数。

分析

枚举每个数并逐位拆出数字，等于 2 即计数，是数位枚举的直接应用。

#include <bits/stdc++.h> using namespace std; int main(){ int L,R,ans=0; cin>>L>>R; for(int x=L;x<=R;x++){ int t=x; while(t){if(t%10==2)ans++;t/=10;} } cout<<ans; }

P1151

子数整数

入门题意

对一个五位数，定义三个子数（连续取若干位得到）。给定三个目标和，输出所有满足三个子数分别能被给定数整除的五位数。

分析

枚举所有五位数（或按位构造），用 / 与 % 取出三个连续数位组成的子数，判断整除条件即可。

#include <bits/stdc++.h> using namespace std; int main(){ int k1,k2,k3; cin>>k1>>k2>>k3; bool none=true; for(int n=10000;n<=30000;n++){ int a=n/100; // 前3位 int b=n/10%1000; // 中3位 int c=n%1000; // 后3位 if(a%k1==0&&b%k2==0&&c%k3==0){cout<<n<<'\n';none=false;} } if(none) cout<<"No"; }

C 组 · 排列组合与搜索枚举

P1157

组合的输出

入门题意

从 1~n 中选出 r 个数的所有组合，按字典序输出，每个数占 3 个字符宽度。

分析

DFS 枚举组合，记录已选个数与起始下标，只选比当前大的数即可保证不重不漏、天然字典序。

#include <bits/stdc++.h> using namespace std; int n,r,path[25]; void dfs(int cnt,int start){ if(cnt==r){ for(int i=0;i<r;i++) printf("%3d",path[i]); puts(""); return; } for(int x=start;x<=n;x++){ path[cnt]=x; dfs(cnt+1,x+1); } } int main(){cin>>n>>r;dfs(0,1);}

P2089

烤鸡

入门题意

烤鸡需要 10 种配料，每种放 1~3 克。给定美味程度 n（=各配料克数之和），输出方案总数及所有配料方案。

分析

用 DFS 枚举 10 种配料各自的克数（1~3），剪枝：剩余配料全取最小/最大仍无法凑到 n 时提前返回。方案总量 3¹⁰，配合剪枝很快。

#include <bits/stdc++.h> using namespace std; int n, use[12]; vector<array<int,10>> ans; void dfs(int k,int sum){ if(k==10){ if(sum==n){ array<int,10> a; for(int i=0;i<10;i++)a[i]=use[i]; ans.push_back(a);} return; } for(int g=1;g<=3;g++){ int left=9-k; if(sum+g+left*1>n || sum+g+left*3<n) continue; // 剪枝 use[k]=g; dfs(k+1,sum+g); } } int main(){ cin>>n; if(n<10||n>30){cout<<0;return 0;} dfs(0,0); cout<<ans.size()<<'\n'; for(int i=0;i<(int)ans.size();i++){for(int j=0;j<10;j++)cout<<ans[i][j]<<' ';cout<<'\n';} }

P1149

火柴棒等式（NOIP 2008）

普及-题意

用 n 根火柴棒摆出形如 A+B=C 的等式（0~9 各数字所需火柴棒根数固定，加号与等号各占 2 根），统计能摆出的不同等式数量。

分析

预处理每个数字（及一个数整体）所需火柴棒根数。枚举 A、B，计算 C=A+B，判断三者火柴棒总数 +4 是否等于 n。枚举上限可据火柴棒根数反推（约到 1100 即可覆盖）。

#include <bits/stdc++.h> using namespace std; int cost[10]={6,2,5,5,4,5,6,3,7,6}; int need(int x){ if(x==0) return cost[0]; int s=0; while(x){s+=cost[x%10];x/=10;} return s; } int main(){ int n,ans=0; cin>>n; for(int A=0;A<=1100;A++) for(int B=0;B<=1100;B++){ int C=A+B; if(need(A)+need(B)+need(C)+4==n) ans++; } cout<<ans; }

P2084

进制转换

入门题意

给定一个十进制数 M 和进制 N（2~16），把 M 转换成 N 进制输出（含字母数码）。

分析

除 N 取余、逆序排列；余数 ≥10 时映射为 A~F。是进制枚举/转换的直接应用。

#include <bits/stdc++.h> using namespace std; int main(){ int M,N; cin>>M>>N; string d="0123456789ABCDEF",ans=""; if(M==0)ans="0"; while(M){ans=d[M%N]+ans;M/=N;} cout<<ans; }

D 组 · 方形与棋盘枚举

P2241

统计方形（数据加强版）

普及-题意

在 n×m 方格棋盘中，分别统计正方形个数与长方形（不含正方形）个数。

分析

边长 k 的正方形有 (n−k+1)(m−k+1) 个，累加；矩形总数为 n(n+1)/2·m(m+1)/2，减去正方形即长方形。用公式代替四重枚举，注意 long long。

#include <bits/stdc++.h> using namespace std; int main(){ long long n,m; cin>>n>>m; long long sq=0; for(long long k=1;k<=min(n,m);k++) sq+=(n-k+1)*(m-k+1); long long all=n*(n+1)/2*m*(m+1)/2; cout<<sq<<' '<<all-sq; }

P1548

棋盘问题（NOIP 1997）

入门题意

在 n×m 棋盘中统计正方形与长方形个数（数据较小）。

分析

与 P2241 同源，可四重循环枚举两角点统计，建议理解公式法。

for(int x1=1;x1<=n;x1++) for(int y1=1;y1<=m;y1++) for(int x2=x1;x2<=n;x2++) for(int y2=y1;y2<=m;y2++) if(x2-x1==y2-y1)sq++; else rec++;

P1006

传纸条（NOIP 2008）

提高拓展：已超枚举题意

在 m×n 矩阵中找两条从左上到右下尽量不相交的路径，使经过的好心程度之和最大。

分析

枚举两路径会组合爆炸，正解是双线动态规划。此处仅作视野拓展，说明枚举到极限应升级为 DP。

学习提示要求两路径整体最优、枚举爆炸时，是典型动态规划信号。

E 组 · 查找与二分答案拓展

P2440

木材加工

普及-题意

n 根原木要截出 k 段等长木料，求每段最长多长。

分析

二分每段长度 L，check 统计 ∑⌊h[i]/L⌋ 是否 ≥k，段数随 L 单调。

bool ok(long long L){ long long cnt=0; for(int i=0;i<n;i++){cnt+=h[i]/L;if(cnt>=k)return true;} return false; } // 主函数二分 long long l=1,r=mx,ans=0; while(l<=r){ long long mid=l+(r-l)/2; if(ok(mid)){ans=mid;l=mid+1;}else r=mid-1; }

P1182

数列分段 Section II

普及/提高-题意

把 n 个正整数分成连续 m 段，使各段和的最大值最小。

分析

二分每段和上限 S，check 贪心扫描，超 S 就新开段，判断最少段数是否 ≤m。

bool ok(long long S){ int seg=1; long long cur=0; for(int i=0;i<n;i++){ if(a[i]>S)return false; if(cur+a[i]>S){seg++;cur=a[i];}else cur+=a[i]; } return seg<=m; }

P1083

借教室（NOIP 2012）

提高题意

订单按顺序处理，找第一个无法满足教室需求的订单；全满足输出 0。

分析

可行性随订单数单调，二分订单数；check(k) 用差分叠加前 k 个订单每天需求，再与 r[i] 比较。二分+差分 O((n+m)log m)。

bool ok(int k){ fill(diff.begin(),diff.end(),0); for(int i=1;i<=k;i++){diff[s[i]]+=d[i];diff[t[i]+1]-=d[i];} long long cur=0; for(int day=1;day<=n;day++){cur+=diff[day];if(cur>r[day])return false;} return true; }

P3853

路标设置（TJOI2007）

普及/提高-题意

可增设路标，求使相邻最大间距尽量小的方案（受增设数量限制）。

分析

与跳石头同类。二分最大间距 d，每段长 len 需增设 ⌈len/d⌉−1 个，判断总数是否超限。

bool ok(int d){ int add=0; for(int i=1;i<N;i++){ int len=pos[i]-pos[i-1]; add+=(len+d-1)/d-1; if(add>K)return false; } return add<=K; }

P1024

一元三次方程求解（NOIP 2001）

普及/提高-题意

给定三次方程系数，已知有三个不同实根（相邻根差≥1），求三个实根（保留 2 位小数）。

分析

实数二分：以长度 1 扫描，端点函数值异号则区间内有根，对该区间二分至足够精确。注意端点恰为根。

if(y1*y2<0){ double l=x1,r=x2; while(r-l>1e-4){ double m=(l+r)/2; if(f(m)*f(l)<=0)r=m;else l=m; } printf("%.2f ",l);found++; }

肆

第四部分 · 总结与方法梳理

4.1 枚举法知识地图

4.2 查找与二分知识地图

4.3 方法论口诀

枚举三问① 枚举什么？② 范围多大、能否剪枝？③ 如何判定 / 计数、会不会重复？

二分三步① 确定要二分的答案参数；② 证明「可行性单调」并写对 check；③ 定好边界与中点，注意死循环与溢出。

易错清单枚举：边界取等、去重计数、超时（先估运算量）； 二分：有序前提、mid 用 l+(r−l)/2 防溢出、更新方向写反、l/r 更新导致死循环。

4.4 进阶路线

• 枚举 + 前缀和 / 差分：把区间统计、区间修改降到 O(1)。
• 二分答案 + 贪心 check：跳石头、数列分段等「最 X 的最 Y」通法。
• 当枚举组合爆炸且需整体最优 → 动态规划（传纸条）。
• 当搜索空间大、需要剪枝 → DFS/BFS（选数、全排列的深化）。

↑

枚举、查找算法讲义 · 题目来自洛谷题单，版权归原题作者所有 · 代码以标准 C++ 编写