1026: [SCOI2009]windy数(数位dp)
2024-08-30 22:15:59
1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 9016 Solved: 4085
[Submit][Status][Discuss]
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,
在A和B之间,包括A和B,总共有多少个windy数?
Input
包含两个整数,A B。
Output
一个整数
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
9
【输出样例二】
20
HINT
【数据规模和约定】
100%的数据,满足 1 <= A <= B <= 2000000000 。
分析
数位dp,注意特判第一位,注意只有在没有限制和第一位存在这两个条件同时满足时,使用数位dp。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream> using namespace std; int a[],p;
int dp[][]; // 当前第i位,上一位是j int dfs(int pos,int pre,bool fir,bool limit) {
if (pos==) return ;
if (!limit && fir && dp[pos][pre]!=-) return dp[pos][pre];
int u = limit ? a[pos] : ;
int cnt = ;
for (int i=; i<=u; ++i) {
if (fir && (fir && abs(pre-i) < )) continue;
cnt += dfs(pos-,i,(fir||(!fir&&i!=)),limit&&i==a[pos]);
}
if (!limit && fir) dp[pos][pre] = cnt;
return cnt;
}
int Calc(int x) {
if (x==) return ;
if (x==) return ;
memset(dp,-,sizeof(dp));
p = ;
while (x) {
a[++p] = x % ;x /= ;
}
return dfs(p,-,false,true);
}
int main () {
int L,R;
while (cin >> L >> R)
cout << Calc(R) - Calc(L-) << "\n";
return ;
}
最新文章
- 创建ejs模板的express工程
- Jquery easy ui datagrid動態加載列問題
- SQL Server 自定义聚合函数
- Mysql Innodb 间隙锁浅析
- 使用HyperV虚拟机装系统
- php-jquery-json-3
- URAL 1139 City Blocks(数论)
- 前端开发与Seo基础
- Android -- Home按键
- ARC __bridge modifiers demystified
- Qt经典出错信息之”Basic XLib functionality test failed!”
- JVM运行时内存结构
- java 操作POI参考文章
- Mybatis-Spring SqlSessionTemplate 源码解析
- MyBatis基础用法(一)
- android应用开发基础知道
- linux中probe函数传递参数的寻找(下)
- 使用Entity Framework Core访问数据库(DB2篇)
- ES7
- [物理学与PDEs]第4章第3节 一维反应流体力学方程组 3.3 一维反应流体力学方程组的数学结构
热门文章
- 给类型为text的input设置value值却无法修改
- mockjs模拟数据请求
- 使用CMake生成VS2010项目查看OpenCV源代码
- Hybris ECP里Customer对应的数据库表
- 避免使用 JS 特性 with(obj){}
- 【BZOJ1854】[SCOI2010] 游戏(匈牙利算法的应用)
- 统计学基于SPSS贾俊平 授课笔记 发布作业 spss19cn 软件下载地址及破解包spss19_10039 下载地址
- 第29题:LeetCode54:Spiral Matrix螺旋矩阵
- Python基础2-Python中文乱码(转)
- django+xadmin在线教育平台(四)