• 搬题人：
  • 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)$，接下来有若干情况：

1. $L\lt x\lt R$，说明 $a_{i+1}=x$。
2. $L=x$，说明 $a_{i+1}\lt a_{l_1}=x$，将 $l_1$ 更新为 $i+1$ 并询问出新的 $L$，$R=x$ 同理。
3. $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 拼起来即可。