P8599 [蓝桥杯 2013 省 B] 带分数

题目知识点：全排列加指针划分数组。
链接：https://www.luogu.com.cn/problem/P8599

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
using namespace std;
typedef long long ll;


int numlst[15];//可以删去
bool vis[15] = { 0 };//用于全排列记录是否被加入
int target[15] = { 0 };//记录当前队形
int n;
int ans = 0;
int get_num(int b, int a)//记录区间[a,b]形成的数字
{
	int aa = 0;
	for (int i = b; i <= a; i++)aa = aa * 10 + target[i];
	return aa;
}
bool judge()//判断能不能形成
{
	int i = 1;
	int final = 9;
	int j = i;
	for (j; j < final; j++)
	{
		int k = j + 1;//这里不要把赋值k的写到循环外面了，之前就是犯这个错误
		int numint = 0;
		numint = get_num(i, j);//get_num会更好
		if (numint > n)return false;//剪枝，整数部分
		for (k; k < final; k++)
		{
			int fz = 0;
			fz = get_num(j + 1, k);
			int fm = 0;
			fm = get_num(k + 1, final);
			if (fz % fm == 0 and fz / fm + numint == n)return true;
		}
	}


}
void dfs(int num)
{
	if (num == 9)//如果递归到第9层，那么就可以判断并返回，其实正确的应该改成：补充
		if (judge())
		{
			ans++;
			return;
		}
	for (int i = 1; i < 10; i++)
    //全排列的代码
	{
		if (!vis[i])
		{
			vis[i] = 1;
			target[num+1] = numlst[i];
			dfs(num+1);
			vis[i] = 0;
		}
	}
}
int main()
{
	for (int i = 1; i < 10; i++)numlst[i] = i;
	cin >> n;
	dfs(0);
	cout << ans;
	return 0;
}

上面代码：
if (num == 9)//如果递归到第9层，那么就可以判断并返回，其实正确的应该改成：补充
		if (judge())
		{
			ans++;
			return;
		}
改为：
if (num == 9)
{
	if (judge())ans++;
    return;
}
会更符合逻辑，因为不一定得judge才退出，如果judge是false一样得退出

由于一些dinner错误调试了十几分钟