蓝桥杯2013年第四届真题-带分数-题解（C++代码）

解题思路: 由题意可知1-9都要出现，且只能出现一次。自然想到用全排列来做，只需要加入一些判断即可（最后面的完整改进后完整代码有一些细节讲解）

注意事项: 在这个网站可以运行但是在蓝桥杯网站运可能会超时

参考代码（1）:在这个网站可以运行，但是在蓝桥杯网站会超时，但是也可以学习一些一些函数及字符串处理

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

//这种方法超时，因为多次用了substr（）来截取字符串，每次都要拷贝，和扫描
//过于耗时
int main(){
	int n;
	int ans = 0;
	cin>>n;
	std::string s = "123456789"; 
	do {
			for(int i=0;i<=7;i++){
				string a=s.substr(0,i); 
				int inta = atoi(a.c_str());
				if(inta >= n) break;
				
				for (int j=1;j<=9-i-1;j++){
					string b = s.substr(i,j);
					string c = s.substr(i+j,9);
					int intb = atoi(b.c_str());
					int intc = atoi(c.c_str());
					if(intb%intc==0&&inta+intb/intc==n) ans++;
				}
				
			}
		} while(std::next_permutation(s.begin(),s.end())) ;
		
	cout<<ans;
	return 0;
}

改进代码：因为我们的atoi函数没有选择字符串长度就是只转化某个位置的字符串，所以我们需要自己定义一个转化函数。

//pos代表串开始的位置，len代表长度（包含pos） 
int parse(const char *arr,int pos,int len){
	int ans = 0;
	int t = 1;
	for(int i=pos+len-1-1;i>=pos-1;i--){
		ans+=(arr[i]-'0')*t;
		t*=10;
	}
	return ans;
}

改进后完整代码：

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

int parse(const char *arr,int pos,int len){
	int ans = 0;
	int t = 1;
	for(int i=pos+len-1-1;i>=pos-1;i--){
		ans+=(arr[i]-'0')*t;
		t*=10;
	}
	return ans;
}
int main(){
	int n;
	int ans = 0;
	cin>>n;
	std::string s = "123456789"; 
	do {
			const char *str = s.c_str();// 由于s.c_str()这个函数返回的是const的类型，
										// 所以我们上面定义的函数的参数也要是const
			for(int i=0;i<=7;i++){
				int inta = parse(str,1,i); // +号前的数字 
				if(inta >= n) break; // 如果单inta就>=n,那后面就不用遍历了，进入下一种排列
				
				for (int j=1;j<=9-i-1;j++){
				int intb=parse(str,i+1,j); // +和/中间的数字
				int intc=parse(str,i+j+1,9-i-j); // / 后面的数字
				if(intb%intc==0&&inta+intb/intc==n) ans++;
				}
				
			}
		} while(std::next_permutation(s.begin(),s.end())) ;
		
	cout<<ans;
	return 0;
}