p_b_p_b' blog

Blog

Public Round #4 题解

2022-06-05 14:49:28 By p_b_p_b
  • 搬题人:
    • 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 拼起来即可。

Comments

No comments yet

Comments are turned off.