2026-10-27(#18)：A city burned down to ashes

Mazare / Philip Strand —— Battlecry

[Ynoi2012] NOIP2015 充满了希望

为什么有人把单点求值看成了区间求和想了一晚上不会做呢。

46 [IOI 2022] 囚徒挑战

想了一会儿意识到：$500$ 个囚犯是假的。

按照进制拆位，一开始二进制，分成每位用两个代表数当前位是 $0/1$ 以及看的是 A 还是 B，然后发现后者没用，轮流看就行，三进制的话这个东西能做到 $24$。

这里有个插曲：我在睡梦中想到一个囚犯有较大的概率去抄上一个囚犯写的数字，觉得很有用，而且这样 $500$ 个囚犯就有用了！虽然第二天醒来发现没有用，但是很有意思！接下来的内容是第二天想的。

最后一次查询是没有用的，因为两个数不相等，一旦查出最小最大就直接结束。

根据此可以转化到，有一棵线段树，每个节点可以使用 $b$ 的代价将其分为 $b+2$ 部分，第一个部分和最后一个部分大小都是 $1$。因此：

1
2
3
4
5
6
7

for (int i = 3; i <= n; ++i) {
    f[i] = 1e9;
    for (int j = 1; j <= i - 2; ++j) {
        f[i] = min(f[i], f[(i - 2 + j - 1) / j] + j);
    }
    cout << i << ' ' << f[i] << '\n';
}

这里甚至有 $f_{5588}=20$，于是做完了。将转移打印出来，然后根据此建表即可。

但仔细一想发现多少有点难写。