懒得写那么多题解，于是就有了这个文章。
难度评级
D：很简单，也没怎么调。很可能不会出现在这个文章里。
C：会做，但是出了一些不是特别傻的 bug。
B：勉强会做 / 写代码是遇到了问题。
A：不会，看了题解很容易就弄懂了。
S：完全不会，反复看题解和代码才懂。
可能用加减号来更细化一些，+表示难，-表示简单。
Chapter 1 递推
E 练习1 划分数列
给定一个长度为 $n$ 的数列，要求划分最少的段数，使得每一段要么单调不降，要么单调不升。
难度：D+
有点贪心的感觉，可以发现如果能接上肯定比不接好，和每一段越长越好。
预处理 $up_i,down_i$ 表示以 $i$ 为结尾的最长不降/不升段的开始位置，然后答案 $f_i=\min(f_{up_i-1},f_{down_i-1})+1$。
G 练习2 无限序列
我们按以下方式产生序列：
- 开始时序列是：
1； - 每一次变化把序列中的
1变成10，0变成1。
经过无限次变化，我们得到序列 1011010110110101101...。
总共有 $Q$ 个询问（ $Q\leq5000$） ，要回答在区间 $[a,b]$ 间有多少个1（$1\leq a\leq b\leq2^{63}$）。
难度：D+
手玩发现第 $i$ 次变化后得到的序列是 $i-1$ 次变化后的序列 + $i-2$ 次变化后的序列，于是这就是个斐波那契。
对于每个询问，转换成前缀和，然后不停二分即可。要注意二分时要找到第一个不大于它的，所以用 std::lower_bound() 时要注意。
{% spoiler Code %}
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
using std::cout;
using std::endl;
const int maxn = 100 + 10, n = 100;
typedef unsigned long long ll;
inline ll read()
{
ll x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
x = x * 10 + ch - '0', ch = getchar();
return x;
}
void write(ll x)
{
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
ll f[maxn], ans[maxn];
ll solve(ll x)
{
if (x == 0)
return 0;
ll res = 0;
while (x)
{
int pos = std::lower_bound(f, f + 1 + n, x + 1) - f;
pos--;
if (pos < 0)
return res;
res += ans[pos];
x -= f[pos];
}
return res;
}
int main()
{
f[0] = ans[0] = 1, f[1] = 2, ans[1] = 1;
for (int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2], ans[i] = f[i - 1];
int q;
scanf("%d", &q);
while (q--)
{
ll x, y;
x = read(), y = read();
write(solve(y) - solve(x - 1));
puts("");
}
}
{% endspoiler %}
Chapter 2 二分
F 练习3 攻击法坛
难度：C
二分 $L$，然后用 DP 来 check，$f(i,j)=\max(nxt1_{f(i-1,j)+1},nxt2_{f(i,j-1)+1})$。其中 $f(i,j)$ 表示用 $i$ 个第一种法杖和 $j$ 个第二种法杖能覆盖的最远的法坛，$nxt1_i,nxt2_i$ 分别表示在第 $i$ 个祭坛处用第一种/第二种法杖能覆盖的最远的法坛。特别地，$nxt1_{n+1}=nxt2_{n+1}=n$。注意使用次数限制需要和 $n$ 取一个最小值。
Chapter 19 倍增
H 练习3 图上查询
一个 $n$ 个点 $n$ 条边的 有向图，对每个点求出从它出发经过 $k$ 条边，这些边的权值和以及这些边的权值最小值。
难度：D+
一开始没看到有向图，就纳闷了，这玩意基环树？？？然后越想越不对劲，感觉是有向图这个题就不对了啊。
看了题解发现是有向图。。。。。。。然后这个有向图每个点的出度都是 $1$，那么倍增一下就行。
然后写着写着又忘记这个有向图有环了，可以无限走下去，于是挂了好几遍。。。
确实要注意一下。
Chapter 22 数位DP
C 例题3 数字计数 [ZJOI2010]
给定两个正整数 $l$ 和 $r$，求在 $[l,r]$ 中的所有整数中，每个数码各出现了多少次。
难度：B+
第一道自己做的数位DP…
虽说是数位DP，但我似乎并不是正统数位DP，更像是一种推式子的递推。
做每道推式子的计数都很费劲啊。。。实际上这题并不难。
设 $f(i,1/0)$ 表示从低到高第 $i$ 位，是/否紧贴上界，当前数码出现总次数。$cnt(i,1/0)$ 表示由低到高 $i$ 位，是/否紧贴上界，总共有几个数。$p_i$ 表示从低到高第 $i$ 位数。
对于数码 $1\sim9$ 显然有 $cnt(i,0)=cnt(i+1,0)\times10+p_i$，$cnt(i,1)=cnt(i+1,1)$，$f(i,1)=f(i+1,1)+[p_i=x]$。其中 $x$ 为当前要算的数码。
考虑 $f(i,0)$，先给出来式子：$f(i,0)=f(i+1,0)\times10+cnt(i+1,0)+f(i+1,1)\times p_i+[p_i>x]$。
解释一下：上一位所有含当前数码的数在这一位可以随便填一个数，所以乘一个 $10$；之前所有数后面都可以填一个当前数码，所以要加上 $cnt(i+1,0)$；之前紧贴上界的数可以填一个小于 $p_i$ 的数，如果当前数码比 $p_i$ 小，那么在刚刚填的时候还会填进去一个当前数码，要算进去。
{% spoiler Code %}
在该开 long long 的地方记得开。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
const int maxn = 20;
typedef long long ll;
ll f[maxn][2], cnt[maxn][2];
int p[maxn], len;
ll dp(int x)
{
cnt[len + 1][1] = 1;
for (int i = len; i >= 1; i--)
{
cnt[i][0] = cnt[i + 1][0] * 10 + p[i];
cnt[i][1] = cnt[i + 1][1];
f[i][1] = f[i + 1][1] + (p[i] == x ? 1 : 0);
f[i][0] = f[i + 1][0] * 10 + cnt[i + 1][0] + f[i + 1][1] * p[i];
if (p[i] > x)
f[i][0]++;
}
ll tmp = 0;
if (x == 0)
for (int i = 1; i <= len; i++)
tmp = tmp * 10 + 1;
return f[1][0] + f[1][1] - tmp;
}
ll solve(ll x, int i) // 此处没开 long long，导致 WA 了一遍。。。
{
len = 0;
while (x)
p[++len] = x % 10, x /= 10;
memset(cnt, 0, sizeof(cnt)), memset(f, 0, sizeof(f));
return dp(i);
}
int main()
{
ll a, b;
cin >> a >> b;
for (int i = 0; i <= 9; i++)
cout << solve(b, i) - solve(a - 1, i) << " ";
cout << endl;
}
{% endspoiler %}