HDU 5787 K-wolf Number (数位DP)

时间:2022-09-01 13:23:15

K-wolf Number

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5787

Description

Alice thinks an integer x is a K-wolf number, if every K adjacent digits in decimal representation of x is pairwised different.

Given (L,R,K), please count how many K-wolf numbers in range of [L,R].

Input

The input contains multiple test cases. There are about 10 test cases.

Each test case contains three integers L, R and K.

1≤L≤R≤1e18

2≤K≤5

Output

For each test case output a line contains an integer.

Sample Input

1 1 2

20 100 5

Sample Output

1

72

Source

2016 Multi-University Training Contest 5

##题意:

找出区间[L,R]中有多少个数满足任意相邻的K位均不不相同.


##题解:

数位DP:分别对l-1.r求出从0开始一共有多少个数满足条件.
dp[i][j]:处理到还剩下i个数时左边相邻k个数是j(j代表一串数)的情况种数.
用map, LL> dp[maxn]来表示dp数组,vector存储左边相邻的k个数.
依次枚举每一位可能放置的数字并进行递归处理.

1. 在递归时要标记一下之前放置的那些数能否保证小于上限,如果可以当前位可以放置0-9任意数.
2. 注意处理前导零和非前导零的情况:这里用-1代表前导零,如果枚举到当前位为0时,要先看上一位是否为-1,如果是-1则当前位要更新为-1(也是前导零).
3. 记忆化:用map-dp记录下当前的计算结果. 注意:仅当当前数能确定比上限小时才能记录dp值.
(反例:比如样例的20和100,先处理100得到dp[2][-1,-1,-1]=91, 若记录下当前dp,在处理19时,则会直接返回91.)
4. 之前一直TLE是因为每次处理数据时都把dp初始化了一遍,而实际上对于所有数据dp都可以共用,只需要初始化一次即可.
5. 看到一份用五维dp数组记录的代码仅用了300ms,而上述用map-vector的记录方式用了2000ms.


##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define mid(a,b) ((a+b)>>1)
#define eps 1e-8
#define maxn 55000
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;

int k;

int num[20];

map<vector, LL> dp[20];

bool is_ok(const vector& cur) {

int state = 0;

for(int i=0; i<k; i++) {

if(cur[i] == -1) continue;

if(state & (1<<cur[i])) return false;

else state |= (1<<cur[i]);

}

return true;

}

LL dfs(int len, vector cur, bool is_small) {

if(len == 0) return 1LL;

if(is_small && dp[len].count(cur)) return dp[len][cur];

int limits = is_small? 9:num[len];
vector<int> next; next.clear();
int sz = cur.size();
for(int i=1; i<sz; i++) {
next.push_back(cur[i]);
} LL ret = 0;
for(int i=0; i<=limits; i++) {
if(i) next.push_back(i);
else {
if(next[k-2] == -1) next.push_back(-1);
else next.push_back(0);
}
if(is_ok(next)) {
ret += dfs(len-1, next, !(!is_small&&i==limits));
}
next.pop_back();
} if(is_small) dp[len][cur] = ret;
return ret;

}

LL solve(LL x) {

int cnt = 0;

vector cur; cur.clear();

while(x) {

num[++cnt] = x % 10;

x /= 10;

}

for(int i=0; i<k; i++)

cur.push_back(-1);

return dfs(cnt, cur, 0);

}

int main(int argc, char const *argv[])

{

//IN;

LL l,r;
for(int i=0; i<20; i++) dp[i].clear(); while(scanf("%I64d %I64d %d", &l,&r,&k) != EOF)
{
//for(int i=0; i<20; i++) dp[i].clear();
printf("%I64d\n", solve(r) - solve(l-1));
} return 0;

}

