[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释!)

2024-05-12 00:08

本文主要是介绍[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释!),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://acm.tju.edu.cn/toj/showp2839.html(真的找不到链接了)

题目大意:

给你一个范围A~B,求出在整数A 到B之间,0到9这十个数字,分别出现了多少次?

1≤A,B≤10^18

样例输入  129 137

样例输出  1 10 2 9 1 1 1 1 0 1


题解:

数位DP

我的第一道数位DP。。尽管是基础水题但是搞了好久ORZ &&感谢关大学霸%%%!

范围A~B,那么就先算出在1~B中这十个数字分别出现了多少次。再算出在1~A-1中各出现了多少次,然后相减就好了。

[我都是 最高位从1开始...就是诶待会看下图]

以样例为例。先说一下什么叫上限边缘。

假设算的是1~137中各个数的出现次数。现在做到了第2位,如果前面枚举的是1,那么就处于上限边缘。枚举当前位,即第2位为3的话,仍处于上限边缘,而为0~2的话就不在上限边缘了。

然后就用图说明一下bit[]和ret[]存的是什么好了。其他的代码里有,很多很多注释!怕自己以后看不懂...


...bit[]就不画了= =,意思也差不多。bit[i]=10^i。因为还没限制,所以可以填的总数就是bit[后面有几位].

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;LL f[20][2][2];
//f[i][flag][zero]表示搞到第i位 flag-0/1 zero-0/1的时候某数的数目
//flag表示该位是不是在上限边缘 zero表示目前是否还是前导零
LL d[10],bit[20],ret[20];
char s[20];int len;
LL dfs(int x,int i,int flag,int zero)
{if (f[i][flag][zero]!=-1) return f[i][flag][zero];//记忆化↑ 不加超时if (i>len) return 0;LL ans=0;if (flag)//如果前面的部分处于上限边缘{int j=s[i]-'0';//该位的上限是多少for (int k=0;k<j;k++)//枚举该位填什么{ans+=dfs(x,i+1,0,zero&(k==0));//不是上限的边缘↑了  ↑就是看看还是不是前导0if (k==x && !(zero&(k==0))) ans+=bit[len-i];//如果k是要统计次数的那个数字 而且不是在前导零的时候//而且还不是在上限的边缘!//那么后面几位的数字有多少种填法x就出现了几次}ans+=dfs(x,i+1,1,zero&(j==0));//该位填上限就仍在上限边缘if (j==x && !(zero && (j==0))) ans+=ret[i]+1;//如果填的是要统计次数的那个数字 而且不是在前导零的时候//那么后面的数字最多有多少种填法x就出现了几次(受限的哦!}else//↓就没有限制啦随便填 该统计的时候跟上面同理统计{for (int k=0;k<=9;k++){ans+=dfs(x,i+1,0,zero&(k==0));if (k==x && !(zero && (k==0))) ans+=bit[len-i];}}f[i][flag][zero]=ans;//记忆化return ans;
}
void cl()//把A减1 其实这样最高位可能变成了0 
//但是我的最高位是从1开始往后存的 所以没办法..(懒得全部往前挪一下= =
{int t=len;while (t>1 && s[t]=='0'){s[t]='9';t--;}s[t]--;
}
int main()
{//freopen("dream.in","r",stdin);//freopen("dream.out","w",stdout);int i;memset(d,0,sizeof(d));scanf("%s ",s+1);bit[0]=1;for (i=1;i<=18;i++) bit[i]=bit[i-1]*10;len=strlen(s+1);cl();ret[len]=0;for (i=len-1;i>=1;i--) ret[i]=(s[i+1]-'0')*bit[len-i-1]+ret[i+1];for (i=0;i<=9;i++){memset(f,-1,sizeof(f));d[i]-=dfs(i,1,1,1);}scanf("%s",s+1);len=strlen(s+1);ret[len]=0;for (i=len-1;i>=1;i--) ret[i]=(s[i+1]-'0')*bit[len-i-1]+ret[i+1];for (i=0;i<=9;i++){memset(f,-1,sizeof(f));d[i]+=dfs(i,1,1,1);}for (i=0;i<9;i++)printf("%d ",d[i]);printf("%d\n",d[9]);return 0;
}

这篇关于[USACO2003 Dec]Cow Queueing数数的梦 (基础水数位DP带注释!)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/981045

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Python中的输入输出与注释教程

《Python中的输入输出与注释教程》:本文主要介绍Python中的输入输出与注释教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、print 输出功能1. 基础用法2. 多参数输出3. 格式化输出4. 换行控制二、input 输入功能1. 基础用法2. 类

Rust中的注释使用解读

《Rust中的注释使用解读》本文介绍了Rust中的行注释、块注释和文档注释的使用方法,通过示例展示了如何在实际代码中应用这些注释,以提高代码的可读性和可维护性... 目录Rust 中的注释使用指南1. 行注释示例:行注释2. 块注释示例:块注释3. 文档注释示例:文档注释4. 综合示例总结Rust 中的注释

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应