前言
这道题理解起来不难，但是要找到一个合适的方法对题目进行优化，就会相对麻烦些。
蓝桥杯的题，真的到处都是坑的感觉。。。
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6
①、带分数中，数字1~9分别出现且只出现一次（不包含0）。
②、100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
①：如何实现在带分数中，数字1~9分别出现且只出现一次。我们可以考虑全排列，将每种排列都来一遍（感觉挺麻烦的，如果有更好的方法欢迎留言讨论）。
②：在例子中 100 = 3 + 69258 / 714，“3 + 69258 / 714”部分要符合数字1~9分别出现且只出现一次，这时可以用到我们字符串截取。拿上面的例子说，排列为369258714，我们截取了字符串3、字符串69258、字符串714，然后将三个字符串转换为int类型变量，看看是否符合条件（100 = 3 + 69258 / 714）符合则记录下来。
在C++中，在字符串要有序的前提下，我们能使用现成的函数完成字符串的全排列。例如：string s=“123456789”;，字符串s已经有序。通过 while(next_permutation(s.begin(), s.end())); 不断将s进行全排序，当s的全排序全部排完后，跳出循环。可能你会觉得这个有什么用？让我们带着这个问题看看代码设计吧！
string s="123456789";
do
{
....
}
while(next_permutation(s.begin(), s.end()));
我们这里用do-while的循环体，保证s每进行一次全排列就会先进行do包含的语句。
在s字符串中，从下标为i的位置，向右截取len长度的字符串，得到a字符串。
将字符串s转换为int类型变量a。
通过我们的解题思路和工具结合，我们可以得到以下代码一。
//全排列 next_permutation(s.begin(),s.end())
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
#define ll long long
ll ans=0;
int main()
{
// clock_t start, finish;
// start = clock();
int n;
string s="123456789";
// sort(s,s+9);
cin>>n;
do
{
for(int i=1; i<=7; i++)
{
string a=s.substr(0,i);
int inta=atoi(a.c_str());
if(inta>=n) break;
for(int j=1; j<=8-i; j++)
{
string b=s.substr(i, j);
int intb=atoi(b.c_str());
string c=s.substr(j+i);
int intc=atoi(c.c_str());
if(intb%intc==0&&inta+intb/intc==n)
ans++;
}
}
}
//使用next_permutation前要先排序
while(next_permutation(s.begin(), s.end()));
cout<<ans;
// finish = clock();
// double _time = (double)(finish - start) / CLOCKS_PER_SEC;
// printf("\ntime:%llf", _time);
return 0;
}
好啦，恭喜你答对了题目一半，为什么是一半呢？因为如果你拿去评测的话， 你会发现：运行超时！
下面是代码二在N=100条件下的运行时间time （单位秒）
原因：substr函数返回的是值(而不是引用或指针) 在多次调用中传递了大量对象(而不是引用或指针) 导致了耗时多。
在代码里，substr函数被放在内层循环中，被调用的次数很多，这样的对程序运行总时间的影响就增大了，拖慢了程序运行速度。
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
#define ll long long
ll ans=0;
int parse(string &s, int a, int b)//字符串转换为int类型
{
int temp=0;
for(int i=a; i<b; i++)
{
temp+=s[i]-'0';
if(i<b-1)
temp*=10;
}
return temp;
}
int main()
{
// clock_t start, finish;
// start = clock();
int N;
string s="123456789";
// sort(s,s+9);
cin>>N;
do
{// 1234567+8/9
for(int i=1; i<=7; i++) //分割第一个数据长度
{
int inta = parse(s, 0, i);
if(inta>N) break;
//1+2345678/9
//12+345678/9
//1+2/3456789
for(int j=1; j<=8-i; j++) //分割第二个数据长度
{
int intb=parse(s, i, j+i);
int intc=parse(s, j+i, s.length());//分割第三个数据
if(intb%intc==0&&inta+intb/intc==N)
{
// cout<<inta<<"+"<<intb<<"/"<<intc<<endl;
ans++;
}
}
}
}
while(next_permutation(s.begin(), s.end()));
cout<<ans;
// finish = clock();
// double _time = (double)(finish - start) / CLOCKS_PER_SEC;
// printf("\ntime:%llf", _time);
return 0;
}
优化：截取字符串函数传参采用传指针或引用(即在parse 的string参数右侧加一个&)。
下面是代码二在N=100条件下的运行时间time （单位秒）
时间上满足1s内，可以通过评测。
下面还能够再通过优化算法的方式，进一步缩短运行时间。
#include<bits/stdc++.h>
#include<time.h>
using namespace std;
#define ll long long
ll ans=0;
int parse(string& s, int a, int b)//字符串转换为int类型
{
int temp=0;
for(int i=a; i<b; i++)
{
temp+=s[i]-'0';
if(i<b-1)
temp*=10;
}
return temp;
}
int main()
{
// clock_t start, finish;
// start = clock();
int N;
string s="123456789";
// sort(s,s+9);
// N=100;
cin>>N;
do
{
for(int i=1; i<=7; i++)
{
int inta = parse(s, 0, i);
if(inta>N) break;
//1+2345678/9
//12+345678/9
//1+2/3456789
for(int j=1; j<=8-i; j++)
{
if(j<9-i-j) continue; //排除多余情况
int intb=parse(s, i, j+i);
int intc=parse(s, j+i, s.length());
if(intb%intc==0&&inta+intb/intc==N)
{
// cout<<inta<<"+"<<intb<<"/"<<intc<<endl;
ans++;
}
}
}
}
while(next_permutation(s.begin(), s.end()));
cout<<ans;
// finish = clock();
// double _time = (double)(finish - start) / CLOCKS_PER_SEC;
// printf("\ntime:%llf", _time);
return 0;
}
优化：排除多余判断情况。
下面是代码三在N=100条件下的运行时间time（单位秒）
这道题思路固然重要，但是优化也很重要。
在蓝桥杯的比赛中，都是提交代码，我们不能都提前判断我们的代码是否能够通过所有评测数据，所以要尽量将时间复杂度降到最小。
感谢评论区的朋友，对我的文章提出指正√
希望能够将自己的一些学习经验分享给有需要的人。
我是小郑，一个坚持不懈的小白。