题解 P2657 【[SCOI2009]windy数】
Anguei
2018-10-31 14:36:50
~~这一看就是一个分段打表题~~
思路:每隔 $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 限制。