- 搬题人：
- A, B, C：hehezhou
- 组题人：hehezhou
- 题解：hehezhou
因为忘记宣传了，pjudge 复活的第一场比赛竟然没什么人打……后面还会有比赛，希望大家帮忙宣传宣传 >_<
赌徒
题目来源：
- Petrozavodsk Summer 2021 Day 7: MIPT Contest, GP of Dolgoprudny, Problem G
- XXII Open Cup named after E.V. Pankratiev, Grand Prix of Dolgoprudny, Problem G
QOJ 链接：https://qoj.ac/contest/697/problem/1880
两面一定是 $1$ 或出现过的数字，因此可以离散化。
如果不考虑买硬币的代价，两面是独立的，先求出一面是 $a$ 时的收益 $S_a$，这可以简单通过前缀和得到。
接下来需要求出 $\max_{a,b}\{S_a+S_b-ab\}$，考虑固定 $a$，发现只有在凸包上的 $b$ 有用，反之亦然。因此只保留凸包上的点，继而可以双指针。
时间复杂度 $O(n)$。
猜猜看
题目来源：
- Petrozavodsk Summer 2021. Day 1. Kyoto U Contest, Problem J
QOJ 链接：https://qoj.ac/contest/691/problem/1813
不难发现两次询问 $1$ 的用途是确定询问 $2$ 无法区分的 $1,2$ 和 $n-1,n$。
当 $n=4$ 时，可以通过 $4$ 次询问来得到两个较小的数和两个较大的数。
当 $n$ 更大时，不妨考虑增量法，逐个点加入，维护出 $1\sim i$ 中的最小值及次小值的下标 $l_1,l_2$，最大值及次大值的下标 $r_1,r_2$，次小值 $L$ 和次大值 $R$。注意你暂时无法区分 $l_1,l_2$，$r_1,r_2$ 同理。
先询问 $x=Q_2(l_1,r_1,i+1)$，接下来有若干情况：
- $L\lt x\lt R$，说明 $a_{i+1}=x$。
- $L=x$，说明 $a_{i+1}\lt a_{l_1}=x$，将 $l_1$ 更新为 $i+1$ 并询问出新的 $L$，$R=x$ 同理。
- $x\lt L$，说明 $a_{i+1}\lt a_{l_2}=L$，将 $l_2$ 更新为 $i+1$，$L$ 更新为 $x$，$R\lt x$ 同理。
最后使用两次操作 $1$ 区分 $l_1,l_2$ 及 $r_1,r_2$ 即可。
第 $2$ 类询问次数 $2n-4$。
到底有没有九
题目来源：
- Petrozavodsk Summer 2021 Day 7: MIPT Contest, GP of Dolgoprudny, Problem B
- XXII Open Cup named after E.V. Pankratiev, Grand Prix of Dolgoprudny, Problem B
QOJ 链接：https://qoj.ac/contest/697/problem/1875
算法 1
如果尝试直接求出第 $n$ 个 $x$ 满足 $x\times (10^k-1)$ 不包含 $9$ 并没有比较好的转化，但是可以考虑求出第 $n$ 个 $x$ 满足 $x$ 的十进制表示不包含 $9$ 并且 $x$ 是 $10^k-1$ 的倍数，答案即为 $\frac{x}{10^k-1}$。
考虑逐位确定答案，答案的位数是 $O(k+\log n)$ 的，因此可以将问题转化为 $O(k+\log n)$ 次询问形如 $\overline{x_1x_2x_3\cdots x_k??\cdots ?}$ 的数有多少种方案将 $?$ 替换为 $0\sim 8$ 使得这个数是 $10^k-1$ 的倍数。
一个数是 $10^k-1$ 的倍数当且仅当从低往高位，每 $k$ 位划为一段，所有段的和是 $10^k-1$ 的倍数。
因为段数很少（设为 $l$），不妨先枚举这个和，即 $[i(10^k-1)]_{i=0}^{l}$。接下来按照在段中的位置，从低往高数位 dp 即可。
时间复杂度：$O(\text{poly}(\log n+k))$，视实现而定。
std 的复杂度为：$O(\log^4 n+k^2)$ 。
算法 2
一个暴力。
把 $x\times (10^k-1)$ 拆分为 $x\times 10^k$ 和 $x$ 相减。
不难发现，如果无脑从低到高 DP ，需要记录低位的 $k$ 个位置分别选了什么。
直接二分答案，然后暴力 DP ，复杂度 $O(10^k(k+\log n)^2)$ 。
算法 3
另一个暴力。
考虑 $k$ 较大怎么办。设 $y=x\times (10^k-1)$ ，那么 $y_i$ 只和 $x_i,x_{i-k}$ 以及是否有退位有关。（这里 $x_i,y_i$ 分别表示 $x,y$ 十进制下的第 $i$ 位。）
除了退位以外，不同的 $i\bmod k$ 是独立的！
毛估估一下，答案长度应该不会比 $k+\log n$ 大多少。所以可以把 $x$ 每 $k$ 位分一段，设分成了 $l$ 段。
那么可以先枚举 $2^l$ 种段间退位的情况，然后所有段一起从低到高 DP ，记录目前的退位情况即可。
复杂度大概是 $O(4^l(k+\log n)^2)$ 吧。
算法 4
把算法 2 和算法 3 拼起来即可。