前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ACM刷题之路(三)dfs+排列 第K个幸运排列

ACM刷题之路(三)dfs+排列 第K个幸运排列

作者头像
Designer 小郑
发布2023-07-31 15:23:07
1180
发布2023-07-31 15:23:07
举报
文章被收录于专栏:跟着小郑学JAVA跟着小郑学JAVA

题目链接https://vjudge.net/problem/51Nod-1635

题解:这题是这学期最后一次模拟赛的A题:

题目大意就是说1到n的第m个全排列中,求下标和数值都是幸运数的个数其中数字全是4或者7的数叫做幸运数

刚开始想了好久,其实跟上次那题全排列类似,前面的数不受影响,可以用深搜判断,因为下标就等于数值,不需要一一分类讨论,第ii项开始,会因为第m个全排列而发生变化,所以要用for循环遍历一遍,当下标和数组的值都是幸运数,再让ans++。

总体思路挺简单的,判断是否幸运数的函数也不难写,中间的全排列产生如果看不懂,可以参考我以前写的博客。

把答案分为两部分,第一部分为1到ii-1不会变的数,第二部分为ii到n会变的数,一个深搜,一个遍历。

直接上代码:

代码语言:javascript
复制
#include<iostream>  
using namespace std;

long long n, m, ans, a[100], f[100], g[100], n1;
long long pd(long long t){//a数组用于判断是否为幸运数
	long long n1 = 0;
	while (t){
		n1++;
		a[n1] = t % 10;
		t /= 10;
		if (a[n1] != 4 && a[n1] != 7)return 0;
	}
	return 1;
}
void dfs(long long x) {//dfs深搜
	if (x > n1)return;
	if (x)ans++;
	dfs(x * 10 + 4);
	dfs(x * 10 + 7);
}
int main() {
	long long i, ii, j, t, k, s, la;
	scanf("%lld%lld", &n, &m);//1到n的第k个排列
	t = 1;
	for (i = 2; i <= n; i++) {  //这里计算n的阶乘
		if (t > m)break;     //用于计算第m种排列会影响最后多少个数字
		t *= i;
		la = i;
	}
	if (t < m) { //如果n的阶乘比m小,输出-1
		printf("-1");
		return 0;
	}
	ii = la;//ii是受影响的最后数字的总排列个数
	k = t;//k是受影响的最后数字的总排列阶乘
	for (i = 1; i <= ii; i++){
		g[i] = 1;
	}
	for (i = n - ii + 1; i <= n; i++){ //最后ii+1个数遍历一遍
		k /= (ii - (i - (n - ii + 1)));//相当于n!除以n
		s = 0;
		for (j = 1; j <= ii; j++){
			if (g[j]){
				s++;
				if (s * k >= m){
					m -= (s - 1) * k;
					g[j] = 0;
					f[i - (n - ii)] = j + (n - ii);
					break;
				}
			}
		}
	}//实现第m个全排列
	//全排列产生方法不会的看这里https://blog.csdn.net/qq_41464123/article/details/80584899
	n1 = n - ii;			//n1代表全排列中前面不变的数的个数
	dfs(0);					//0到n1是不会变的 所以直接暴力模拟
	for (i = 1; i <= ii; i++)//显然,ii是第m个排列影响到的最后几位的位数,
		//会根据m的排列而变化  所以要判断下标和数值
		if (pd(f[i]) && pd(n - ii + i))ans++;
	printf("%lld\n", ans);//最后输出两部分的和
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-06-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档