P2657 [SCOI2009]windy数

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

输入格式

包含两个整数，A B。

输出格式

一个整数

?

思路

首先很明显这是一个数位dp，我觉得数位dp在dp里面是很有很有套路性的，大部分都是预处理答案+统计并累加答案。

那么这道题询问一个区间[A,B]，如果用暴力的思维直接从A枚举到B想必是会超麻烦，所以我们要用前缀和。通过算法求出[0,K]的答案个数再进行加减即可获得[A,B]的答案个数。

我们首先预处理得到dp[i][j]，表示这个数的最高位 第i位 是j时windy数的个数（j此时是不是0我们不管）。转移方程dp[i][j] = sum{dp[i-1][k]} k在[0,9]之间且|k-j|>=2。

那么如何用dp数组求[0,K]的答案个数呢？我们先假设K是53575（是一个windy数）

我们考虑所有最高位是[1,5)的五位数[10000,49999]

然后再把答案加上所有位数小于五位的wendy数（这两步比较好理解）

最后统计[50000,K],因为最高位5已经定了所以我们从次高位依次往低位扫描,然后枚举小于这个位置上的数 且符合要求的数的个数。比如说我们到了3, 2、1、0都小于3且和前一位5的差值大于2，所以答案+=dp[4][2]+dp[4][1]+dp[4][0]，这个时候我们认为这一位就是3，然后看下一位5......以此类推

如果这个数是53475我们便不能认为第三位是4了（因为3和4差值小于2）所以后面的解都已经统计过了，可以跳出循环返回答案（想想这是为什么）

下面看代码吧注释挺多的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

#define ll long long
#define re register

int dp[20][15];//dp[i][j]记录最高位（第i位）是j时 windy数的个数
int temp[20];//用来拆分数位的临时数组
int a, b;//题目输入
int abs(int x) { return x > 0 ? x : -x; } //手写abs
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int fx(int x)//计算 [0,x) 之间的windy数个数 后面会解释为什么左闭右开
{
    int l = 0, ans = 0; //数字的位数 答案
    memset(temp, 0, sizeof(temp)); //初始化
    while (x)
    {
        temp[++l] = x % 10;
        x /= 10;
    }//拆数
    for (int i = 1; i < temp[l]; i++)
        ans += dp[l][i];
    //统计位数是l的且严格小于x的windy数个数
    for (int i = 1; i < l; i++)
        for (int j = 1; j <= 9; j++)
            ans += dp[i][j];
    //统计位数在[0,l)之间的windy数个数
    for (int i = l - 1; i >= 1; i--)
    {//对于除最高位的每一位，我们枚举他们小于temp[i]的所有情况，然后默认他们等于temp[i]，累加至答案
        for (int j = 0; j < temp[i]; j++)
        {
            if (abs(j - temp[i + 1]) >= 2) ans += dp[i][j];
        }//然后默认他们就是temp[i]，来判断后面的数位是否合法
        if (abs(temp[i] - temp[i + 1]) < 2) break;
        //若枚举的这一位和前一位差值小于2 这一位和前一位不能同时是原数 所以这种情况已经统计过了 于是退出
    }
    //若x恰好是一个windy数 因为上面j循环没有循环到temp[i] 所以dp[1][temp[1]]没有对答案有贡献
    //所以说fx()的区间是左闭右开的
    return ans;
}

int main()
{
    for (int i = 0; i <= 9; i++) dp[1][i] = 1;
    for (int i = 2; i <= 15; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                if (abs(j - k) >= 2)
                {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }//初始化
    a = read(), b = read();
    cout << fx(b + 1) - fx(a); //f[x]求得的区间是左闭右开的
    return 0;
}

19.07.31

题解 P2657 [SCOI2009]windy数

原文：https://www.cnblogs.com/YuanqiQHFZ/p/11624923.html