首页 > 代码库 > [蓝桥杯]带分数
[蓝桥杯]带分数
题目链接:http://lx.lanqiao.cn/problem.page?gpid=T26
题目大意:1~9在a,b,c中出现且仅出现一次,要求输入n,输出符合要求的(a,b,c)的解的个数。
关键思想:a,b,c相连其实就是一个排列,只要将该排列依次分割成两部分就可以了。还可以剪枝:显然n>a,那么n的位数也大于等于a的位数;因为b要整除c,所以b的位数肯定大于等于c。
代码如下:
#include <iostream> #include <string> #include <algorithm> using namespace std; int a[10]={0,1,2,3,4,5,6,7,8,9}; int getValue(int x,int y){//得到数组下标x~y所代表的整数 int val=0; for(int i=x;i<=y;i++){ val=val*10+a[i]; } return val; } int main(){ int n,x,y,z; cin>>n; int cnt=0; int tmp=n,digit=0; while(tmp){ tmp/=10; digit++; }//求位数 do{ for(int i=1;i<=digit;i++){//剪枝1 for(int j=8;2*j>=i+9;j--){//剪枝2 x=getValue(1,i),y=getValue(i+1,j),z=getValue(j+1,9); if((y%z==0)&&(x+y/z==n))cnt++; } } }while(next_permutation(a+1,a+10));//全排列函数 cout<<cnt<<endl; return 0; }
[蓝桥杯]带分数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。