华为OD机考双机位C卷 - 挑选宝石（Java Python JS C/C++ GO ）-平芜编程栈

题目描述

游乐园有一款互动游戏，游戏开始时会提供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

输出

说明

解题思路

这是一个经典的组合问题，可以通过深度优先搜索 (DFS) / 回溯法来解决。

由于宝石数量n nn较小（n < 20 n < 20n<20），我们可以遍历所有可能的组合，找出其中选取x xx个宝石且乘积等于y yy的方案数量。

解题思路

数据读取：读取n , x , y n, x, yn,x,y以及n nn个宝石的属性值。
回溯算法 (DFS)：
- 我们需要设计一个递归函数，记录当前遍历到的宝石索引 (index)、已经选取的宝石数量 (count) 以及当前的乘积 (currentVal)。
- 递归出口：
  - 如果已经选够了x xx个宝石：检查当前乘积是否等于y yy。如果是，计数器加 1。无论是否相等，都结束当前分支。
  - 如果遍历完了所有宝石（index == n）但没选够x xx个：结束当前分支。
- 递归分支：
  - 选择当前宝石：进入下一层递归，count + 1，乘积更新为currentVal * gems[index]。
  - 不选当前宝石：进入下一层递归，count不变，乘积不变。
数据类型：虽然单个属性值在int范围内，但多个数相乘可能会超出int范围，建议使用long来存储乘积（尽管y yy也是输入值，但在中间计算过程中防止溢出是个好习惯）。

Java

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// 1. 读取 n, x, yif(!scanner.hasNext())return;intn=scanner.nextInt();intx=scanner.nextInt();inty=scanner.nextInt();// 2. 读取宝石属性值long[]gems=newlong[n];for(inti=0;i<n;i++){gems[i]=scanner.nextLong();}intres=0;inttotalStates=1<<n;// 2的n次方// 3. 二进制枚举所有组合for(inti=0;i<totalStates;i++){// 优化：利用 bitCount 快速判断当前组合是否选了 x 个if(Integer.bitCount(i)!=x){continue;}longprod=1L;// 计算当前组合的乘积for(intj=0;j<n;j++){// 判断二进制第 j 位是否为 1if((i&(1<<j))!=0){prod*=gems[j];}}// 4. 判断条件// 根据用例1 (目标8，输出3)，这里必须是 "大于等于"// 2*4=8, 2*5=10, 4*5=20，共3种if(prod>=y){res++;}}System.out.println(res);}}

Python

importsys# 1. 读取 n, x, yn,x,y=map(int,input().split())# 2. 读取宝石属性值gems=list(map(int,input().split()))res=0totalStates=1<<n# 2的n次方# 3. 二进制枚举所有组合foriinrange(totalStates):# 优化：利用 bit_count 快速判断当前组合是否选了 x 个ifbin(i).count('1')!=x:continueprod=1# 计算当前组合的乘积forjinrange(n):# 判断二进制第 j 位是否为 1if(i&(1<<j))!=0:prod*=gems[j]# 4. 判断条件# 根据用例1 (目标8，输出3)，这里必须是 "大于等于"# 2*4=8, 2*5=10, 4*5=20，共3种ifprod>=y:res+=1print(res)

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];rl.on('line',(line)=>{inputLines.push(line);}).on('close',()=>{// 1. 读取 n, x, yconst[n,x,y]=inputLines[0].split(' ').map(Number);// 2. 读取宝石属性值constgems=inputLines[1].split(' ').map(Number);letres=0;consttotalStates=1<<n;// 2的n次方// 3. 二进制枚举所有组合for(leti=0;i<totalStates;i++){// 优化：利用 bitCount 快速判断当前组合是否选了 x 个if(i.toString(2).split('1').length-1!==x){continue;}letprod=1n;// 计算当前组合的乘积for(letj=0;j<n;j++){// 判断二进制第 j 位是否为 1if((i&(1<<j))!==0){prod*=BigInt(gems[j]);}}// 4. 判断条件// 根据用例1 (目标8，输出3)，这里必须是 "大于等于"// 2*4=8, 2*5=10, 4*5=20，共3种if(prod>=BigInt(y)){res++;}}console.log(res);});

C++

#include<iostream>#include<vector>intmain(){// 1. 读取 n, x, yintn,x;longlongy;std::cin>>n>>x>>y;// 2. 读取宝石属性值std::vector<longlong>gems(n);for(inti=0;i<n;i++){std::cin>>gems[i];}intres=0;inttotalStates=1<<n;// 2的n次方// 3. 二进制枚举所有组合for(inti=0;i<totalStates;i++){// 优化：利用 __builtin_popcount 快速判断当前组合是否选了 x 个if(__builtin_popcount(i)!=x){continue;}longlongprod=1LL;// 计算当前组合的乘积for(intj=0;j<n;j++){// 判断二进制第 j 位是否为 1if((i&(1<<j))!=0){prod*=gems[j];}}// 4. 判断条件// 根据用例1 (目标8，输出3)，这里必须是 "大于等于"// 2*4=8, 2*5=10, 4*5=20，共3种if(prod>=y){res++;}}std::cout<<res<<std::endl;return0;}

Go

package main import ( "fmt" "math/bits" ) func main() { // 1. 读取 n, x, y var n, x int var y int64 fmt.Scan(&n, &x, &y) // 2. 读取宝石属性值 gems := make([]int64, n) for i := 0; i < n; i++ { fmt.Scan(&gems[i]) } res := 0 totalStates := 1 << n // 2的n次方 // 3. 二进制枚举所有组合 for i := 0; i < totalStates; i++ { // 优化：利用 bits.OnesCount 快速判断当前组合是否选了 x 个 if bits.OnesCount(uint(i)) != x { continue } prod := int64(1) // 计算当前组合的乘积 for j := 0; j < n; j++ { // 判断二进制第 j 位是否为 1 if (i & (1 << j)) != 0 { prod *= gems[j] } } // 4. 判断条件 // 根据用例1 (目标8，输出3)，这里必须是 "大于等于" // 2*4=8, 2*5=10, 4*5=20，共3种 if prod >= y { res++ } } fmt.Println(res) }

C语言

#include<stdio.h>#include<stdlib.h>intcountSetBits(intn){intcount=0;while(n){count+=n&1;n>>=1;}returncount;}intmain(){// 1. 读取 n, x, yintn,x;longlongy;scanf("%d %d %lld",&n,&x,&y);// 2. 读取宝石属性值longlong*gems=(longlong*)malloc(n*sizeof(longlong));for(inti=0;i<n;i++){scanf("%lld",&gems[i]);}intres=0;inttotalStates=1<<n;// 2的n次方// 3. 二进制枚举所有组合for(inti=0;i<totalStates;i++){// 优化：利用 countSetBits 快速判断当前组合是否选了 x 个if(countSetBits(i)!=x){continue;}longlongprod=1LL;// 计算当前组合的乘积for(intj=0;j<n;j++){// 判断二进制第 j 位是否为 1if((i&(1<<j))!=0){prod*=gems[j];}}// 4. 判断条件// 根据用例1 (目标8，输出3)，这里必须是 "大于等于"// 2*4=8, 2*5=10, 4*5=20，共3种if(prod>=y){res++;}}printf("%d\n",res);free(gems);return0;}