企业官网建设流程全解析

挑选宝石

2025华为OD机试双机位B卷 - 华为OD上机考试双机位B卷 100分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

游乐园有一款互动游戏，游戏开始时会提供n个宝石，每个宝石都一个属性值a1,a2,…an.玩家在游戏前可以挑选x颗宝石，将这些宝石的属性值相乘组成玩家的属性值。游戏玩家需要y点属性值，请帮助游戏玩家计算有多少种计算方式。

输入描述

第一行：三个整数n,x,y

• 第一个整数n(0 < n <20)表示宝石总数量。
• 第二个整数x(0<x <=n)，表示可以选择宝石个数
• 第三个整数y，表示通过游戏需要的属性值

第二行：n个整数，a1,a2,…an(-100 < ai < 100)，表示每个宝石的属性值。

输出描述

输出一个整数，表示玩家可以通过游戏的挑选方式的数量。

用例1

输入

4 2 8 2 -3 4 5

输出

3

题解

思路：二进制枚举

1. 于n < 20数据量对应2^20比较小，可以采用二进制暴力枚举判断。
2. 二进制枚举的规则：如果一个20位的二进制数，二进制为1的位置代表会选择对应宝石，例如101表示会选中第1和第3个宝石
3. 枚举范围为[1, 2 ^ n -1], 对于每个枚举值先求出所有二进制为1的位置用数组position保存
   • 首先判断position的数量是否等于x，不等于直接跳过。
   • 将所有宝石的值进行相乘然后判断是否大于y,大于y的话直接结果+1。这里a的值范围比较大，非python用户尽量使用大的数据类型进行保存，防止溢出
4. 输出结果。

c语言

#include <stdio.h> int main() { int n, x; long long y; scanf("%d %d %lld", &n, &x, &y); int ans[25]; // 假设 n 不会太大（<=20 很常见） for (int i = 0; i < n; i++) { scanf("%d", &ans[i]); } int res = 0; // 枚举所有非空子集 for (int mask = 1; mask < (1 << n); mask++) { int cnt = 0; // 已选元素个数 long long product = 1; // 当前乘积 for (int i = 0; i < n; i++) { // 判断第 i 位是否被选中 if (mask & (1 << i)) { cnt++; // 超过 x 个，直接剪枝 if (cnt > x) { break; } product *= ans[i]; } } // 必须刚好选 x 个 if (cnt == x && product >= y) { res++; } } printf("%d\n", res); return 0; }

相关链接

本题包含其它多语言实现，可以点击跳转实现:华为OD机试双机位C卷 - 挑选宝石 (C++ & Python & JAVA & JS & GO)