1026: [SCOI2009]windy数
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 9240 Solved: 4213
[Submit][Status][Discuss]
Description
windy界说了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包孕A和B，总共有几多个windy数？
Input
包罗两个整数，，A B。
Output
一个整数
Sample Input
【输入样例一】
1 10
【输入样例二】
25 50
Sample Output
【输出样例一】
9
【输出样例二】
20
HINT
【数据规模和约定】
100%的数据，满足 1 <= A <= B <= 2000000000 。
Source
题解
不难想思路。
真TMD难写啊。
具体看代码。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
inline long long max(long long a, long long b){return a > b ? a : b;}
inline long long min(long long a, long long b){return a < b ? a : b;}
inline long long abs(long long x){return x < 0 ? -x : x;}
inline void swap(long long &x, long long &y){long long tmp = x;x = y;y = tmp;}
inline void read(long long &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch < '0' || ch > '9') c = ch, ch = getchar();
while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
if(c == '-') x = -x;
}
const long long INF = 0x3f3f3f3f;
long long dp[110][10], num[110];
//dp[i][j]:<= i位数，最高位为j
//计算1...x - 1的windy数个数
long long solve(long long x)
{
if(x == 0) return 1;
long long M = 0, tmp = x;
while(tmp)
{
num[++ M] = tmp % 10;
tmp /= 10;
}
long long pre = num[M], re = 0;
for(int i = 1;i < num[M];++ i)
re += dp[M][i];
for(int i = 1;i < M;++ i)
for(int j = 1;j <= 9;++ j)
re += dp[i][j];
for(long long i = M - 1;i >= 1;-- i)
{
for(long long j = 0;j < num[i];++ j)
if(abs(num[i + 1] - j) >= 2)
re += dp[i][j];
if(abs(num[i + 1] - num[i]) < 2) break;
}
return re;
}
int main()
{
for(long long i = 0;i <= 9;++ i) dp[1][i] = 1;
for(long long i = 2;i <= 11; ++ i)
for(long long j = 0;j <= 9;++ j)
for(long long k = 0;k <= 9;++ k)
if(abs(j - k) >= 2)
dp[i][j] += dp[i - 1][k];
long long a,b;
read(a), read(b);
if(a > b) swap(a, b);
printf("%lld\n", solve(b + 1) - solve(a));
return 0;
}
