poj 3208 Apocalypse Someday（数位dp）

客官°小女子只卖身不卖艺 2021-11-29 06:36 224阅读 0赞

## 题意：给定n，输出第n大包含666的数字。 ##

## 分析：数位dp，详见《算法竞赛进阶指南》P342-344。 ##

## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    long long f[21][4];
    int t, n, m;
    
    void prework() {
    	f[0][0] = 1;
    	for (int i = 0; i < 20; i++) {
    		for (int j = 0; j < 3; j++) {
    			f[i + 1][j + 1] += f[i][j];
    			f[i + 1][0] += f[i][j] * 9;
    		}
    		f[i + 1][3] += f[i][3] * 10;
    	}
    }
    
    int main() {
    	prework();
    	cin >> t; // 数据组数
    	while (t--) {
    		scanf("%d", &n); // 题目中的X
    		// 第n个魔鬼数有m位
    		for (m = 3; f[m][3] < n; m++);
    		// 试填第i位，末尾已有k个6（k=3也表示已经是魔鬼数）
    		for (int i = m, k = 0; i; i--) {
    			// 从小到大枚举第i位填的数字j
    			for (int j = 0; j <= 9; j++) {
    				// 求出后边的i-1位有多少种填法能让整个数是魔鬼数
    				long long cnt = f[i - 1][3];
    				if (j == 6 || k == 3)
    					for (int l = max(3 - k - (j == 6), 0); l<3; l++)
    						cnt += f[i - 1][l];
    				// 如果cnt比n小，说明第n个魔鬼数的第i位应该比j更大
    				if (cnt < n) {
    					n -= cnt;
    				}
    				// 否则，第i位就应该是j
    				else {
    					if (k < 3) {
    						if (j == 6) k++; else k = 0;
    					}
    					printf("%d", j);
    					break;
    				}
    			}
    		}
    		printf("\n");
    	}
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3252-Round Numbers【二进制数位DP】

题意：问你一个区间内有多少个二进制下0的个数比1的多的数。思路：dp\[i\]\[j\]\[k\] 表示第i位二进制长度为k，其中0的个数为j的答案，然后剩下的就是一些细节

桃扇骨/ 2023年06月01日 12:46/ 0 赞/ 25 阅读

相关 POJ 3208-Apocalypse Someday【数位DP+二分】

题意：给你一个n(n<5e7)，让你找到第n个包含“666”的数。思路：妥妥的数位DP，我们可以考虑二分答案，左边界为0，右边界我提前试了一下发现在（1<< 32）之内，我

秒速五厘米/ 2023年06月01日 11:13/ 0 赞/ 15 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 242 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 220 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 330 阅读

相关【数位DP】Round Numbers POJ - 3252

Think: 1知识点：数位DP+二进制 2题意：输入一个区间判断有多少个“Round Number”，“Round Number”的定义为其二进制表示中0的数量大于等

阳光穿透心脏的1/2处/ 2022年06月08日 14:08/ 0 赞/ 180 阅读

相关 POJ3208:Apocalypse Someday

题目描述 The number 666 is considered to be the occult “number of the beast” and is a we

梦里梦外;/ 2021年12月24日 16:25/ 0 赞/ 113 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 327 阅读

相关 poj 3208 Apocalypse Someday（数位dp）

题意：给定n，输出第n大包含666的数字。分析：数位dp，详见《算法竞赛进阶指南》P342-344。代码： include<iostream>

客官°小女子只卖身不卖艺/ 2021年11月29日 06:36/ 0 赞/ 225 阅读

相关 poj3208 Apocalypse Someday 题解报告

[题目传送门][Link 1] 【题目大意】包含连续的至少三个6的数称为“beastly number”，将这些数从小到大排序，求第n个数。【思路分析】 (注：以

谁借莪１个温暖的怀抱￠/ 2021年11月02日 09:40/ 0 赞/ 212 阅读