博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 3208 Apocalypse Someday
阅读量:6600 次
发布时间:2019-06-24

本文共 2979 字,大约阅读时间需要 9 分钟。

题意:

   将含有连续的三个6的数称为不吉利数,比如666,1666,6662,但是6266吉利。则666为第一个不吉利数,输入整数n,求第n个不吉利数。(n <= 5*10^7)

解法:

   如果是给出n,求n以内的不吉利数有多少个,就是一个普通的数位DP。所以,就二分答案,对于每一个mid,求一下小于等于mid的数中不吉利数的个数。

tag:二分法,数位DP

1 /*  2  * Author:  Plumrain  3  * Created Time:  2013-12-14 20:55  4  * File Name: DP-POJ-3208.cpp  5  */  6 #include 
7 #include
8 #include
9 10 using namespace std; 11 12 #define CLR(x) memset(x, 0, sizeof(x)) 13 typedef long long int64; 14 int64 d1[20][10][10], d2[20][10][10]; 15 16 int64 get_num(int64 x) 17 { 18 int len = 0, dit[30]; 19 bool xxx = 0; 20 while (x){ 21 dit[len++] = x % 10; 22 x /= 10; 23 if (len > 2 && dit[len-1] == 6 && dit[len-2] == 6 && dit[len-3] == 6) 24 xxx = 1; 25 } 26 dit[len] = 0; dit[len+1] = 0; 27 28 int64 ret = 0; 29 if (xxx) ret = 1; 30 bool flag = 0; 31 for (int i = len-1; i >= 0; -- i){ 32 for (int j = 0; j < 10; ++ j) 33 for (int k = 0; k < 10; ++ k) 34 ret += dit[i] * d2[i][j][k]; 35 36 if (flag){ 37 for (int j = 0; j < 10; ++ j) 38 for (int k = 0; k < 10; ++ k) 39 ret += dit[i] * d1[i][j][k]; 40 } 41 else { 42 if (dit[i+2] == 6 && dit[i+1] == 6 && dit[i] > 6){ 43 for (int j = 0; j < 10; ++ j) 44 for (int k = 0; k < 10; ++ k) 45 ret += d1[i][j][k]; 46 } 47 else if (dit[i+1] == 6 && dit[i] > 6){ 48 for (int j = 0; j < 10; ++ j) 49 ret += d1[i][6][j]; 50 } 51 else if (dit[i] > 6) ret += d1[i][6][6]; 52 } 53 54 if (dit[i] == 6 && dit[i+1] == 6 && dit[i+2] == 6) 55 flag = 1; 56 } 57 return ret; 58 } 59 60 int64 gao(int64 n) 61 { 62 int64 l = 0, r = 100000000000000; 63 while (l <= r){ 64 int64 mid = (l + r) >> 1; 65 if (get_num(mid) < n) l = mid + 1; 66 else r = mid - 1; 67 } 68 return l; 69 } 70 71 int main() 72 { 73 CLR (d1); CLR (d2); 74 d1[0][0][0] = 1; 75 for (int i = 0; i < 10; ++ i){ 76 d1[1][i][0] = 1; 77 for (int j = 0; j < 10; ++ j) 78 d1[2][i][j] = 1; 79 } 80 81 for (int i = 3; i < 15; ++ i){ 82 d2[i][6][6] += d1[i-1][6][6]; 83 d1[i][6][6] -= d1[i-1][6][6]; 84 for (int j = 0; j < 10; ++ j) 85 for (int k = 0; k < 10; ++ k) 86 for (int l = 0; l < 10; ++ l){ 87 d2[i][j][k] += d2[i-1][k][l]; 88 d1[i][j][k] += d1[i-1][k][l]; 89 } 90 } 91 92 int T; 93 scanf ("%d", &T); 94 while (T--){ 95 int64 n; 96 cin >> n; 97 cout << gao(n) << endl; 98 } 99 return 0;100 }
View Code

 

转载于:https://www.cnblogs.com/plumrain/p/POJ_3208.html

你可能感兴趣的文章
[unity3d]unity中打包成.unity3d格式并实现本地加载出来
查看>>
【软件推荐】用HTML开发跨桌面应用
查看>>
div垂直居中
查看>>
Decentralized Applications
查看>>
哪种语言的密码更容易破解?
查看>>
如何将MFC程序改为UNICODE类型
查看>>
Open***应用案例
查看>>
php代码规范
查看>>
在分片集群中追踪MongoDB的操作日志
查看>>
判断DataTable为空
查看>>
vs中调用WebService
查看>>
Spring Boot 系统要求
查看>>
【CentOS 7笔记35】,几个特殊符号和一些常用命令#171117
查看>>
五款免费的磁盘空间使用情况报告软件
查看>>
JAVA线程7 - 终止线程
查看>>
网卡绑定(服务器&&交换机),缓存服务器Squid架构配置
查看>>
linux下CPU、内存、IO、网络的压力测试,硬盘读写速度测试,Linux三个系统资源监控工具...
查看>>
Linux的lvm逻辑卷管理
查看>>
web网站加速之CDN(Content Delivery Network)技术原理
查看>>
Redis 数据结构-字符串源码分析
查看>>