bzoj 1026——windy 数

拼搏现实的明天。 2022-08-13 16:41 159阅读 0赞

思想很简单，但是由于在这道题上犯二，此题让我改到吐血，代码能力还是很差。

题意：

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

只需要预处理出第I位最高位为j的windy数是多少，然后去计算就行了，但是注意迁到不能为零。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    typedef long long LL;
    const int maxn=0x3f3f3f3f;
    
    int dp[15][12],num[15];
    
    void anticipation(){
    	memset(dp,0,sizeof(dp));
    	for(int i=0;i<10;i++)
    		dp[1][i]=1;
    	for(int i=2;i<=10;i++)
    		for(int j=0;j<10;j++)
    			for(int k=0;k<10;k++)
    				if(abs(j-k)>1)
    					dp[i][j]+=dp[i-1][k];
    }
    int solve(int x){
    	int len=1,ans=0;
    	while(x){
    		num[len++]=x%10;
    		x/=10;
    	}
    	--len;
    	for(int i=len-1;i>=1;i--)
    		for(int j=1;j<10;j++)
    		   ans+=dp[i][j];
    
    	for(int i=num[len]-1;i>=1;i--)
    		ans+=dp[len][i];
    
    	for(int i=len-1;i>0;i--){
    		for(int j=num[i]-1;j>=0;j--)
    			if(abs(num[i+1]-j)>1)
    				ans+=dp[i][j];
    		if(abs(num[i+1]-num[i])<2)
    			break;
    	}
    	return ans;
    }
    
    int main(){
        int x,y;
    	anticipation();
    	while(scanf("%d%d",&x,&y)==2){
    	printf("%d\n",solve(y+1)-solve(x));
    	}
    return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关 1083 Windy数（数位dp）

1. 问题描述： Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。Windy 想知道，在 A 和 B 之间，包

不念不忘少年蓝@/ 2022年09月14日 08:43/ 0 赞/ 141 阅读

相关 bzoj 1026——windy 数

思想很简单，但是由于在这道题上犯二，此题让我改到吐血，代码能力还是很差。题意： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为

拼搏现实的明天。/ 2022年08月13日 16:41/ 0 赞/ 160 阅读

相关 uestc 250 windy数【数位dp】

题目：[uestc 250 windy数][uestc 250 windy] 题意： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的

迈不过友情╰/ 2022年08月13日 13:37/ 0 赞/ 161 阅读

相关 BZOJ 3530 数数【AC自动机+数位dp】

[\[Sdoi2014\]数数][Sdoi2014] 简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法

骑猪看日落/ 2022年08月09日 01:53/ 0 赞/ 168 阅读

相关杭电1026

Ignatius and the Princess I Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 6553

快来打我*/ 2022年06月04日 05:53/ 0 赞/ 288 阅读

相关 PAT乙级1026

1026 程序运行时间（15 分）要获得一个 C 语言程序的运行时间，常用的方法是调用头文件 time.h，其中提供了 clock() 函数，可以捕捉从程序开始运行到 c

旧城等待，/ 2022年05月12日 09:16/ 0 赞/ 170 阅读

相关 BZOJ1012 最大数maxnumber

单调栈的妙处！！刚看到这题差点写个splay。。但是后来看到询问范围的只是后L个数，因为当有一个数新进来且大于之前的数时，那之前的数全都没有用了，满足这种性质的序列可用

桃扇骨/ 2022年01月07日 05:11/ 0 赞/ 145 阅读

相关 bzoj2724 - 蒲公英 (分块+区间众数)

题面： Description ![T2des_286_29.gif][] Input ![T2input_286_29.gif][] 修正一下 l

客官°小女子只卖身不卖艺/ 2021年12月14日 12:07/ 0 赞/ 259 阅读

相关 [SCOI2009]windy数

题目描述 windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个

梦里梦外;/ 2021年11月04日 22:04/ 0 赞/ 232 阅读

相关 luoguP2657 [SCOI2009]windy数

和诸位巨佬不同，蒟蒻如我，只能想到怎么统计不满足windy数条件的数就是个爆搜定义c\[i\]\[j\]\[k\]表示第i位且前一位为j，k表示是否满足条件 ![Co

旧城等待，/ 2021年11月02日 01:02/ 0 赞/ 250 阅读