题解 P2657 【[SCOI2009]windy数】

Anguei

2018-10-31 14:36:50

Solution

~~这一看就是一个分段打表题~~ 思路:每隔 $1000000$ 分一段,总共 $2000$ 段。预先打表计算出每一段当中的 windy 数个数,根据输入确定 $A,B$ 在哪一段当中。如果在同一段,那就直接暴力。否则先把中间那些段求和,再对两头的小块暴力。 有点类似分块:维护大的,暴力小的。 现有题解打表是求出 $1$ ~ $n$ 的 windy 数个数,最后统计答案需要搞一搞前缀和。如果打表的时候计算每一段的 windy 数个数,最后直接计算就可以了,感觉方便一些。 ### 判断是不是一个 windy 数 ```cpp 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; } ``` ### 生成表(大概两三分钟跑完) ```cpp 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(' '); } } ``` ### 主程序 ```cpp 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); } ``` ### 最后把表贴上 ```cpp 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 限制。