解题思路:

本题采用排列组合的方式,保证严格递增,以题目为例,共七位,分为三组;

  1. 最高位为0时,只需要后两位严格递增即可,如何保证呢,从范围内抽取两个数即可满足,抽取两个数,我们就指定它用递增方式去放。所以我们只需要满足从1-7中抽取两个数即可满足。

  2. 最高位不为0时,可以采用for循环遍历的方式,遍历最高位的值。指定最高位,后两位用排列组合的方式,不过后两位的范围要对应发生更改,只需要用上面的范围减去最高位的值,抽取的位数保持不变。


注意事项:

       排列组合的关键点在于:我们不需要去满足严格递增,因为当我们从几个数中,抽出两个数时,这个数就有一种情况来满足题目所需,即我们讲抽出来的数,按照要求放好即可,那么就转变成了抽取有多少种情况,即排列组合。

       除此之外,我们还需要去考虑,是否整除,如果整除,则不需要考虑最高位,因为最高位和其它没有什么区别,当不整除时,由于高位与低位的范围不一致,所以分开进行考虑。

下面是组合的代码:

int jiecheng(int x){//阶乘
	long long ret=1;
	for(int i=x;i>0;i--){
		ret *=i;
		
	}
	return ret;
}

int c(int x,int y){//组合
	
	long long int ret=0;
	
	ret=jiecheng(x)/jiecheng(y)/jiecheng(x-y);
	return ret;
}


参考代码:

#include<bits/stdc++.h>
using namespace std;

int jiecheng(int x){
	long long ret=1;
	for(int i=x;i>0;i--){
		ret *=i;
		
	}
	return ret;
}

int c(int x,int y){
	
	long long int ret=0;
	
	ret=jiecheng(x)/jiecheng(y)/jiecheng(x-y);
	return ret;
}
int main(){
	int k,w;
	cin>>k>>w;
	int wei=w/k;
	int max=pow(2,k)-1;
	int zui=pow(2,w%k)-1;
	long long int sum=0;
	//最高位是0,或正好w/k整除

	if(w%k){
		for(int i=2;i<=wei;i++){
			sum+=c(max,i);
		
		} 
		for(int i=1;i<=zui;i++){
			sum+=c(max-i,wei);
		}
	}
	
	if(w%k==0){
		for(int i=2;i<=wei;i++){
			sum+=c(max,i);
		} 
		
	}
	 cout<<sum;
	
	
	
	
	
	
	return 0;
}


点赞(0)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 1 条评论

l 2年前 回复TA