GESP 二级编程题之——组合枚举

组合枚举是 GESP C++ 二级的高频编程题型，核心特征是题目给出明确的等式或判定规则，包含若干未知量，要求统计满足条件的方案数、判断是否存在合法解。通用解法是有几个未知量就写几层循环，逐层枚举所有可能取值，在内层循环中校验条件，符合则计数或输出结果。

一、核心思想与通用模板

题型识别：

一旦题目中出现一个明确的式子或等量关系，问里面的未知量有哪些可能，则通用枚举法解决

解题核心逻辑

1. 确定未知量：分析题目中独立可变参数的数量，对应循环的层数
2. 划定枚举范围：根据数据范围反推每个变量的上下界，避免过大范围枚举导致超时
3. 条件判定：在内层循环代入等式/规则，判断当前组合是否合法
4. 结果统计：用计数器累加合法方案数；需去重的场景强制变量有序，避免重复计数；判断“是否存在”类题目用 flag 标记状态

关键优化技巧

• 范围压缩：根据等式反推变量上限。例如判断 b⁴ = a，若 a 最大为 10⁸，则 b 只需枚举到 100，无需遍历到 a
• 去重处理：要求组合不考虑顺序时，强制内层变量起始值大于等于外层变量，避免 (a,b) 和 (b,a) 重复计数
• flag 标记：判断“是否存在合法解”的题目，找到符合条件的组合后标记状态，可提前跳出循环

可能使用到的函数

• a的b次方： pow(a, b) 例如2的n次方：pow(2, n)
• 根号：sqrt(a)， 也可以写pow(a, 0.5) 根号a等同于a的0.5次方
• a的绝对值：abs(a) 例如abs(-3)就等于3

二、真题解析

例题1：B4064 [GESP202412 二级] 寻找数字

题目描述

小杨有一个正整数 a，小杨想知道是否存在一个正整数 b 满足 a = b⁴。
输入 t 组测试数据，每组输出对应的 b；若不存在则输出 -1。

解题思路

单个未知量 b，属于单层枚举入门题。
范围优化：由 b⁴ ≤ a 可推出 b 的最大值约为 a 的四次方根，a 最大为 10⁸ 时 b 最大为 100，只需枚举到 100 即可。

参考代码

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        int a;
        cin >> a;
        bool flag = 1;
        for(int b = 1; b  <= 100; b++) // 应用上面的推理，a最大是10⁸，则b最大就是100
        {
            if(b * b * b * b == a)
            {
                cout << b << endl;
                flag = 0;
                break;
            }
        }
        if(flag == 1)
        {
            cout << -1 << endl; // 没找到 输出-1
        }
    }
    return 0;
}

例题2：B4002 [GESP202406 二级] 平方之和

题目描述

给定 n 个正整数，对每个数判断是否存在两个正整数 x 和 y，满足 x² + y² 等于该数。存在输出 Yes，否则输出 No。

解题思路

x、y 两个未知量，标准双层枚举题。

• 范围优化：由 x² < a ，题目已知a最大到10000，则x最大也就是100，因100*100得10000，y的范围同理。

• 去重处理：强制 y 从 x 开始枚举，保证 x ≤ y，避免同一组解被重复计算

  参考代码

  #include <iostream>
  #include <cmath>
  using namespace std;
  
  int main()
  {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) // 循环输入
    {
        int a;
        cin >> a;
        bool flag = 0;
        for(int x = 1; x <= 100; x++) // 枚举x
        {
            for(int y = x; y <= 100; y++) // 枚举y
            {
                if(x * x + y * y == a) // 判断题目要求的关系成立
                {
                    flag = 1; // 用flag为1标记找到了
                }
            }
        }
        if(flag == 1)
        {
            cout << "Yes" << endl; // 找到了
        }
        else
        {
            cout << "No" << endl; // 没找到
        }
    }
    return 0;
  }

例题3：B4357 [GESP202506 二级] 幂和数

题目描述

如果正整数 n 可以表示为两个 2 的次幂之和，即 n = 2ˣ + 2ʸ（x、y 为非负整数），则称 n 为幂和数。
给定区间 [l, r]，求区间内有多少个幂和数。

解题思路

外层循环遍历区间内的每一个整数，内层双层枚举指数 x 和 y，判断当前数是否满足幂和数的定义。
范围优化：枚举范围最大为 10⁴，已知2的10次方大约是1000，2的20次方大约是1000000，所以x和y最大不超过20，再精确一点就是14。

