【Bzoj1026】【Luogu2657】windy数

来源和评测点

SCOI2009 Day1
Bzoj1026
Luogu2657

题目

【题目大意】
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道,在A和B之间,包括A和B,总共有多少个windy数?
【输入格式】
包含两个整数,A B。
【输出格式】
一个整数
【限定条件】
1<=A<=B<=2000000000
【输入样例】
25 50
【输出样例】
20
【样例解释】

刷题记录

20min
1AC

分析

数位dp入门题
分类讨论即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
//*******************全局定义*******************
int c[11],ln;
int f[11][10];
//*******************实现*******************
int dp()
{
int ans=0;
for(int i=1;i<=ln-1;i++)//首位0
for(int j=1;j<=9;j++)//非首位
ans+=f[i][j];
for(int i=1;i<=c[ln]-1;i++) ans+=f[ln][i];//首位1
for(int i=ln-1;i>=1;i--)//首位2的次位
{
for(int j=0;j<=c[i]-1;j++)
{
if(myabs(c[i+1]-j)>=2) ans+=f[i][j];
}
if(myabs(c[i+1]-c[i])<2) break;//剪枝,后面都是0
if(i==1) ans++;//b
}
return ans;
}
int solve(int x)
{
ln=0;
while(x>0)
{
c[++ln]=x%10;
x/=10;
}
return dp();
}
//*******************主函数*******************
int main()
{
memset(f,0,sizeof(f));
int a,b;scanf("%d%d",&a,&b);
for(int i=0;i<=9;i++) f[1][i]=1;
for(int i=2;i<=10;i++)
for(int x=0;x<=9;x++)
for(int y=0;y<=9;y++)
if(myabs(x-y)>=2)
f[i][x]+=f[i-1][y];
printf("%d",solve(b)-solve(a-1));
}

UP 2018.8.28:
写了个记忆化搜索的版本
好写好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=30;
const int INF=0x3f3f3f3f;
int myabs(int x) {return x>0?x:-x;}
int mymin(int x,int y) {return x<y?x:y;}
int f[15][10];
bool v[15][10];
int num[15];
int calc(int ln,int lst,bool prezero,bool mask)
{
if(ln==0) return 1;
if(!mask and !prezero and v[ln][lst]) return f[ln][lst];
int tot=0,mx=mask?num[ln]:9;
for(int now=0;now<=mx;now++)
if(prezero or myabs(lst-now)>=2)
tot+=calc(ln-1,now,prezero and now==0,mask and now==mx);
if(!mask and !prezero) v[ln][lst]=1,f[ln][lst]=tot;
return tot;
}
int solve(int x)
{
int n=0;while(x>0) num[++n]=x%10,x/=10;
return calc(n,0,1,1);
}
void main()
{
int a,b;scanf("%d%d",&a,&b);
printf("%d",solve(b)-solve(a-1));
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4670.html
转载请注明出处,谢谢!