BZOJ 1026: [SCOI2009]windy数

2021-07-17 18:19

阅读：1698

标签：max post 数字 ble php zoj lin efi div

二次联通门 : BZOJ 1026: [SCOI2009]windy数

/*
    BZOJ 1026: [SCOI2009]windy数

    水题开心
    数位dp
    f[i][j]表示一个i位的数字的第i位是j的数字有几个

    设 s (x)为[0,x)的答案
    怎么求s(x)?
    设x有t位，我们先找到所有t - 1的符合题意的数
    然后从高到低一位一位得确定为原数字x对应位上的数字
    在此基础上累计方案数就好了
    就能求出[0,x)的答案了
    然后s (M + 1) - s (N)即可
*/
#include #define rg register
#define Max 20
int f[Max][Max], d[Max];
inline int abs (int x) { return x 0 ? -x : x; }
int Calc (int x)
{
    int c = 0, res = 0; rg int i, j, k;
    for (; x; d[++ c] = x % 10, x /= 10);
    for (i = 1; i  i)
        for (j = 1; j 9; ++ j) res += f[i][j];
    for (i = c; i; -- i)
    {
        for (j = (i == c); j  j)
            if (i == c || abs (j - d[i + 1]) >= 2)
                res += f[i][j];
        if (i 1] - d[i]) 2) break;
    }
    return res;
}
int main (int argc, char *argv[])
{
    rg int i, j, k;
    for (i = 0; i 9; ++ i) f[1][i] = 1;
    for (i = 1; i 10; ++ i)
        for (j = 0; j 9; ++ j)
        {
            for (k = 0; k 2; ++ k) f[i + 1][k] += f[i][j];
            for (k = j + 2; k 9; ++ k) f[i + 1][k] += f[i][j];
        }
    int N, M;
    scanf ("%d%d", &N, &M);
    printf ("%d", Calc (M + 1) - Calc (N));

    return 0;
}

BZOJ 1026: [SCOI2009]windy数

标签：max post 数字 ble php zoj lin efi div

原文地址：https://www.cnblogs.com/ZlycerQan/p/8127816.html

上一篇：拖拽窗体的实现

下一篇：Spring-Cloud的版本是如何定义的

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

亲，登录后才可以留言！

BZOJ 1026: [SCOI2009]windy数

评论

热门文章

推荐文章

最新文章

置顶文章