历届试题 带分数

问题描述

100 可以表示为带分数的形式：$100=3+69258/714$。
还可以表示为：$100=82+3546/197$。
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。

输入格式

从标准输入读入一个正整数 $N(N<1000\ast 1000)$ 。

输出格式

程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！

样例输入 1

100

样例输出 1

11

样例输入 2

105

样例输出 2

6

—— 题解 ——

本题给人的第一感觉是，枚举：对任意的输入，通过枚举进行判断。
但是对于枚举而言，势必需要考虑其枚举范围。
先来看一下本题提供的式子：

$$N=a+\frac{b}{c}$$

假设题目输入的 $N=100$，那么 $a$ 的枚举范围就是 $1-99$，对于后面的 $\frac{b}{c}$ 的范围相较而言就要大很多。因为剩下的项是由一个除法式子组成的，而这里面的两个数的排列情况又是庞大的。并且最恐怖的是，后面的 $\frac{b}{c}$ 这一部分还会随着 $a$ 的变化又重新组合，于是乎~~~陷入困难。

这时候必须另辟捷径了。
熟话说的好，失败乃成功之母。
在上面的分析中，我相信同学们应该都注意到了一个点。那就是，无论 $N$ 是多少，在你的枚举过程中，总是会重头到尾的去把可能的情况枚举一遍。并且为了便于枚举，总是会按照某种逻辑来进行（当然，这个情况下我相信大部分同学都是依照全排列的顺序来进行的）。

既然如此，反正对于任何的输入（$N$），都会去走一遍那个排列的过程，那么为什么我们不把这些枚举情况都保存下来呢？（类似于打表）。

话说到这里，相信你也或多或少有一些思路了。
是的，我们的解题思路就是从这里下手：
将 $1-9$ 进行全排列，然后从中间按照某种顺序截取三段，以这三段分别作为 $a、b、c$，接着带入那个公式，并将得到的结果保存在某个数组中( cnt[ a+b/c ]++ )，最后利用数组的随机访问特性直接输出结果即可。即假设给出下面某种排列：123456789，则你可以在这串数中任意插入两根棍子得到：123 | 4567 | 89 三部分。9 个数字存在 8 个间隙，因此 “插棍子” 可以通过两重循环实现。

分析到这里，还不够，为了确保时间上的可行，我们还要分析一下程序大概的枚举次数。
要知道 9!=362,880 ，而对于每一个排列的结果又有 $C_8^3=56$ 种情况，这样一来，总的枚举情况就有 362,880 ╳ 56=20,316,800，约两千万的次数。
还能接受！

需要注意的是，在代码中实现 “插棍” 将通过三重小循环实现（详见代码部分），因此实际上的程序赋值语句大致为两千万╳10=两亿次。

前面说了，我们是在打表。也就是说上面的代码执行结束后，会生成一个记录每个数的带分数的数量的数组。这样，对于后面的任何输出都可以直接将其带分数数量输出，这样也就不用担心超时了。

下面给出本题的完整代码：

—— 分割线 ——

#include<iostream>
#include<algorithm>
using namespace std;

int p[9];							//用于放置基本的9个数字
int cnt[10000005];					//打表用到的数组

int main()
{
    for(int i=0;i<9;i++)
        p[i]=i+1;
    int a,b,c,ans;
    do{
        for(int i=0;i<=6;i++)
            for(int j=i+1;j<=7;j++)
            {
            	a=b=c=ans=0;
                for(int k=0;k<=i;k++)
                {
                    a=a*10+p[k];
                }
                for(int k=i+1;k<=j;k++)
                {
                    b=b*10+p[k];
				}
                for(int k=j+1;k<=8;k++)
                {
                    c=c*10+p[k];
                }
                if(b%c==0)
                {
                    ans=a+b/c;
                    if(ans<1000000)
                    cnt[ans]++;
                }
            }
    }while(next_permutation(p,p+9));  //这是一个求一个排序的下一个排列的函数，可以遍历全排列,要包含头文件<algorithm>
    int n;
    cin>>n;
    cout<<cnt[n];    
}

END