AcWing 1209. 带分数(蓝桥杯真题）

AcWing 1209. 带分数(蓝桥杯真题） AcWing 1209. 带分数(蓝桥杯真题）

参加y总课程讲的题目，为什么一看这种DFS题目就懵逼。考试的时候随缘吧。毕竟我做的题目太少了。我认为初学这种题目一定要吧搜索树画明白。不然脑袋根本难以想代码。

————————————————————————————
题目说的就是一个数字可以表示为一个整数加一个分数。这个分数不要求真分数。就是n = a + （b/c）；一共会分解产生a,b,c三个数。要求这三个数字，每个位上的数字刚好是1~9.注意1-9必须都出现，同时不能出现0；
————————————————————————————

我们这里有多种枚举方法但是我不懂啊。所以只能说一下最简单的那一种。就是先枚举a,b,c.然后判断这组数字是否合理。我看的代码思路是这样的先枚举a，有哪几种可能，在a的叶子节点上再搜索c。通过上面提到的公式，我们知道a和c之后，我们就可以算出b再判断是否合理就ok了

逐步分解一下问题。首先是对a的可能的判断

//这里输出的x是已经用了几个1-9的数字了。a是当前a的值是多少
//had_use[i]代表第i个数字是否已经被使用
//
void DFS_A(int x, int a)
{
	if(a >= n) return;
	if(a) DFS_C(x,a,0);//DFS_C是对c的进一步搜索

	//枚举当前位置可以用哪些数字
	for(int i =  1; i <= 9; i++) {
		if(!had_use[i]) {
			had_use[i] = 1;//使用这个数字
			DFS_A(x,a*10+i);//DFS下一层
			had_use[i] = 0;//回溯
		}
	}
}

对C的DFS

void dfs_c(int x,int a,int c)//x表示我们已经用了多少个数字
{
    if(x>=10)return;
    //如果我们把10个数字都用了的话，那就直接return了

    if(check(a,c))ans++;
    //如果符合要求，那么答案++

    for(int i=1;i<=9;i++)//否则的话我们把c从1到9全部枚举一遍
      if(!had_use[i])
      {
          had_use[i]=1;
          dfs_c(x+1,a,c*10+i);//dfs下一层。
          had_use[i]=0;
      }
}

check函数

bool check(int a,int c) {
   int b = n*c - a*c;//根据a，c计算b
   if(!a || !b || !c) return false;//数字不能为0
   memcpy(ever,had_use,sizeof had_use);//复制had_use数组。
   //为什么，因为你check的时候吧数组变了。你的dfs会受影响
   
   //判断b是否合理
   while(b) {
      int t = b%10;
      b/=10;
      if(!t ||ever[t]) return false;//每个数位都能是0且t还没有被使用
      ever[t] =1;//t已经使用
   }
//判断1-9是否都已经用了
   for(int i = 1; i <= 9; i++) {
      if(!ever[i])
         return false;
   }
   
   return true;
}

完整代码：

#include 
#include 
#include 
#include 

using namespace std;

const int N  = 520;

int had_use[N], ever[N];

int ans = 0;

int n;

bool check(int a,int c) {
   int b = n*c - a*c;
   if(!a || !b || !c) return false;
   memcpy(ever,had_use,sizeof had_use);
   while(b) {
      int t = b%10;
      b/=10;
      if(!t ||ever[t]) return false;
      ever[t] =1;
   }
   for(int i = 1; i <= 9; i++) {
      if(!ever[i])
         return false;
   }
   return true;
}

void dfs_c(int x,int a,int c) {
   if(x >= 10) return;

   if(check(a,c)) ans++;
   
   for(int i = 1; i <= 9; i++) {
      if(!had_use[i]) {
         had_use[i] = 1;
         dfs_c(x+1,a,c*10+i);
         had_use[i] = 0;
      }
   }

}

void dfs_a(int x, int a) {
   if(a >= n) return;
   if(a) dfs_c(x,a,0);

   for(int i = 1; i <= 9; i++) {
      if(!had_use[i]) {
         had_use[i] = 1;
         dfs_a(x+1,a*10+i);
         had_use[i] = 0;
      }
   }

}

int main() {
  scanf("%d", &n);
   dfs_a(0,0);
   cout << ans << endl;

   return 0;
}