蓝桥杯 历届试题 带分数

  历届试题 带分数  

时间限制：1.0s   内存限制：256.0MB

直接用DFS搜索，假设n为156，整数不会超过三位，分别搜索整数位数为1-3三种情况下符合条件的答案，其中整数和分母搜索得出，分子计算得出，并且分子位数必须小于等于分母位数，代码如下，速度比全排列快不少，15MS通过，全排列需要200Ms左右。

#include<iostream>#include<cstring>using namespace std;int vis[10], vis1[10], ans, n;void dfs(int t,int left, int left_number, int right, int right_number){	if (left >= n) return;	if(left_number==t)	{int z = (n - left)*right;	int c = 0, ok = 1;	memset(vis1, 0, sizeof(vis1));	while (z)	{		int r = z % 10;		if (vis[r] || vis1[r] || r == 0) {			ok = 0;break;		}		else			vis1[r] = 1,			c++,			z = z / 10;	}	if (ok == 1 && c + left_number + right_number == 9)	{		ans++;return;	}	}	for (int i = 1;i <= 9;i++)		if (!vis[i])		{			if (right_number==0&&left<n)			{				vis[i] = 1;				dfs(t,left * 10 + i, left_number + 1, right, right_number);				vis[i] = 0;			}			if (left_number==t&&right_number<(9 - left_number) / 2)			{				vis[i] = 1;				dfs(t,left, left_number, right * 10 + i, right_number + 1);				vis[i] = 0;			}		}}int main(){	cin >> n;	int cnt=0,t=n;	while (t)	{		cnt++;		t = t / 10;	}	for (int i = 1;i <= cnt;i++)	dfs(i,0, 0, 0, 0);	cout << ans;	return 0;}