代码收藏家 枚举算法（竞赛必备）
一、引言
提到枚举，大家的第一印象可能都是Java亦或者是C++中的enum，如下：
enum 枚举类型名 {
常量1,
常量2,
...
常量n
};但在算法竞赛中的 “枚举”，可不止这么简单。重点：算法中的枚举，是一种思想，而不是一种语法结构！( •̀ ω •́ )y
二、枚举算法基础
核心思想：将所有可能罗列出来，逐一检验每个解，是否符合条件。（又称暴力解法-BF解法）
定义：简单来说，就是把所有可能的解空间进行遍历，逐一检验每个可能解是否是问题的真正解。
三、练习
枚举题型，更多会在填空题中考察。
提示( •̀ ω •́ )✧：
至少要独立思考10min，若20min后仍无思路在看解析，收获会更大！
1、好数（蓝桥真题）(解析)
2、蓝 (解析)
3、兴趣小组（蓝桥真题）（解析）
4、单词分析（蓝桥真题）（解析）
5、约数个数（蓝桥真题）（解析）
6、相乘（蓝桥真题）(解析）
7、直线（蓝桥真题）(解析)
8、大衣最多1的个数（解析）
目录
一、入门：
1、好数（蓝桥真题）
2、蓝
3、兴趣小组（蓝桥真题）
二、基础：
4、单词分析（蓝桥真题）
5、约数个数（蓝桥真题）
6、相乘（蓝桥真题）
三、进阶：
7、直线（蓝桥真题）
8、大衣最多1的个数
一、入门：
1、好数（蓝桥真题）
（枚举思想，将所有可能枚举出来）
问题描述
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 NN，请计算从 1 到 NN 一共有多少个好数。
输入格式
一个整数 NN。
输出格式
一个整数代表答案。
样例输入
24样例输出
7样例说明
对于第一个样例，2424 以内的好数有 11、33、55、77、99、2121、2323，一共 77 个。
评测用例规模与约定
对于 10%10% 的评测用例，1≤N≤1001≤N≤100 。
对于 100%100% 的评测用例，1≤N≤1071≤N≤107 。
Java版：
import java.util.Scanner; // 导入Scanner类，用于从控制台读取输入
public class Main {
// 定义一个方法来判断一个数字是否是“好数字”
public static boolean isGoodNum(int num) {
boolean flag = true; // 初始化标志位为true，假设当前数字是“好数字”
String str = Integer.toString(num); // 将整数num转换为字符串形式，便于逐位处理
// 从字符串的最后一位开始向前遍历
for (int i = str.length() - 1; i >= 0; --i) {
int number = str.charAt(i) - '0'; // 获取该位置的数字（字符转整数）
int place = str.length() - i; // 计算该数字在原数字中的位置（从1开始计数）
if (place % 2 == 0) { // 如果该位置是偶数位
if (number % 2 != 0) { // 如果该位置上的数字是奇数
flag = false; // 标记为非“好数字”
break; // 结束循环
}
} else { // 如果该位置是奇数位
if (number % 2 == 0) { // 如果该位置上的数字是偶数
flag = false; // 标记为非“好数字”
break; // 结束循环
}
}
}
return flag; // 返回标志位，表示是否是“好数字”
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建一个Scanner对象，用于读取输入
int N = scanner.nextInt(); // 读取用户输入的整数N
int goodNumCount = 0; // 初始化计数器，记录“好数字”的数量
// 遍历从1到N的所有整数
for (int i = 1; i <= N; ++i) {
if (isGoodNum(i)) { // 调用isGoodNum方法检查当前数字是否为“好数字”
goodNumCount++; // 如果是，则计数器加1
}
}
System.out.println(goodNumCount); // 输出“好数字”的总数
scanner.close(); // 关闭scanner对象，防止资源泄露
}
}C++版：
#include <iostream>
using namespace std;
bool is_GoodNum(int num){
bool flag = true;
string str = to_string(num);
for(int i=str.size()-1; i>=0; --i){
int number = str[i]-'0'; // 获取该位置的数字
int place = str.size()-i; // 用数组代表，个位、十位、百位...
if(place%2==0){ // 偶数位
if(number%2!=0){
flag = false;
break;
}
} else { // 奇数位
if(number%2==0){ // 奇数位若是偶数，则错误
flag = false;
break;
}
}
}
return flag;
}
int main()
{
int N;
cin>>N;
int GoodNum = 0;
for(int i=1; i<=N; ++i){
if(is_GoodNum(i)) GoodNum++;
}
cout<<GoodNum<<endl;
return 0;
}2、蓝
本题有两点需注意，
1、类型大小要开到long（C++是 long long），int只能表示（
-2,147,483,648 – 2,147,483,647之间的数字，大致就是：1的9次方左右，两亿。
超出范围，就会报错，就需要用long来储存。
）
且C++版中 num += (long long)vec[i] * vec[j] * vec[k];
与 num += (long long)(vec[i] * vec[j] * vec[k];) 是不一样的。
第二者，是错的
2、本题可用递归解决，但介于在练习枚举，便无伤大雅。
（额外，C++的switch要牢记语法框架）
问题描述
小蓝打算去参加蓝桥杯，他看到
lanqiao这个英文，于是想到了一个问题。现在有 nn 个小写英文单词，每个单词长度 1≤∣Si∣≤101≤∣Si∣≤10，他想从这些字符串中选出 33 个单词，要求这三个单词的首字符分别是
l，q，i，a，o55 个字母中的一个，且首字母不能有重复。现在小蓝想知道有多少种选择单词的方案，你可以写一个程序帮助他吗？
输入格式
第一行输入一个 nn ，表示输入的字符串的数量。
第二行输入 nn 个由空格隔开的小写英文单词 SiSi。
输出格式
输出一个整数，表示小蓝可以选择单词的方案数。
样例输入
5 lan qiao bei operation qqq样例输出
2说明
我们可以选择：
lan，qiao，operation与lan，qqq，operation。但是我们不能选择：
qqq，qiao，lan，因为q字母重复了。
Java版：
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
long n=scan.nextLong();
long[] arr={0,0,0,0,0};
while(n-- > 0){
String str=scan.next();
if(str.charAt(0)=='l') arr[0]++;
else if(str.charAt(0)=='q') arr[1]++;
else if(str.charAt(0)=='i') arr[2]++;
else if(str.charAt(0)=='a') arr[3]++;
else if(str.charAt(0)=='o') arr[4]++;
}
// 初始化一个长整型变量 sum，用于存储从以 'l'、'q'、'i'、'a'、'o' 开头的单词中选取 3 种不同开头的单词组合的总数
long sum = 0;
// 使用三层嵌套的 for 循环来枚举所有可能的 3 种不同开头的单词组合
// 外层循环控制第一个索引 i，范围是从 0 到 2（因为要保证后续有两个不同的索引）
for (int i = 0; i < 3; i++) {
// 中层循环控制第二个索引 j，范围是从 i + 1 到 3，确保 j 大于 i
for (int j = i + 1; j < 4; j++) {
// 内层循环控制第三个索引 k，范围是从 j + 1 到 4，确保 k 大于 j
for (int k = j + 1; k < 5; k++) {
// 计算当前这 3 种开头的单词组合的数量，通过将对应数组元素相乘得到
// 并将结果累加到 sum 中
sum += arr[i] * arr[j] * arr[k];
}
}
}
// 输出最终计算得到的组合总数
System.out.println(sum);
// 关闭 Scanner 对象，释放相关资源，避免资源泄漏
scan.close();
}
}C++版：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 本题是枚举类型，所以只需要记录每个字母开头，有几个单词就够了
int t;
cin >> t;
string str;
vector<int> vec(5, 0); // 标记每种单词依次+1
while (t--)
{
cin >> str;
// 根据单词的首字母，更新对应的计数
switch (str[0])
{
case 'l':
vec[0]++;
break;
case 'q':
vec[1]++;
break;
case 'i':
vec[2]++;
break;
case 'a':
vec[3]++;
break;
case 'o':
vec[4]++;
break;
default:
// 若输入的单词不是以 'l', 'q', 'i', 'a', 'o' 开头，则跳过该单词
continue;
}
}
long long num = 0;
// 用3层循环，把所有可能枚举出来
// 其实还能用递归代替，但是现在是在讲解简单枚举，所以不用复杂方法
for (int i = 0; i < 3; ++i)
{
for (int j = i + 1; j < 4; ++j)
{
for (int k = j + 1; k < 5; ++k)
{
num += (long long)vec[i] * vec[j] * vec[k];
}
}
}
cout << num << endl;
return 0;
}3、兴趣小组（蓝桥真题）
Java版：
public class Main {
// 定义一个公共类 Main，Java 程序执行时需要一个包含 main 方法的公共类作为入口
public static void main(String[] args) {
// 定义一个整型数组 resA，用于存储一组整数数据
// 这里只是示例，实际使用时省略号 ... 应替换为完整的数据
int[] resA = {12894792, 92774113, 59529208, 22962224 ... };
// 定义一个整型数组 resB，同样用于存储一组整数数据
// 省略号 ... 需替换为完整的数据
int[] resB = {44894050, 34662733, 44141729, 92774113 ... };
// 定义一个整型数组 resC，存储另一组整数数据
// 省略号 ... 要替换为完整的数据
int[] resC = {13404901, 39952424, 47847739, 94939581 ... };
// 定义一个整型变量 num，初始化为 0，用于统计满足特定条件的元素个数
int num = 0;
// 使用增强 for 循环遍历 resA 数组
// 每次循环，变量 i 依次取 resA 数组中的每个元素
for (int i : resA) {
// 定义一个布尔型变量 flag，初始化为 false
// 该变量用于标记当前元素 i 是否满足存在于 resB 且不存在于 resC 的条件
boolean flag = false;
// 使用增强 for 循环遍历 resB 数组
// 每次循环，变量 j 依次取 resB 数组中的每个元素
for (int j : resB) {
// 比较当前 resA 中的元素 i 和 resB 中的元素 j 是否相等
if (i == j) {
// 如果相等，将 flag 置为 true，表示 i 在 resB 中被找到了
flag = true;
}
// 使用增强 for 循环遍历 resC 数组
// 每次循环，变量 k 依次取 resC 数组中的每个元素
for (int k : resC) {
// 比较当前 resA 中的元素 i 和 resC 中的元素 k 是否相等
if (i == k) {
// 如果相等，将 flag 置为 false，表示 i 存在于 resC 中，不满足条件
flag = false;
}
}
}
// 判断 flag 的值
if (flag) {
// 如果 flag 为 true，说明元素 i 存在于 resB 且不存在于 resC
// 满足条件，将计数器 num 加 1
num++;
}
}
// 使用 System.out.println 方法输出满足条件的元素个数 num
System.out.println(num);
}
}C++版：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> resA{ 12894792, 92774113, 59529208, 22962224 ... };
vector<int> resB{ 44894050, 34662733, 44141729, 92774113 ... };
vector<int> resC{ 13404901, 39952424, 47847739, 94939581 ... };
int num = 0;
for(int i : resA){
bool flag = false;
for(int j : resB){
if(i==j) flag=true;
for(int k : resC){
if(i==k) flag=false;
}
}
if(flag) num++;
}
cout<<num<<endl;
return 0;
}二、基础：
4、单词分析（蓝桥真题）
Java版：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建一个大小为 26 的整型数组，用于统计每个字母的出现次数，初始值都为 0
int[] arr = new int[26];
// 创建一个 Scanner 对象，用于从标准输入读取用户输入的字符串
Scanner scanner = new Scanner(System.in);
// 读取用户输入的一行字符串
String str = scanner.nextLine();
// 关闭 Scanner 对象，释放资源
scanner.close();
// 遍历字符串中的每个字符
for (char c : str.toCharArray()) {
// 计算当前字符相对于 'a' 的偏移量，作为数组的索引
int num = c - 'a';
// 对应索引位置的计数加 1
arr[num]++;
}
// 初始化字母为 'a'
char letter = 'a';
// 初始化最大出现次数为 -1
int letterNum = -1;
// 遍历数组，找出出现次数最多的字母
for (int i = 0; i < 26; i++) {
// 如果当前字母的出现次数大于之前记录的最大次数
if (letterNum < arr[i]) {
// 更新最大出现次数
letterNum = arr[i];
// 根据索引计算对应的字母
letter = (char) (i + 'a');
}
}
// 输出出现次数最多的字母
System.out.println(letter);
// 输出该字母的出现次数
System.out.println(letterNum);
}
}C++版：
#include <iostream>
using namespace std;
int main()
{
// 谈论到字典，能用26个英语字母表示
// 也能用map表示
int arr[26]{0};
string str;
cin>>str;
for(char c : str){
int num = c-'a';
arr[num]++;
}
char letter = 'a';
int letterNum = -1;;
for(int i=0; i<26; ++i){
if(letterNum<arr[i]){
letterNum = arr[i];
letter = i+'a';
}
}
cout<<letter<<endl;
cout<<letterNum<<endl;
return 0;
}5、约数个数（蓝桥真题）
首先了解一下：什么是约数 # 小学数学
// 这道题目难就难在你不知道，啥是约数！然后没了
// 其他就是枚举（遍历所有可能），判断一下。
Java版：
public class Main {
public static void main(String[] args) {
// 初始化变量number，用于记录1200000的约数个数，初始值为0
int number = 0;
// 使用for循环进行枚举，从1到1200000
for (int i = 1; i <= 1200000; ++i) {
// 判断i是否为1200000的约数，如果1200000除以i的余数为0，则i是1200000的约数
if (1200000 % i == 0) {
// 如果i是约数，将number的值加1
number++;
}
}
// 输出1200000的约数个数
System.out.println(number);
}
}C++版：
#include <iostream>
using namespace std;
// 这道题目难就难在你不知道，啥是约数！然后没了
// 其他就是枚举（遍历所有可能），判断一下。
int main()
{
int number = 0;
for(int i=1; i<=1200000; ++i){
if(1200000%i==0) number++;
}
cout<<number<<endl;
return 0;
}6、相乘（蓝桥真题）
其实本题超级超级简单，这种题型也说明了为啥蓝桥杯，被称为暴力杯。
C++做这道题时不用担心超时。但是Java一定！要在循环结束后➕break，否则必然超时！
Java版：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 定义一个长整型变量 flag，用于存储最终符合条件的 i 值，初始化为 0
long flag = 0;
// 开始循环，从 1 到 1000000007 进行遍历
for (long i = 1; i <= 1000000007; i++) {
// 计算 i 乘以 2021 之后对 1000000007 取模的结果，存储在 num 中
long num = (i * 2021) % 1000000007;
// 判断 num 对 1000000007 取模的结果是否等于 999999999
if (num % 1000000007 == 999999999) {
// 如果满足条件，将当前的 i 值赋给 flag
flag = i;
break;
}
}
// 输出最终找到的符合条件的 i 值
System.out.println(flag);
}
}C++版：
#include <iostream>
#define ll long long
using namespace std;
int main()
{
ll flag = 0;
for(ll i=1; i<=1000000007; ++i){
ll num = i*2021%1000000007;
if(num%1000000007 == 999999999) flag = i;
}
cout<<flag<<endl;
return 0;
}三、进阶：
其实说是进阶，更不如说是综合题目，将多种知识糅合在一起，形成题目。
7、直线（蓝桥真题）
Java不懂HashSet的点击这里
这道题目就是典型的，嘴上说着超级超级难，其实超级简单！
因为他就是一道（枚举+数学题型）
为啥呢？看完这个公式就知道了：y=mx+C
另大家感到难受无非两个点。
1、怎么把所有直线表示出来。
2、怎么判断表示出来的直线，是否重复！
第一条，挺好解决的，就是个枚举问题，答案大家肯定能看懂。
第二条，更容易解决，判断他的斜率是否相等就行。
m相等，证明两条直线平行或重合。C相等，证明两条直线相交。
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z，即横坐标 是 00 到 11 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。
给定平面上 20×2120×21 个整点 (x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横 坐标是 00 到 1919 (包含 00 和 1919) 之间的整数、纵坐标是 00 到 2020 (包含 00 和 2020) 之 间的整数的点。
请问这些点一共确定了多少条不同的直线。
Java题解
import java.util.HashSet;
import java.util.Set;
public class Main {
/*
0<=x<20
0<=y<21
这些点确定了多少直线
提示：
0<=x<2
0<=y<3
这些点确定了11条直线
对于 y=ax+b,
*/
public static void main(String[] args) {
Set<String> set= new HashSet<>();
//遍历x1,x2,y1,y2四个点
for (int x1 = 0; x1 < 20; x1++) {
for (int y1= 0; y1 <21; y1++) {
for(int x2 =0;x2<20;x2++) {
for (int y2= 0; y2 <21; y2++) {
set.add(fun(x1,y1,x2,y2));
}
}
}
}
System.out.println(set.size()-1); //去掉下面第一种情况
}
private static String fun(int x1, int y1, int x2, int y2) {
//虽然set支持去重（方程一样），但是对于下面的三种情况，无法去重。
if(x1==x2&&y1==y2) {
return "_";
}
else if(x1==x2) {
return "x="+x1; // 垂直于 x 轴
}
else if(y1==y2) {
return "y="+y1;// 垂直于 y 轴
}else {
double k =(y2-y1)*1.0 /(x2-x1);
double b = (y1*x2 - y2*x1)*1.0/(x2-x1);
b+=0.0; //注意，这里必须加这一步，因为上一步的计算并不会改变b变量本身的数据类型
return "y="+k+"x+"+b; //交给set存储
}
}
}C++题解
#include <iostream>
#include <set>
using namespace std;
// 在做这种题目时，为避免精度问题，尽量将公式展开
// 接下来，两行其实是等价的，都是由一个公式推导出来的，但是第一个是错的！
// double c = (double)(y0-k*x0);
// double c = (double)(x0*y1-x1*y0)/(x0-x1);
// 因为，第一个，减少了中间步骤，也就减少了浮点数精度误差累积的机会，所以在某些情况下可能会得到更准确的结果。
int main()
{
set<pair<double,double>> s1;
for(int x0=0; x0<20; ++x0){
for(int x1=0; x1<20; ++x1){
for(int y0=0; y0<21; ++y0){
for(int y1=0; y1<21; ++y1){
if(x1==x0&&y1==y0) continue; // 两点相同的情况
if(x1==x0) continue; // 垂直时，跳过，后面加上20
// 分析垂直情况
double k = (double)(y0-y1)/(x0-x1);
// double c = (double)(y0-k*x0);
double c = (double)(x0*y1-x1*y0)/(x0-x1);
s1.insert({k,c});
}
}
}
}
cout<<s1.size()+20<<endl;
return 0;
}8、大衣最多1的个数
了解符号异或（ ^ 也就是本题中的 ⊕）
问题描述
大衣有一个长度为 NN 的二进制字符串 SS。
你需要构造一个长度为 NN 的字符串 XX：
对于每一个索引 i(1≤i≤N)i(1≤i≤N)，有 X(i+1)=Xi⊕SiX(i+1)=Xi⊕Si，其中 ⊕⊕ 表示按位异或。 字符串 XX 中字符 11 的个数最多。 请找出字符串 XX 中 11 的最多个数。
输入格式
第一行输入一个正整数 TT 表示测试数据的组数。
接下来 TT 组测试数据每组输入两行：
第一行输入一个正整数 NN 表示字符串 SS 的长度。
第二行输入一个长度为 NN 个二进制字符串 SS。
输出格式
对于每组测试数据，输出一个整数表示字符串 XX 中 11 的最多个数，并换行。
样例输入1
3 4 0011 4 1100 4 1010样例输出1
3 3 2说明
样例 11：考虑字符串 X=1110X=1110，其中 X2=X1⊕S1=1⊕0,X3=X2⊕S2=1⊕0,X4=X3⊕S3=1⊕1X2=X1⊕S1=1⊕0,X3=X2⊕S2=1⊕0,X4=X3⊕S3=1⊕1，字符串包含 33 个 11，可以证明没有更多的构造方案。
样例 22：考虑字符串 X=1011X=1011，其中 X2=X1⊕S1=1⊕1,X3=X2⊕S2=0⊕1,X4=X3⊕S3=1⊕0X2=X1⊕S1=1⊕1,X3=X2⊕S2=0⊕1,X4=X3⊕S3=1⊕0，字符串包含 33 个 11，可以证明没有更多的构造方案。
样例 33：考虑字符串 X=0110X=0110，字符串包含 22 个 11，可以证明没有更多的构造方案。
java版
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取测试用例的数量
int t = scanner.nextInt();
while (t > 0) {
// 读取字符串的长度
int N = scanner.nextInt();
// 读取字符串
String str = scanner.next();
// 用于记录初始值为 0 和 1 时 1 的个数
int num0 = 0;
int num1 = 0;
// 初始化 X0 为 0，X1 为 1
int X0 = 0;
int X1 = 1;
// 遍历字符串
for (int i = 0; i < N; i++) {
// 将字符转换为整数
int S = str.charAt(i) - '0';
// 假设 X 初始为 0
if (X0 == 1) {
num0++;
}
// 假设 X 初始化为 1
if (X1 == 1) {
num1++;
}
// 更新 X0 和 X1 的值
X0 = X0 ^ S;
X1 = X1 ^ S;
}
// 输出 num0 和 num1 中的最大值
System.out.println(Math.max(num0, num1));
t--;
}
scanner.close();
}
}C++版
#include <iostream>
using namespace std;
// 其实不难，别被题目|ﾟДﾟ)))吓到
// 本质就俩，
// 1、理解异或运算符
// 2、知道这是一个递推公式，只需要把X0初始化1或0就行。
int main()
{
// 这道题目很简单，只是会害怕与字符串
int t;
cin>>t;
while(t--){
int N;
cin>>N;
string str = ""; // 初始化
cin>>str; // 输入字符串
int num0 = 0; // 用于记录1的个数
int num1 = 0;
int X0 = 0;
int X1 = 1;
for(int i=0; i<N; ++i){ // 必须要完整的遍历，最后一次遍历X0,X1也会改变，但是不会生效。
int S = str[i]-'0';
// 假设X初始为0
if(X0==1) num0++;
// 假设X初始化为1
if(X1==1) num1++;
X0 = X0^S;
X1 = X1^S;
}
cout<<max(num0,num1)<<endl;
}
return 0;
}（切记，自己先实践，仍然无头绪，在询问组长）
借鉴博客、视频、网站：
1、蓝桥杯官网
2、什么是约数 # 小学数学
3、Java不懂HashSet的点击这里
4、了解符号异或（ ^ 也就是本题中的 ⊕）
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
作者：ん贤
