[bzoj1026] [SCOI2009]windy数

2021-06-15 20:06

阅读：358

标签：上界 ons space span fine print -- names max

Description

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

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

25 50

Sample Output

Solution

数位\(dp\)入门题。

\(f[i][j]\)表示\(i\)位，最高为是\(j\)的方案数。

然后贴着上界算答案就好了。

#include
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

#define write(x) printf("%d\n",x)

const int maxn = 2e5+10;

int f[30][12],r[30];

int calc(int n) {
    int d=0,x=n,ans=0;
    while(x) r[++d]=x%10,x/=10;
    for(int i=1;i=2) ans+=f[i][j];
        if(abs(r[i+1]-r[i])=2) f[i][j]+=f[i-1][k];
    int a,b;read(a),read(b),write(calc(b)-calc(a-1));
    return 0;
}

[bzoj1026] [SCOI2009]windy数

标签：上界 ons space span fine print -- names max

原文地址：https://www.cnblogs.com/hbyer/p/10357978.html

上一篇：WinForm POST上传与后台接收

下一篇：多线程模拟生产者消费者示例之BlockQuue

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj1026] [SCOI2009]windy数
文章链接：http://soscw.com/index.php/essay/94275.html

亲，登录后才可以留言！

[bzoj1026] [SCOI2009]windy数

Description

Input

Output

Sample Input

Sample Output

Solution

评论

热门文章

推荐文章

最新文章

置顶文章