[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

相关文章

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步搞定一个应

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b