洛谷 - P2657 - windy数 - 数位dp
2024-10-20 00:25:02
https://www.luogu.org/problemnew/show/P2657
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
这道题是个显然到不能再显然的数位dp了。
来个最神奇的dp[i][j]表示i位数,开头为j的windy数的个数吧。
那么dp[i][j]的求法是很显然的,写个sum数组求和更为方便。
那么怎么统计windy数呢?
约定由布丁酱写的数位dp,求闭区间[l,r]时,使用count(r)-count(l-1),也就是count(x)表示不小于的[0,x]中windy数的个数。
怎么求count呢,最简单的思路就是分类讨论。
对最高位分三类:
最高位为0,遍历所有的dp[i][1~9]再加上0本身。
最高位为非0且比x最高位小,后面满足条件的可以随意取。
最高位相等,交给下一位去做。
对非最高位分两类:
该位在受前面位的限制下任取,后面满足条件的任取。
该位相等,交给下一位去做。(小心该位相等时非法,找了很久!)
最后补上x本身的判断。
最后要小心爆int……
意思是说,在数位dp的时候,每一步分类要不重不漏,每一步要判断合法。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[][]; ll sum(int i,int j1,int j2){
/*if(i==0)
return 1;*/
if(j1<)
j1=;
if(j2>)
j2=;
ll res=;
for(int j=j1;j<=j2;j++){
res+=dp[i][j];
}
return res;
} void init(){
for(int j=;j<=;j++)
dp[][j]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
dp[i][j]=sum(i-,,j-)+sum(i-,j+,);
}
} /*for(int j=1;j<=2;j++){
dp[9][j]=sum(8,0,j-2)+sum(8,j+2,9);
}*/ /*for(int i=1;i<=9;i++){
for(int j=0;j<=9;j++){
printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
}
printf("\n");
}*/
} ll A,B;
int digit[]; ll count(ll x){
//cout<<"x="<<x<<endl;
if(x==)
return ;
//否则岂不是0位数?
ll k=,cx=x;
digit[k++]=;
//占位用的
while(cx){
digit[k++]=cx%;
cx/=;
}
k--;
digit[k+]=;
//也是占位 ll res=;
for(int i=k;i>=;i--){
//printf("res=%d\n",res);
if(i==k){
//最高位取0
for(int ii=i-;ii>=;ii--)
res+=sum(ii,,);
res+=;//0
//其实不用特判啊
for(int j=;j<digit[i];j++){
//最高位比digit小且不为0
if(i->=){
res+=sum(i-,,j-)+sum(i-,j+,);
}
else{
res+=;
}
}
//最高位就取相等,问题留给下一次循环
}
else{
//前面的位都相等,非最高位的情况,双重受限
for(int j=;j<digit[i];j++){
if(abs(digit[i+]-j)<=)
;//被前一位限制取值
else if(i->=){
res+=sum(i-,,j-)+sum(i-,j+,);
}
else{
res+=;
}
}
}
} for(int i=;i<=k;i++){
if(abs(digit[i]-digit[i-])<=){
//printf("res1=%d\n",res);
return res;
}
}
//printf("res2=%d\n",res+1);
return res+;
} int main(){
init();
while(~scanf("%lld%lld",&A,&B)){
printf("%lld\n",count(B)-count(A-));
}
}
后来学会了另一种写法。搜索写法。这种写法里要用到lead来指定new_state1的状态。
#include<bits/stdc++.h>
using namespace std;
#define ll long long int a[];
ll dp[][/*前一位的取值,只有0~9*/];//不同题目状态不同
ll dfs(int pos,int state1/*前一位的取值,只有0~9,-1表示不受限制*/,bool lead/*这一位的前面是否为零*/,bool limit/*这一位是否取值被限制(也就是上一位没有解除限制)*/)
//不是每个题都要处理前导零
{
//递归边界,最低位是0,那么pos==-1说明这个数枚举完了
if(pos==-)
return ;/*这里返回1,表示枚举的这个数是合法的,那么这里就需要在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state1]!=-)
return dp[pos][state1];
/*常规写法都是在没有限制的条件记忆化,这里与下面记录状态对应*/
int up=limit?a[pos]:;//根据limit判断枚举的上界up
ll ans=;
//开始计数
for(int i=; i<=up; i++) { //枚举,然后把不同情况的个数加到ans就可以了
int new_state1=i;
if(lead==true&&i==){
//这一位继续是前导0,new_state1应为-1
new_state1=-;
}
if(state1>=&&abs(new_state1-state1)<)
continue;
/*
计数的时候用continue跳过不合法的状态,不再搜索
*/ //合法的状态向下搜索
ans+=dfs(pos-,new_state1,lead && i==,limit && i==a[pos]);//最后两个变量传参都是这样写的
}
//计算完,记录状态
if(!limit && !lead)
dp[pos][state1]=ans;
/*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
return ans;
} ll solve(ll x) {
//可能需要特殊处理0或者-1
if(x<=)
return ; int pos=;
while(x) { //把数位分解
a[pos++]=x%;//编号为[0,pos),注意数位边界
x/=;
} return dfs(pos-/*从最高位开始枚举*/,-/*表示这一位前面并没有对其限制的高位*/,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
} int main() {
memset(dp,-,sizeof(dp));
//一定要初始化为-1 ll le,ri;
while(~scanf("%lld%lld",&le,&ri)) {
printf("%lld\n",solve(ri)-solve(le-));
}
}
最新文章
- 在windows下面配置redis集群遇到的一些坑
- 在Javascript中监听flash事件(转)
- JSON value
- CSS Counters 计数属性
- printf函数重定向
- C++访问权限
- 夏梦竹谈Hive vs. HBase的区别
- Openlayers 3 热力图
- 关于IP网段间互访的问题—路由是根本(转)
- Java并发编程:线程的基本状态
- MacBook 经常使用快捷键
- Coding语言强弱类型且动静态类型简单解析。附图解
- JavaSE assert断言的学习
- 百度分享不支持Https的解决方案--本地化
- malloc()參数为0的情况
- 解决linux系统CentOS下调整home和根分区大小
- 用java打暴雪星际争霸(2)——执行測试机器人
- CSV 中添加逗号
- NOIP 算法模板
- git 提交代码出现git Permission to Xx denied to Xx 错误