P8599 [蓝桥杯 2013 省 B] 带分数(dfs+全排列+断点判断)

互联网 12 月前 0 4

本文介绍: 2.设置为每个排列设置两个断点，分为三部分：a,b,c。代码如下：（可用next_permut a tion全排列函数代替dfs）3.转换为乘法判断条件，满足加一。思路：1.深度枚举所有排列情况。

思路：1.深度 枚举所有排列情况

2.设置为每个排列设置 两个 断点，将排列分为三部分：a,b,c

3.转换为乘法判断 条件，满足加一

代码如下：（可用next_permut a tion全排列函数代替dfs）

#include&lt;iostream&gt;
#include<stdio.h&gt;
using namespace std;
int ans = 0;

int visit[11] = { 0 };

int arr[11] = { 0 }, k = 0;

int tonum(int l, int r) {//将num数组的第l至r个数转为一个数
	int re = 0;
	for (int i = l; i <r; i++) {
		re = re * 10 + arr[i];
	}
	return re;
}

void dec();

void dfs();

int l = 0;

int main()
{
	
	scanf("%d", &amp;l);
	dfs();
	cout << ans << endl;
	return 0;
}
void dfs()
{
	for (int i = 1; i <= 9; i++)
	{

		if (!visit[i])
		{
			visit[i] = 1;
			arr[k++] = i;
			dfs();
			if (k == 9)		dec();
			k--;
			visit[i] = 0;
		}
	}
}

void dec()
{
	for (int i = 1; i <= 7; i++)
	{	int a = tonum(0, i);
		for (int j = i; j <= 8; j++)
		{
			int b = tonum(i, j);
			int c = tonum(j, 9);
			if ((l - a) * c == b) {
				ans++;
			}
		}
	}
}