天津哪家公司做企业网站,做爰网站贴吧,服务器安全卫士,柏枫谈做网站都需要学什么Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道#xff0c;在A和B之间#xff0c;包括A和B#xff0c;总共有多少个windy数#xff1f; Input 包含两个整数#xff0c;A B。 Output 一个整数 Sample Input… 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 Solution 设$f[i][j]$表示i位数且最高位为j的满足题意的数有多少个: $f[i][j] \sum\limits_{|k - j| \geq {2}}^{9}f[i - 1][k]$ 查询时按照类前缀和的原理进行。 1 #include bits/stdc.h2 using namespace std;3 int num[11], f[11][10];4 5 int solve(int x)6 {7 int len, ans 0;8 for(len 0; x; x / 10)9 num[len] x % 10;
10 for(int i 0; i len - 1; i)
11 for(int j 1; j 10; j)
12 ans f[i][j];
13 for(int i 1; i num[len - 1]; i)
14 ans f[len - 1][i];
15 for(int i len - 2; i -1; i--)
16 {
17 for(int j 0; j num[i]; j)
18 if(abs(j - num[i 1]) 2) ans f[i][j];
19 if(abs(num[i] - num[i 1]) 2) break;
20 }
21 return ans;
22 }
23
24 int main()
25 {
26 int a, b;
27 scanf(%d%d, a, b);
28 for(int i 0; i 10; i)
29 f[0][i] 1;
30 for(int i 1; i 11; i)
31 for(int j 0; j 10; j)
32 for(int k 0; k 10; k)
33 if(abs(j - k) 2) f[i][j] f[i - 1][k];
34 cout solve(b 1) - solve(a) endl;
35 return 0;
36 } View Code 转载于:https://www.cnblogs.com/CtrlCV/p/5430289.html
