题解 P2657 【[SCOI2009]windy数】

2018-10-31 14:36:50


这一看就是一个分段打表题

思路:每隔 $1000000$ 分一段,总共 $2000$ 段。预先打表计算出每一段当中的 windy 数个数,根据输入确定 $A,B$ 在哪一段当中。如果在同一段,那就直接暴力。否则先把中间那些段求和,再对两头的小块暴力。

有点类似分块:维护大的,暴力小的。

现有题解打表是求出 $1$ ~ $n$ 的 windy 数个数,最后统计答案需要搞一搞前缀和。如果打表的时候计算每一段的 windy 数个数,最后直接计算就可以了,感觉方便一些。

判断是不是一个 windy 数

bool calc(int x) {
    int last = x % 10; x /= 10;
    while (x) {
        int now = x % 10; x /= 10;
        if (abs(last - now) < 2) return false;
        last = now;
    }
    return true;
}

生成表(大概两三分钟跑完)

void makeTable() {
    for (int i = 1; i <= 2000000000; i += 1000000) {
        int l = i, r = std::min(2000000000ll, i + 1000000 - 1), ans = 0;
        rep(j, l, r) if (calc(j)) ++ans;
        print(ans), pc(','), pc(' ');
    }
}

主程序

void solution() {
    int a = read(), b = read(), ans = 0;
    int blockA = a / 1000000 + 1, blockB = b / 1000000 + 1;
    // 同一块的直接暴力搞,否则用表。
    if (blockA == blockB) { rep(i, a, b) ans += calc(i); println(ans); return; }
    rep(i, blockA + 1, blockB - 1) ans += table[i];
    rep(i, a, a / 1000000 * 1000000 + 1000000) ans += calc(i);
    rep(i, b - b % 1000000, b) ans += calc(i);
    println(ans);
}

最后把表贴上

const int table[] = { -1, 202174, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      155315, 136131, 138503, 138214, 138252, 138252, 138214, 138503, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 138503, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      0, 0, 0, 138214, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 0, 0, 0, 138252, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 0, 0, 0, 138252, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 0, 0, 0, 138214, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 0, 0, 0, 138503, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 0, 0, 0, 136131, 155315, 
                      155315, 136131, 138503, 138214, 138252, 138252, 0, 0, 0, 155315, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

最后源程序大小 17 KB,没有超过 NOI 系列赛事的 100 KB 限制。