蓝桥杯-2016-全排列

2016-3-凑算式

B DEF
A + --- + ------- = 10
C GHI
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法这个算式共有多少种解法？

蓝桥杯-2016-全排列

坑：通分后能整除

#include<stdio.h>
#include<algorithm>
#include<iostream> 
/*

 全排列 
 坑点：1.通分后可以整除(求余为0)  (a[1]*y+a[2]*x) % (a[2]*y) == 0
 	   2.a[0]+通分后的一坨加和为10 
*/
using namespace std;
int a[9] = {1,2,3,4,5,6,7,8,9};
int ans;

bool check()
{
	int x = a[3]*100 + a[4]*10 + a[5];
	int y = a[6]*100 + a[7]*10 + a[8];
	if( (a[1]*y+a[2]*x) % (a[2]*y) == 0 && a[0] + (a[1]*y+a[2]*x) / (a[2]*y) == 10 )
	{
		return true;
	}
	return false;
}

int main(int argc, char *argv[])
{
	do{
		if(check())
		{
			ans++;
		}
	}while(next_permutation(a,a+9));
	
	cout<<<<ans<<endl;
}

2013-9带分数

100 带分数的形式：100 = 3 + 69258 / 714

100 = 82 + 3546 / 197

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

100 有 11 种表示法。

/*
输入输出样例
100 11
105 6
2013 5
*/

思路：1-9全排列，先插入+，再插入/，验算等式，计数

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<string>
using namespace std;
string s = "123456789";
int n,ans = 0;
/*
	const char *c_str();			返回一个指向正规C字符串的指针, 内容与本字符串相同. 
	int atoi( const char *str ); 	将字符串str转换成一个整数并返回结果。

*/

bool check(int n)
{
	const char *arr = s.c_str();
	for(int i=1; i<=7; i++)     //+号前的串的长度 
	{
		//string a = s.substr(0,i);   
		//int inta = atoi(a.c_str());
		int inta = parse(arr,0,i);
		if( inta>=n ) continue;    //这个逻辑不能忘 break与continue区别 
		for(int j=1; j<=9-1-i; j++)   // +和/之间的串的长度
		{
			//string b = s.substr(i,j);
			//string c = s.substr(i+j,9-i-j);
			//	int intb = atoi(b.c_str());
			//	int intc = atoi(c.c_str());
			int intb = parse(arr,i,j);	
			int intc = parse(arr,i+j,9-i-j);    //这是/后面的串
			if( inta+intb/intc==n && intb%intc==0 )  {return true;}
			
		}
	}
}


int main(int argc, const char *argv[])
{
	scanf("%d",&n);
	do{
		if(check(n))
		{
			ans++;
		}
	}while(next_permutation(s.begin(), s.end()));
	cout<<ans<<endl;
	//cout<<parse(s.c_str(),2,4)<<endl;
}

(1)字符串的相关表示：

字符串的使用很重要，但是本题有坑，

不能反复截取字符串substr（申请内存空间新建串，拷贝）所以尽量规避，运行超时 用字符数组处理

1 s.substr()  截取子串 

  s.substr(pos, n)    截取s中从pos开始（包括0）的n个字符的子串，并返回
  s.substr(pos)        截取s中从从pos开始（包括0）到末尾的所有字符的子串，并返回

2 s.c_str(); 将字符串以C字符数组的形式返回  

   const char *c_str();			返回一个指向正规C字符串的指针, 内容与本字符串相同. 

3 atoi()  将字符串转换成整数  

	int atoi( const char *str ); 	将字符串str转换成一个整数并返回结果。

string a = s.substr(0,i);
int inta = atoi(a.c_str());

4 next_permutation(s.begin(),s.end()) 字符串起始与终止位置表示

(2)使用字符数组将子串化为整数

/*手工从字符串pos开始,取长为len的子串，并将其化为整数
  传入字符数组型的字符串，位置，长度*/
int parse(const char *arr, int pos, int len)
{
	int t=1,num=0;
	for(int i=pos+len-1; i>=pos; i--)
	{
	    num += (arr[i]-'0')*t;
		t*=10;
	}
	return num;
}

（3)check() i 和 j 代表的意义

i +号前的串的长度

j +和/之间的串的长度

注意字符数组下标，以及for循环起点和终点的条件

蓝桥杯-2016-全排列

蓝桥杯-2016-全排列

2016-3-凑算式

2013-9带分数

相关推荐