2019年9月训练(壹)数位DP (HDU 2089)
2024-09-05 09:46:09
开学之后完全没时间写博客....
HDU 2089 不要62(vjudge) 数位DP
思路:
题目给出区间[n,m] ,找出不含4或62的数的个数
用一个简单的差分:先求0~m+1的个数,再减去0~n的个数.
但问题依旧不简单,再次简化为求0~i位数中不含4或62的数的个数.
i= //0~9中
i= //0~99中
i= //0~999中
......
dp[i][] //0~i位数中的吉利数
dp[i][] //0~i位数中以2打头的吉利数
dp[i][] //0~i位数中的非吉利数(含4或62)
所以第i位数中的吉利数个数为:
dp[i][]=dp[i-1][]*-dp[i-][i]
第i位数中以2打头的幸运数个数为:
dp[i][]=dp[i-][]
第i位数中的非吉利数个数为:
dp[i][]=dp[i-][]*+dp[i-][]+dp[i-][]
同时初始值为:
dp[][]=;
dp[][]=;
dp[][]=;
AC码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][]; void INIT()
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=;i++)
{
dp[i][]=dp[i-][]*-dp[i-][];//在吉利数首位补除了4的9个数,减去在2前补6的个数
dp[i][]=dp[i-][];//吉利数在首位补2
dp[i][]=dp[i-][]*+dp[i-][]+dp[i-][];//不吉利的情况
}
} int work(int x)
{
int d[],cnt=,temp=x;
while(temp)
{
d[++cnt]=temp%;
temp/=;
}
d[cnt+]=;
int flag=,ans=;
for(int i=cnt;i>;i--)
{
ans+=d[i]*dp[i-][];//用前一位所以不吉利数推出
if(flag) ans+=d[i]*dp[i-][];// 之前有不吉利数
else
{
if(d[i]>) ans+=dp[i-][];//4
if(d[i]>) ans+=dp[i-][];//6
if(d[i+]==&&d[i]>) ans+=dp[i][];//62
}
if(d[i]==||(d[i+]==&&d[i]==)) flag=;
}
return x-ans;//减去不吉利数的个数
} int main()
{
int m,n;
INIT();
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==) break;
printf("%d\n",work(m+)-work(n));
}
return ;
}
2019-09-16 18:50:26
最新文章
- iOS 开发者账号到期续费流程
- 1.Android 视图及View绘制分析笔记之setContentView
- Spring实战 (第3版)——AOP
- PHP之MVC项目实战
- mysql 常用操作指令
- iOS开发--动画篇之layout动画深入
- ExtJS4.2学习(八)表格限制输入数据的类型(转)
- 定义Foo() 函数,弹出对话框提示当前选中的是第几个单选框
- Delphi 的接口机制——接口操作的编译器实现过程(2)
- 业务逻辑 : forex &; mlm
- Phaser文档访问不了,下载英文版文档到本地,已经共享在国内网站上面
- Python3.6下scrapy框架的安装
- 前端 SPA 单页应用数据统计解决方案 (ReactJS / VueJS)
- 如何在xlwt中编写多个列的单元格?
- implode() 数组元素组合函数
- js 时间戳转换为‘yyyy-MM-dd hh:mm’格式(es6语法)
- 正则表达式匹配URL或者网址
- laravel框架容器管理
- [翻译]EntityFramework Core 2.2 发布
- 用PE系统安装原版XP
热门文章
- neo4j 一些常用的CQL
- codeforces#1165 F2. Microtransactions (hard version) (二分+贪心)
- Linux 网络通信命令之 netstat
- HA 模式 Hadoop+ZooKeeper+Hbase启动顺序
- Elasticsearch删除数据之_delete_by_query
- 论一种基于JS技术的WEB前端动态生成框图的方法
- python 快速排序-代码示例
- DML语句
- C#可以直接调用的Win32API
- [ML] Machine Learning in the Common Infrastructure ecosystem