Personal Best !

晚上状态挺好，一下就恢复信心了。

D 一下子没有想清楚，吃了一发罚时，其它都还是可以的。

手指受伤前两题慢了些，对后面的题应该影响不大。

A

水题，直接 $21$ 减掉输入的仨。

B

照题目说的做就行了。

C

拿个桶先存一下 B 中出现的就可以了。

D

求 $a$ 个 a 和 $b$ 个 b 组成的字符串中字典序第 $k$ 小的。

思路倒是很快有，就是每次确定最前面的一个 b 的位置，然后一个个处理下去。但是细节上有点小问题，导致我调了一会儿。

这是错误代码：

    for(int i = 1; i <= B; i++) {
        int j;
        for(j = n-b+1; j > B-b+1 && C[n-j+1][b-1] < k; j--);
        flag[j] = 1;
        k -= C[n-j][b-1];
        b--;
    }

我们要确认的第一个的位置应该是第一个随便排会大于等于现在的 $k$ 的位置，而不是确定了这个后面随便排要小于 $k$ 的位置，然后再 $k$ 减掉后面随便排的方案，$b$ 个数去掉 $1$ 继续做就可以了。

这才是正确代码：

    for(int i = 1; i <= B; i++) {
        int j;
        for(j = n-b+1; j > B-b+1 && C[n-j+1][b] < k; j--); 
        flag[j] = 1;
        k -= C[n-j][b];
        b--;
    }

E

输入一棵树，$q$ 次询问，每次求 $u$ 的子树中深度为 $d$ 的点的个数。

直接做 $nq$ 显然会超时。

模拟下这个过程发现每次找了其它的深度是完全没有必要的，所以把每个深度分开来存储，然后考虑如何快速判断一个深度的点有几个在 $u$ 的子树里。

判断是否在子树里很容易想到 dfs 序，只要看 dfs 序是不是在 $[dfn_u, dfn_u + size_u - 1]$ 这个区间里就可以了。为了快速做到这一点，可以将每一个深度的点按 dfs 序排序，然后再 std::lower_bound 一下起止点就可以了。

代码。

#include <cstdio>
#include <vector>
#include <algorithm>
const int N = 200005;
int n, x, y, m, dfn[N], size[N], tot;
std::vector<int> g[N], a[N];
void dfs(int u, int fa, int d) {
    size[u] = 1;
    dfn[u] = ++tot;
    a[d].push_back(dfn[u]);
    for(int i = 0; i < (signed)g[u].size(); i++) {
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v, u, d+1);
        size[u] += size[v];
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        scanf("%d", &x);
        g[x].push_back(i), g[i].push_back(x);
    }
    dfs(1, 0, 0);
    for(int i = 0; i < n; i++)
        if(a[i].size()) std::sort(a[i].begin(), a[i].end());
    scanf("%d", &m);
    while(m--) {
        scanf("%d%d", &x, &y);
        int l = dfn[x], r = dfn[x] + size[x] - 1;
        int L = std::lower_bound(a[y].begin(), a[y].end(), l) - a[y].begin(),
            R = std::upper_bound(a[y].begin(), a[y].end(), r) - a[y].begin();
        printf("%d\n", std::max(R-L, 0));        
    }
    return 0;
}

难得在一个小时多一点就 A 了 E 题。

F

计算几何题，而且很难，没思路，总共才 $25$ 个人过。

最后

APIO 报名时的豪迈壮志最终一天天的化解， $50$ 天一过仍未有任何进步。每天浑浑噩噩的都过去了。

林语堂说：

一个人心地干净，思路清晰，没有多余情绪和妄想的人，是会带给人安全感的，因为他不伤人，也不自伤，不制造麻烦，也不麻烦别人。某种程度上来说，这是一种持戒。

翘翘所谓的可爱，只是在原来可爱优秀的同学们中受感染的罢了。只有真正的独立的做到和坚持“心地干净，思路清晰，没有多余情绪和妄想”，才是真正可爱的翘翘。

任何时候改变都来的及，前方的路还长。加油。