参考代码

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    
    // 外层枚举区间内的每个数
    for(int i = l; i <= r; i++)
    {
        bool flag = 0;
        // 内层枚举所有可能的指数组合
        for(int x = 0; x <= 14; x++)
        {
            for(int y = x; y <= 14; y++)
            {
                // 2的x次方 + 2的y次方 == i
                if(pow(2, x) + pow(2, y) == i)
                {
                    flag = 1;
                }
            }
        }
        if(flag == 1) cnt++;
    }
    
    cout << cnt << endl;
    return 0;
}

比较隐晦的枚举问题：

例题4：B4356 [GESP202506 二级] 数三角形

题目描述

直角三角形两条直角边长为 a、b，面积为 ab/2。当 a、b 均取不超过 n 的正整数时，求有多少个不同的、面积为整数的直角三角形。
(a,b) 和 (b,a) 视为同一个三角形。

解题思路

其实就是问满足a*b/2为整数的a和b有多少种组合。
a、b 两个未知量，双层枚举。

• 条件转化：面积为整数等价于 a×b 为偶数

• 去重处理：强制 a ≤ b，保证每个三角形只统计一次

  参考代码

  #include <iostream>
  using namespace std;
  
  int main()
  {
    int n;
    cin >> n;
    int cnt = 0;
    
    for(int a = 1; a <= n; a++) // 枚举a
    {
        // 枚举b， 保证b比a大，防止1 2, 2 1同一个三角形算两次
        for(int b = a; b <= n; b++) 
        {
            if((a * b) % 2 == 0)
                cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
  }

例题5：B4448 [GESP202512 二级] 黄金格

题目描述

地图有 H 行 W 列，格子坐标为 (r, c)。若格子满足 √(r² + c²) ≤ x + r - c，则称为黄金格。
求地图中一共有多少个黄金格。

解题思路

行号 r、列号 c 两个未知量，双层循环遍历所有格子，直接代入题目给出的不等式判断即可。

参考代码

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int h, w, x;
    cin >> h >> w >> x;
    int cnt = 0;
    
    for(int r = 1; r <= h; r++)
    {
        for(int c = 1; c <= w; c++)
        {
            if(sqrt(r * r + c * c) <= x + r - c) // 照抄题目要求满足的式子 sqrt代表根号
                cnt++;
        }
    }
    
    cout << cnt << endl;
    return 0;
}

例题6：B3836 [GESP202303 二级] 百鸡问题

题目描述

每只公鸡 x 元，每只母鸡 y 元，每 z 只小鸡 1 元。用 n 元买 m 只鸡，求一共有多少种购买方案。

解题思路

公鸡数量、母鸡数量、小鸡数量三个未知量，采用三层循环完整枚举所有可能的组合。
根据价格和总钱数压缩枚举范围，在内层同时判断总只数、总钱数是否符合要求，且小鸡数量必须符合整组售卖的规则。

参考代码

#include <iostream>
using namespace std;

int main()
{
    int x, y, z, n, m;
    cin >> x >> y >> z >> n >> m;
    int cnt = 0;
    
    // 三层循环：分别枚举公鸡、母鸡、小鸡的数量
    for(int g = 0; g * x <= n && g <= m; g++) // 公鸡数量
    {
        for(int mu = 0; mu * y <= n - g * x && g + mu <= m; mu++) // 母鸡数量
        {
            for(int xiao = 0; xiao <= m - g - mu; xiao++) // 小鸡数量
            {
                // 同时满足总只数、总钱数、小鸡整组售卖三个条件
                if(g + mu + xiao == m 
                    && g * x + mu * y + xiao / z == n 
                    && xiao % z == 0)
                {
                    cnt++;
                }
            }
        }
    }
    
    cout << cnt << endl;
    return 0;
}

三、总结

1. 层数对应原则：有几个独立未知量就写几层循环，从最外层变量开始逐层确定枚举范围。
2. 范围优先压缩：根据等式反推变量的最大可能值，不要直接拉满到 n，不然可能超时扣分。
3. 去重固定写法：例如1 2， 2 1 算一个答案时，内层循环起始值等于外层。
4. flag 适用场景：判断“是否存在”类题目，用 flag 标记找到后直接跳出所有循环，最后根据flag的值确定是否找到了，防止一个数被统计多次。