HDU 5787 K-wolf Number (数位DP)的更多相关文章

  1. 多校5 HDU5787 K-wolf Number 数位DP

    // 多校5 HDU5787 K-wolf Number 数位DP // dp[pos][a][b][c][d][f] 当前在pos,前四个数分别是a b c d // f 用作标记,当现在枚举的数小 ...

  2. HDU&period;4352&period;XHXJ&&num;39&semi;s LIS&lpar;数位DP 状压 LIS&rpar;

    题目链接 \(Description\) 求\([l,r]\)中有多少个数,满足把这个数的每一位从高位到低位写下来,其LIS长度为\(k\). \(Solution\) 数位DP. 至于怎么求LIS, ...

  3. HDU 5787 K-wolf Number 数位DP

    K-wolf Number Problem Description   Alice thinks an integer x is a K-wolf number, if every K adjacen ...

  4. hdu 5898 odd-even number 数位DP

    传送门:hdu 5898 odd-even number 思路:数位DP,套着数位DP的模板搞一发就可以了不过要注意前导0的处理,dp[pos][pre][status][ze] pos:当前处理的位 ...

  5. HDU 3709 Balanced Number &lpar;数位DP&rpar;

    Balanced Number Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) ...

  6. HDU 5179 beautiful number 数位dp

    题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc(中文): http://bestcoder.hdu.edu.cn/contes ...

  7. hdu 5898 odd-even number&lpar;数位dp)

    Problem Description For a number,if the length of continuous odd digits is even and the length of co ...

  8. HDU 5898 odd-even number &lpar;数位DP&rpar; -2016 ICPC沈阳赛区网络赛

    题目链接 题意:一个数字,它每个数位上的奇数都形成偶数长度的段,偶数位都形成奇数长度的段他就是好的.问[L , R]的好数个数. 题解:裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的 ...

  9. 2017&quot&semi;百度之星&quot&semi;程序设计大赛 - 复赛1005&amp&semi;&amp&semi;HDU 6148 Valley Numer【数位dp】

    Valley Numer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  10. HDU 4352 - XHXJ&&num;39&semi;s LIS - &lbrack;数位DP&rsqb;&lbrack;LIS问题&rsqb;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4352 Time Limit: 2000/1000 MS (Java/Others) Memory Li ...

随机推荐

  1. PHP实现快速排序、插入排序、选择排序

    1.快速排序 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都 ...

  2. PostgreSQL9&period;2安装和配置指南

    本文只介绍PostgreSQL9.2在centos上的安装和配置过程 1.执行yum 命令安装PostgreSQL yum install postgresql-server 2.初始化Postgre ...

  3. Oracle 10046 trace文件分析

    生成10046 trace文件: SQL> create table t10046 as select * from dba_objects; Table created. SQL> se ...

  4. Tips--怎么使用谷歌搜索

    修改hosts即可: hosts在哪? windows下:C:\Windows\System32\drivers\etc 管理员身份打开,并将下载好的hosts文件内容,添加到原有的hosts文件末尾 ...

  5. SpringBoot&lpar;二&rpar;&lowbar;项目属性配置

    修改端口 在main/resources/application.properties修改端口 server.port=8088 此时启动访问localhost:8088/hello 就会看到 Hel ...

  6. 魅族便签,是否能成为国内便签应用的No&period;1?

    继前不久锤子科技推出便签 Android 新版后,近期魅族在PRO 6公布会上也公布了最新的魅族便签应用.这一次魅族把便签应用拓展到了整个Android体系,也就是说.其它不论什么的Android手机 ...

  7. 数学与猜想 数学中的归纳和类比 &lpar;G&period; 波利亚 著&rpar;

    第一章 归纳方法 (已看) $1. 经验和信念 $2. 启发性联想 $3. 支持性联想 $4. 归纳的态度 第二章 一般化,特殊化,类比 (已看) $1. 一般化,特殊化,类比和归纳 $2. 一般化 ...

  8. IntelliJ IDEA 快捷键积累

    Windows idea 平时常用快捷键 一.视图查看 Ctrl+F12 查看file,method结构图.类继承机构图(方法,参数,返回值)                Ctrl+shift+Al ...

  9. python-minidom模块【解析xml】

    1,xml的文档结构 1.1,XML文档包括XML头信息和XML信息体 1.1.1,XML文档头信息 <?xml version="1.0" encoding="u ...

  10. electron&lowbar;window 创建窗口

    /** * 窗口基类,封装通用的窗口操作 */ const { BrowserWindow } = require('electron'); /** * 基本窗口样式 * @type {{width: ...