首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >带分数 第四届蓝桥杯省赛C++B组

带分数 第四届蓝桥杯省赛C++B组

作者头像
dejavu1zz
发布2020-10-23 15:17:18
4470
发布2020-10-23 15:17:18
举报

题意描述

100 可以表示为带分数的形式:

在这里插入图片描述
在这里插入图片描述

还可以表示为:

在这里插入图片描述
在这里插入图片描述

注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。

类似这样的带分数,100 有 11 种表示法。

输入格式 一个正整数。

输出格式 输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围 1≤N<106

输入样例1: 100 输出样例1: 11 输入样例2: 105 输出样例2: 6

思路一:

题目要求是将一个数字写成a+c/b的形式,所以我们可以先对数字1到9求全排列,然后再暴力枚举出a,b,c如果a,b,c符合题目的要求,则使计数变量加一。这里还可以剪枝优化一下,如果a大于n的话,那么一定不成立,所以就可以略去a大于n的情况

AC代码

#include<iostream>
using namespace std;
const int N=15;
int path[N];
bool st[N];
int n;
int ans=0;
int regSum(int l,int r){
    int m=0;
    for(int i=l;i<=r;i++){
        m=m*10+path[i];
    }
    return m;
}
void dfs(int u){
    if(u==10){
        for(int i=1;i<=7;i++){
            for(int j=i+1;j<=8;j++){
                int a=regSum(1,i);
                if(a>=n) return;
                int b=regSum(i+1,j);
                int c=regSum(j+1,9);
                if(n*c-a*c==b) ans++;
            }
        }
        return;
    }
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            path[u]=i;
            dfs(u+1);
            st[i]=false;
        }
    }
    
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans<<endl;
}

思路二:

思路一是对a,b,c都求了一遍,但实际上我们可以只求a和c,将题目所给式子化简可以得到nc-ac=b,所以我们可以使用在一个dfs中嵌套一个dfs,来分别枚举a和c,然后由此得出b,再进行判断即可。同样可以和思路一同样的进行剪枝优化。

AC代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=20;
int n;
int ans=0;
bool st[N],backup[N];
bool check(int a,int c){
    ll b=n*(ll)c-a*(ll)c;
    if(!b||!a||!c) return false;//如果a,b,c其中有一个为0,返回false
    memcpy(backup,st,sizeof st);//因为有回溯的过程,所以要用一个副本数组来修改
    while(b){
        if(backup[b%10]||!(b%10)) return false;//如果b的某一位为0或者该数字已经使用,返回false
        backup[b%10]=true;
        b/=10;
    }
    for(int i=1;i<=9;i++){
        if(!backup[i]) return false;//如果有数字没有用过,返回false
    }
    return true;
}
void dfs_c(int u,int a,int c){
    if(check(a,c)){
        ans++;
        return;
    }
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            dfs_c(u+1,a,c*10+i);
            st[i]=false;
        }
    }
}
void dfs_a(int u,int a){
    if(a>=n) return;
    if(a) dfs_c(u,a,0);
    
    for(int i=1;i<=9;i++){
        if(!st[i]){
            st[i]=true;
            dfs_a(u+1,a*10+i);
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs_a(0,0);
    cout<<ans<<endl;
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意描述
  • 思路一:
  • AC代码
  • 思路二:
  • AC代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档