带分数

本文最后更新于:2 小时前

[蓝桥杯 2013 省 B] 带分数

题目描述

$100$ 可以表示为带分数的形式:$100 = 3 + \frac{69258}{714}$。

还可以表示为:$100 = 82 + \frac{3546}{197}$。

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

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

输入格式

从标准输入读入一个正整数 $N(N<10^6)$。

输出格式

程序输出数字 $N$ 用数码 $1$ ~ $9$ 不重复不遗漏地组成带分数表示的全部种数。

注意:不要求输出每个表示,只统计有多少表示法!

样例 #1

样例输入 #1

1
100

样例输出 #1

1
11

样例 #2

样例输入 #2

1
105

样例输出 #2

1
6

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

理解:

n=a+b/c;则把a用dfs找出来,每找出一个a,立刻搜寻对应的c,找到c之后,cn-ac=b;看cn-ac之后是否等于b,若等于,则符合条件。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
const int N=20;
bool st[N],backup[N];
int ans;
bool check(int a,int c)
{
int b=n*c-a*c;
if(!a||!b||!c)return false;

memcpy(backup,st,sizeof st);
while(b)
{
int x=b%10;
b/=10;
if(!x||backup[x])return false;
backup[x]=true;
}
for(int i=1;i<=9;i++)
{
if(!backup[i])
return false;
}
return true;
}
void dfs_c(int u,int a,int c)//u表示当前用了几个数字
{
if(u==n)return;
if(check(a,c))ans++;
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)//u表示当前用了几个数字
{
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;
}


带分数
http://example.com/2023/04/08/带分数/
作者
zzh
发布于
2023年4月8日
更新于
2023年4月24日
许可协议
原文链接: HTTPS://ZHANGZHIHAO-BLOG.GITHUB.IO
版权声明: 转载请注明出处!