p_b_p_b的博客

博客

Tags
None

Public NOIP Round #5 公告

2023-02-21 10:16:32 By p_b_p_b

Public NOIP Round #5 将在 2023 年 2 月 25 日 8:30 举行!

本次比赛只有提高组,进行 4.5 小时,有 4 道题,OI 赛制。题目难度约为 noip ,所有题目都有部分分。

本次比赛的组题人为 Qingyu ,搬题人为 p_b_p_b, ShanLunjiaJian, alpha1022, feecle6418

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public NOIP Round #2 公告

2022-09-30 10:59:52 By p_b_p_b

Public NOIP Round #2 将在 2022 年 10 月 4 日 8:30 举行!

比赛分为普及组和提高组,普及组进行 3.5 小时,提高组进行 4.5 小时。普及和提高分别有 4 道题,OI 赛制,其中普及组和提高组有两题相同。

与上一次比赛不同的是,本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛,而 MarsOJ 则可以提供仿真 csp/noip 考场环境的云电脑,具体可以加入用户群(915426363)。

选手可以根据自己的训练需要来自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

本次比赛的题目难度约为 CSP J / noip ,所有题目都有部分分。

本次模拟赛的组题人为 p_b_p_b ,搬题人为 Wu_Ren, hehezhou, Y25t, skip2004, p_b_p_b ,验题人待定。

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public Round #7 题解

2022-07-31 19:46:16 By p_b_p_b

大凯的疑惑

题目来源:

  • Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest, Problem I

QOJ 链接:https://qoj.ac/contest/448/problem/1462

正解不对拍,爆零两行泪。

\begin{aligned} (a+d)^k-a^k=\sum_{i=1}^k {k\choose i}d^ia^{k-i} \end{aligned} f_i={k\choose i}d^i ,列出前后几项:f_1=kd, f_2=k(k-1)d^2/2,\cdots,f_k=d^k

不难发现答案的质因子一定都是 d 的质因子,对 d 的每个质因子 p 分别考虑。设 C(x)=\max\{i\mid p^i|x\} ,即 x 里面 p 的次数。

引理:当 i\le p^{C(k)} 时, C({k\choose i})=C(k)-C(i)

证明:C(k-t)=C(t), 1\le t<p^{C(k)}

因此就有 C(f_i)=iC(d)+C(k)-C(i), 1\le i\le p^{C(k)} 。并且由于 C(d)\ge 1 ,所以可以感性理解得到 C(f_i) 大致是递增的,最小值是 C(f_1) 。并且不难证明,如果 C(f_1) 是唯一的最小值,那么答案就是 p^{C(f_1)}

如果这个感性理解是正确的,那么答案就是 kdd 的所有质因子,即 \gcd(d^{\infty},kd)

事实上这个感性理解的并没有太大问题,只是在 i 特别小的时候需要修一下。当 p=2,C(d)=1,2|k 时,C(f_2)=C(f_1)=C(kd) ,所以答案要多乘一个 2

道路重建

题目来源:

  • 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem E
  • Moscow Pre-Finals Workshops 2022 Day 4, Problem E

QOJ 链接:https://qoj.ac/contest/912/problem/3798

显然可以先把城市内的最小生成树求出来,只有这上面的边是有用的。进一步,按照边权从小到大的顺序合并连通块时,如果至少一边没有枢纽车站,那么这条边一定会被计入答案,也不需要考虑了。

进行这些预处理之后可以认为 m=n-1 且所有火车站都是枢纽车站。

人脑模拟 kruskal 的过程:

  • 在考虑到第一条高铁线路之前,每个城市都在按照相同的顺序合并,只是速度有快有慢。
  • a 从小到大考虑每个城市。
    • 不妨假设 \arg \min a_i=1 ,且 b_1<b_2
    • 显然城市 1 连的边是城市 2 连的边的超集。因此城市 2 目前的每个连通块都会向城市 1 连恰好一条高铁线路。
    • 连接之后,我们发现两个火车站 i,j 连通当且仅当对应编号在城市 1 中连通,而与这两个火车站实际在城市 1 还是城市 2 无关!并且城市 2 里面也不会连接新的动车线路了。
    • 因此接下来可以令 a_1:=a_2 ,然后忽略城市 2 继续做。

复杂度 O(n\log n)

杜杜和DUDU

题目来源:

  • Petrozavodsk Winter 2022. Day 6. 2022 ICPC Training Camp powered by Huawei — Day 1, Problem F

QOJ 链接:https://qoj.ac/contest/824/problem/2610

考虑按 x 从小到大扫描线,维护哪些 (x,y) 可达。

当我们扫完 x\leq K 的时候,扫完的点有 (x_1,y_1),\cdots,(x_q,y_q) .

定义 g_y=\max(x_i|y_i\leq y) ,如果 (x,y) 可达但 x<g_y 那么 (x,y) 没必要保留,因为 (g_y,y) 不可达意味着 (x,y) 不能一次到 (g_y,y) ,注意按照定义一定存在 (g_y,z),z\leq y 的点,所以 (x,y)(g_y,y) 是有转移的,进一步这意味着 (x,y) 不能一次转移到一个横坐标超过 K 的点,因为这样的代价一定不少于 (x,y)(g_y,y) 的代价。

我们需要设计的算法已经很明显了,扫的过程中我们维护一个序列 seq , seq_y=1 表示 (g_y,y) 可达,反之不可达。假设我们现在扫完了小于 K 的部分,现在要加入横坐标为 K 的点,假设其中纵坐标最小的点是 (K,z)

考虑可能的操作形式,一种是横坐标扩大到 K ,但纵坐标不变,这种我们对于 g_y 相同部分的 y(y\geq z) 统一处理,按照势能分析这样的次数是 O(n) 级别的,分析类似单调栈。

还有可能横纵坐标都加大,变成 (K,z) ,这种只要对于每种 g_y 维护可达的最大 (g_y,y) .

在执行完上面两种转移后,我们还可能执行横坐标不变,纵坐标加大的操作,用线段树容易维护 (K,y) 最多往上跳到哪。但我们是不是要对上面两种转移得到的 (K,y) 都执行下这种操作呢。想一想,其实只要转移第一种转移每段转移后得到的最大 y (更小的 y 要么不会增加新的可达点,要么新增的和最大的 y 一样)和第二种的 (K,z) 就好了(如果 (K,z) 可达的话)。

但其实因为我们可能会增加新的纵坐标,所以上面的分析不充分。假如我们新增了 (K,h) ,其中 h 是以前没有出现过的纵坐标,找到在已经出现过的纵坐标中 h 的前驱 p,如果 (K,p) 可达且 (K,p)(K,h) 的转移合法,那么可以扩展 (K,h) 了。

具体算法看 std 效果更佳哦。

Public Round #7 公告

2022-07-27 12:44:07 By p_b_p_b

Public Round #7 将在 2022 年 7 月 31 日 8:00 举行!比赛将进行 5 小时,共 3 道题,OI 赛制。

本次比赛的题目难度约为 NOI D1,所有题目都有部分分。

本次模拟赛的组题人为 p_b_p_b ,搬题人为 p_b_p_b, ezoilearner ,验题人为 superguymj, Qingyu

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public Round #6 题解

2022-07-03 14:50:28 By p_b_p_b

DNA 匹配

题目来源:

  • 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem H
  • Moscow Pre-Finals Workshops 2022 Day 4, Problem H

QOJ 链接:https://qoj.ac/contest/912/problem/3801

都 2202 年了怎么还有输出实数的非计算几何题啊?怎么相对误差在 0.05 以内都算对?

这么离谱的误差范围,不难想到这题应该想一些乱搞。

毛估估一下会发现容斥并不是个好方法。尽管取的 s_i 变多之后概率会迅速变小,但是组合数会迅速变大,所以简单地在某个大小进行截断是无法通过此题的。

另辟蹊径,注意到有一档部分分保证 ans\ge 0.01 ,所以可以用蒙特卡罗法进行随机抽样来估计概率。

蒙特卡罗法的不足之处在于,当答案太小时很难抽中一个合法的 DNA 序列,于是估计结果总是为 0 。但是我们可以限制随机抽样的范围,来保证抽中的序列总是合法的。所以可以想到,我们可以只在合法的 DNA 序列中抽样。

先设置一个贡献的分配方式。对于每一个 DNA 序列 t ,若其在所有 m 个串中可以匹配 k\ (k>0) 个,那么 t 会给每个能匹配的 s_i 带来 \frac 1 k 的贡献。

我们对每个 s_i 分别计算贡献。仍然使用蒙特卡罗法,但是显然只有能匹配 s_i 的 DNA 序列才能对 s_i 带来贡献,因此我们让抽取的 DNA 序列 t 在匹配 s_i 的序列中随机,最后再除掉匹配 s_i 的概率。这样就解决了答案太小的问题。

也可以让 t 只给第一个匹配的 s_i 带来 1 的贡献,做法是一样的。

区间数颜色

题目来源:

  • Petrozavodsk Winter 2022. Day 2. KAIST Contest + KOI TST 2021, Problem H

QOJ 链接:https://qoj.ac/contest/820/problem/2559

考虑假如存在 L_j\le L_i,R_i\le R_j,i< j,那么 i 一定比 j 要早出现在答案里。

一开始,我们把区间按照左端点排序。

当一个区间包含的所有区间都已经加入答案之后,我们再把这个区间加入候选集合。一开始,我们先把不包含其他区间的区间加入候选集合。我们把候选集合里的区间按左端点排序,这样它们的编号也是有序的(事实上,你发现这样右端点也是有序的)。

考虑离散化之后,区间的端点把整个数轴划分成 O(n) 个段,我们每次把某个区间加入答案,相当于覆盖掉某些段。那么一个段被覆盖后,包含这个段的区间在候选集合里是连续的一段。

我们对于每个区间维护一个 \text{remain}_i 表示现在第 i 个区间里没被覆盖的段长之和,对于不在候选集合里的,我们认为是 +\infty

那么就是对标号在某个区间内的 \text{remain}_i 减去这段的长度。我们可以用一个 set 维护哪些段没被覆盖,然后用一个树状数组维护一个区间内没被覆盖的段长之和,这样我们在把某个区间加入候选集合的时候也可以知道它的 \text{remain}

考虑我们把某个区间加入答案后,我们就从候选集合删去它后,此刻可能有一些区间可以加入候选区间,那么找到候选集合里这个区间的前驱 j 和后继 k,那么可以加入的区间一定包含于 (L_j,R_k),那么我们需要它的编号比 j 大,并且右端点比 R_k 小,那么每次找到标号在 (j,n] 里的区间里右端点最小的区间尝试加入,再用一棵线段树维护即可。

复杂度 O(n\log n)

情报传递 2

题目来源:第13回日本情報オリンピック 春季トレーニング合宿, Day 4, Task 漢字しりとり(Kanji Shiritori)

QOJ 链接:https://qoj.ac/contest/337/problem/1407

算法 1

通信题好难啊,还是弃疗吧。直接让 Spy 把 Participant 不知道的信息都发送过去咋样?

计算一下,一共需要发送 K 条边的边权,总共需要 K \cdot \left\lceil \log_2 W\right\rceil = 5 \times 54 = 270 个 bit。随后让 Participant 运行 Floyd 算法,记录过程中更新的最短路并复原该路径即可。

共需 270 个 bit,可以通过子任务 1,得到 5 分。

算法 2

注意到其实 Participant 不需要知道这些边的边权,甚至不需要知道最后最短路的长度 - 他只需要知道方案就可以了!

注意到由于所有边权未知的边的起点均相同,又有所有边权均非负,这意味着我们不可能经过一个顶点超过一次,所以我们可以将最短路分为 K+1 类:

  • 1 \leq i \leq K 类经过了第 i 条未知边
  • 0 类没有经过任何未知边。

注意到对于第 0 类,我们可以直接删掉所有未知边跑最短路,其余第 i 类最短路一定形如 S_j \to A_i \to B_i \to T_j 的形式,同样可以删掉所有未知边来跑。

因此,我们只需要让 Spy 预先跑出所有询问的答案,并将询问类型发送给 Participant 即可。

一共需要 Q \cdot \left\lceil \log_2 (K+1) \right\rceil = 60 \times 3 = 180 个 bit,刚好可以在子任务 2 中获得 11 分,共获得 16 分。

算法 3

注意到算法 2 中,一组询问只需要发送一个 0 \sim 5 内的数,却要使用 3 个 bit,有些愚蠢。我们可以仿照进制转换,将这个 60 位的 6 进制数直接转成 2 进制数发送过去,然后再转换回来即可。

如果懒得写高精度,也可以直接用 8 个 bit 压 3 个数(6^3 = 216 < 2^8 = 256),这样需要 20 \times 8 = 160 个 bit,在子任务 2 中获得 15 分,共获得 20 分。

如果写了高精度,那么 6^{60} = 48873677980689257489322752273774603865660850176,而注意到 2^{156} = 91343852333181432387730302044767688728495783936,因此我们只需要发送 156 个 bit,在子任务 2 中获得 17.4 分,共获得 22.4 分。

当然事实上我们可以利用长度作为信息,只发送 155 个 bit,获得额外的 0.6 分,这样就可以在子任务 2 中获得 18 分,共获得 23 分。

算法 4

我们设 f(i, a, b) 表示对于第 i 个问题,第 a 种最短路和第 b 种最短路哪个更短。

那么对于 Participant 而言,他只需要对所有 0 \leq i < Q, 0 \leq a,b \leq 5,都得到 f(i,a,b) 的值,那么问题就解决了。

1.png

考虑对于以上三组询问中,方案 1 比方案 2 优秀,当且仅当 d_1+e_1+f_1 < d_1 + e_2 + g_1,即 e_1 - e_2 < g_1 - f_1。同理,我们可以发现,对每个 0 \leq i < Q,方案 a 比方案 b 优秀,都可以表示成不等式 e_a - e_b \leq X_{i,b}-X_{i,a} 的形式。注意到双方事实上都知道 X_{i,b} - X_{i,a} 的值,于是我们可以对所有 \binom{6}{2} = 15 种不同的 0 \leq a < b \leq K,计算出 X_{i,b} - X_{i,a} 的值并将他们排序。随后由 Spy 发送给 Participant 一个值 R_{a,b},表示从大到小 R_{a,b}X_{i,b} - X_{i,a} 是能满足 e_a-e_b \leq X_{i,b}-X_{i,a} 的最后一个 i。这样我们便成功发送了 f(i,a,b) 的值。

总共有 15(a,b),每个需要发送一个 0 \sim Q 内的值,共需 \frac{K(K+1)}{2} \left\lceil\log_2 (Q+1)\right\rceil = 15 \times \left\lceil \log_2 61 \right\rceil = 90 个 bit。可以在子任务 2 中获得 43 分,共获得 48 分。

当然你也可以结合算法 3 中的优化方法,61^{15} = 602486784535040403801858901 < 2^{89},因此只需要发送 88 个 bit 即可,获得额外的 0.3077 分。

算法 5

注意到算法 4 的本质即为,我们不断选取 a,b,并比较有多少组询问中 a 优于 b,基于此将所有询问分成两组。

Spy 将所有的限制均发送给了 Participant,但事实上双方可以预先商定策略,因此我们不妨固定选取 a,b,并考虑分组的过程:

2.png

注意到对于固定的 a_i, b_i,我们发送的本质即为 m 的值。虽然参与排序的段很多,但由于 m 一定恰好落在了一组询问区间中,因此事实上,只有一组询问区间的 m 是有用的,其余的 m 并不会划分出更多的区间:

3.png

注意到我们已经预先将询问排序,因此当在进行到第 i 回比较时,在此回合参与比较的询问是一段连续的区间 [L_i, R_i],考虑不发送 m 的值,而是发送 m-L_i 的值。这样的问题是我们不知道 m 落在了哪一个区间中,因此我们考虑修改 a,b 的顺序。若干个随机算法需要发送 70 \sim 80 个 bit,可以得到 55 \sim 78 分。

不妨假设在第一回,我们进行了询问 (x, y),考虑在第二回进行 (x, z)。注意到由于我们已经确定了 x 最优的范围,因此只有 z \in [L_1, R_1] 时,m_{xz} 的值才有意义,否则一定是要么整个区间被划给了 x(等价于 x=R_1),要么是整个区间被划给了 z(等价于 x=L_0)。

4.png

因此我们直接这样进行比较,就只需要发送 m_i-L_i 的值。

我们可以通过一边预处理到此时的 [L_i, R_i],一边计算出所需位数 d,就可以提取出接下来的 d 位用于存储 m_i-L_i

5.png

通过分析,发现当每段被划分的相等时,所需的代价最多,此时代价为: \sum_{i=1}^{K} i\left\lceil\log_2 \frac{Q+1}{i}\right\rceil 总共需要 64 个 bit,期望得分 100 分。

Public Round #6 公告

2022-06-29 12:16:46 By p_b_p_b

Public Round #6 将在 2022 年 7 月 3 日 8:00 举行!比赛将进行 5 小时,共 3 道题,OI 赛制。

本次比赛的题目难度约为 NOI D1,所有题目都有部分分。

本场比赛有一道通信题,请不熟悉的选手预习题目特点和提交格式!

本次模拟赛的搬题人为 p_b_p_b, cdw, Qingyu,组题人为 p_b_p_b 。

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public Round #5 题解

2022-06-12 13:38:33 By p_b_p_b

双向奔赴

题目来源:

  • XXI Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Problem C

QOJ 链接:https://qoj.ac/contest/776/problem/3301

一个强连通分量一定可以由如下过程产生:

  1. 初始有一个集合 S,包含其中的一个点。
  2. 每次选择一条链 u\rightarrow v_1 \rightarrow v_2\rightarrow\cdots\rightarrow v_k\rightarrow w,其中 u,w\in S ,将 v_1,v_2,\cdots,v_k 加入到 S 中。

对于 (i,j) 的无向边,我们可以默认代价较小的那个方向的有向边一定出现,然后将代价同时减去这个较小值。我们可以状压 dp 这个过程,用 d_S 表示集合变为 S 的最小代价。定义 f_{S',v,w} 表示目前考虑了一条 uw 的链,同时这条链已经走到了 v 点,还剩余 vw 的部分没有完成, 表示 S' 并上这条链中 uv 的部分,此时的最小代价。可以直接枚举链上 v 的下一条边转移。需要注意不能同时包含连接两个点的两个方向的有向边。时间复杂度 O(2^nn^3)

循环移位

题目来源:

  • Petrozavodsk Winter 2022. Day 7. Gennady Korotkevich Contest 6, Problem I
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Gomel, Problem I

QOJ 链接:https://qoj.ac/contest/825/problem/2624

经过打表,发现满足条件或不满足条件的排列都看不出任何性质。

那就只能暴力一点,用 O(2^{n-1}) 的时间枚举每个 i 是否有 a[i]<a[1] ,以此获得一个大小关系树。然后再计算有多少个满足条件的排列也同时满足这个大小关系树。

注意到如果当前这个 a[i] 在之前已经被考虑过,那么必然有 a[i]>a[1] 。那么感性理解一下,随着 i 增大,a[i] 从未被考虑过的概率越来越小,从而可能的大小关系树的数量会远小于 2^n

写一个带剪枝的 dfs ,发现 n=42 时只有 \approx 10^9 种可能,因此直接暴力打表即可。

和平共处

题目来源:

  • RuCode 2020 Division A+B Championship Round, Problem I
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Moscow, Problem I

QOJ 链接:https://qoj.ac/contest/923/problem/4219

题解的做法几乎没有用到平面黑白点的任何性质。

利用一些二分图匹配的性质,不难发现题意等价于求这张二分图的字典序最小的最大匹配,字典序的定义为匹配白点集合的字典序,下面简称字典序最小最大匹配为最优匹配。

我们给出结论:如果能在 T(n+m) 的时间复杂度内计算出左右部分别为 n,m 个点的二分图的最小割以及方案,那么可以在 T(n+m)\log {n} 的时间内计算出左部的最优匹配。这里最小割的定义为:设左部和右部分别为 L,R,一个割由左集和右集 X,Y 组成,满足 X\bigcap Y=\emptyset,X\bigcup Y=L\bigcup R 并且 X\bigcap LY\bigcap R 之间不存在边。割的大小定义为 X\bigcap R+Y\bigcap L,令 X_l=X\bigcap L,X_r=X\bigcap R,(Y_l,Y_r) 同理。

具体的做法如下:考虑过程 F(S_1,S_2,S_3) 表示你需要求出左部为 S_1\bigcup S_2,右部为 S_3 的最优匹配,并且 S_2 中所有元素小于 S_1 中元素且一定在最优匹配中,答案就是 F(L,\emptyset,R)

S_1 按照元素大小划分成大小相同的两部分,元素较小和较大部分分别设为 X,Y。求出 (S_2\bigcup X,S_3) 的一个最小割,左集和右集分别设为 (A_l,A_r),(B_l,B_r)

引理 1(B_l\bigcup Y,B_r) 的最优匹配一定包含 B_l

首先 (B_l,B_r) 的最大匹配大小为 |B_l|,因此包含 B_l,注意到 Y 中所有元素大于 B_l 中元素,由匈牙利算法可得,(B_l\bigcup Y,B_r) 的最优匹配包含 B_l\square

引理 2(X\bigcup S_2,S_3) 的最优匹配由 (A_l,A_r)(B_l,B_r) 的最优匹配组成。

两者之间的边只存在于 A_rB_l 之间,这些边不可能成为匹配边,否则这个匹配大小达不到 |A_r|+|B_l|

引理 3(S_1\bigcup S_2,S_3) 的最优匹配由 (A_l,A_r)(B_l\bigcup Y,B_r) 的最优匹配组成。

考虑在 (X\bigcup S_2,S_3) 的最优匹配的基础上,将 Y 中元素逐个加入,模拟找增广路的过程,由于 Y 中元素较大,这样得到的结果就是最优匹配。

每次找到的增广路不可能包含 A,因为 A_l 只和 A_r 相连,A_r 所有点均已匹配且匹配点均在 A_l,一旦增广路走到 A 就无法出来且找不到未匹配点。因此每个点加入后,A 内部的匹配不会改变。\square

(A_l,A_r) 的求解直接调用 F(A_l\bigcap S_1, A_l\bigcap S_2, A_r)。对 (B_l\bigcup Y,B_r) 的求解调用 F(Y,B_l,B_r)。注意到每次递归,每个点恰好会递归至一侧,并且 S_1 的大小减半。递归树仅有 \log n 层,复杂度 T(n+m)\log n

考虑求出一组最小割:这可以贪心解决,具体的,先求匹配,将所有点按照 x 轴排序并枚举,加入黑点时将 y 坐标加入集合,加入白点时找集合中最大的不超过当前白点 y 坐标的黑点,匹配两个点并将黑点从集合中删去,如果找不到则认为匹配不上。然后从所有未匹配的白点开始 bfs,将所有走到的黑点以及他们对应匹配的白点不断加入队列,这可以通过线段树优化建图完成,因此 T(n)=O(n\log n)

总复杂度 O(n\log^2 n)

Public Round #4 题解

2022-06-05 14:49:28 By p_b_p_b

因为忘记宣传了,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,2n-1,n

n=4 时,可以通过 4 次询问来得到两个较小的数和两个较大的数。

n 更大时,不妨考虑增量法,逐个点加入,维护出 1\sim i 中的最小值及次小值的下标 l_1,l_2,最大值及次大值的下标 r_1,r_2,次小值 L 和次大值 R。注意你暂时无法区分 l_1,l_2r_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 并询问出新的 LR=x 同理。
  3. x\lt L,说明 a_{i+1}\lt a_{l_2}=L,将 l_2 更新为 i+1L 更新为 xR\lt x 同理。

最后使用两次操作 1 区分 l_1,l_2r_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

如果尝试直接求出第 nx 满足 x\times (10^k-1) 不包含 9 并没有比较好的转化,但是可以考虑求出第 nx 满足 x 的十进制表示不包含 9 并且 x10^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^kx 相减。

不难发现,如果无脑从低到高 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 大多少。所以可以把 xk 位分一段,设分成了 l 段。

那么可以先枚举 2^l 种段间退位的情况,然后所有段一起从低到高 DP ,记录目前的退位情况即可。

复杂度大概是 O(4^l(k+\log n)^2) 吧。

算法 4

把算法 2 和算法 3 拼起来即可。

Public Easy Round #2 题解

2022-05-01 13:02:01 By p_b_p_b

简单数据结构

题目来源:

  • Petrozavodsk Winter 2022. Day 2. KAIST Contest + KOI TST 2021, Problem A
  • XXII Open Cup, Grand Prix of Daejeon, Problem A

QOJ 链接:https://qoj.ac/problem/2552

u_x+v_x\ge u_y+v_y 当且仅当 u_x-u_y\ge v_y-v_x,以 u_x-u_yv_y-v_x 分别作为下标,用线段树维护。时间复杂度 \mathcal O(Q\log Q)

情报传递

题目来源:第 14 回日本情報オリンピック 春季トレーニング合宿 (JOISC 2014/2015), Day 3, Task 道案内 (Navigation)

QOJ 链接:https://qoj.ac/problem/1212

算法 1

对每个点记录其到终点的距离 d_i。容易发现,如果此时我们所在的点 Sd_S=0,则我们所在的点即为终点,否则一定是前往 d[\cdot] 值最小的点。

该算法所需 m\leq n,期望得分 0.00008 分。

算法 2

容易注意到 d[\cdot] 的编码是连续的,即对于任意条边 (x,y),定有 |d_x-d_y| = 1,因此 S 的邻居中一定恰好有一个点满足 d[\cdot] = d[S] - 1。注意到我们只需要记录 d[\cdot ] \bmod 3 的值,即可得到对应的点是哪一个,因此我们只需要记录每个点到终点的距离模 3 的值即可。

该算法所需 m=2,期望得分 44.44444 分。

算法 3

注意到我们的目标是向终点走,因此如果我们把这棵树视为以 T 为根的一棵有根内向树,则我们只需要找到每个点所对应的唯一的出边。

由于在询问过程中我们唯一能确定的信息即为起点 S 出边所到的点的编号,因此我们尝试来使用编号对每条边随意定向,例如记 \mathrm{dir}(x,y) = \begin{cases} x \to y & x < y \\ y \to x & \mathrm{otherwise}\end{cases}

此时有一些边的定向正确,一些边的定向不正确。我们为 T 随意赋予一个标号,并从 T 开始 DFS 整棵树。在对 X DFS 时,如果接下来访问到的点 Y 的定向不正确(即 Y < X,初始定向为 Y \to X),则我们将 Y 的标号置为与 X 不同,否则将其标号置为与 X 相同。

这样,当一条边的两端点被赋予的标号相同时,这条边的方向即为 \mathrm{dir}(x,y),否则即为其取反后的方向。我们便可以在询问过程中复原出边的方向。

该算法需要 m=1,期望得分 100.0

运算符

题目来源:

  • Benelux Algorithm Programming Contest 2021, Problem G
  • United Kingdom and Ireland Programming Contest 2021, Problem G
  • Petrozavodsk Winter 2022. Day 4. Almost Northern Contest

QOJ 链接:https://qoj.ac/contest/822/problem/2286

运算符太多了,胡乱询问肯定是问不出来的。所以考虑从后往前依次确定。

容易想到一个 O(n) 的暴力做法:在尝试确定 \text{op}_k 时,令 a_0=\cdots=a_{k-1}=0,a_k=\cdots=a_n=1 即可。

如何能够一次多确定几个呢?一种思路是使用奇奇怪怪的 k 进制编码,但是为了不被 \bmod {(10^9+7)} 扰乱,能确定的位数是比较有限的。

更好的做法是尝试充分利用 10^9+7 种返回值:因为 10^9+7\approx 2^{30} ,所以只要随机 16 个数放在最后,就会有比较大的概率能通过返回值唯一确定最后 15 个操作符。在询问前预处理出一组合法的 16 个数即可。

仙人掌

题目来源:

  • Petrozavodsk Winter 2022 Day 7: ICPC Camp Day 2, Gennady Korotkevich Contest 6, Problem E
  • XXII Open Cup, Grand Prix of Gomel, Problem E

QOJ 链接:https://qoj.ac/contest/825/problem/2620

先使用 tarjan 算法把仙人掌上的有向环缩起来,获得一个 DAG 。

考虑在一般的 DAG 上求传递闭包大小会遇到的问题:如果直接使用 dp_x=1+\sum_{(x,v)\in E} dp_v ,那么每个点会被计算路径条数次。

但是仙人掌并没有比树多太多边,也就是说它非常稀疏,那么被多算的次数就不是很多。

f_x 表示 x 能到达的点数(不算重),那么仍然考虑 f_x=1+\sum_{(x,v)\in E}f_v 会多算什么。注意 f_v 都是正确的,因此只会有一些点被算了两次,把它们减掉就行了。

哪些点被算了两次呢?只有在 x 所在的一个环恰好可以被拆成两条路径 x\to v_1\to \cdots\to y,x\to v_2\to \cdots\to y 时,f_y 会被算两次。因此只要对于每一个这样的环,把 f_y 减去即可。

复杂度 O(n)

2048

题目来源:Petrozavodsk Summer 2021. Day 4. Shanghai ICPC Camp 2021 Onsite Day 1 by PKU

QOJ 链接:https://qoj.ac/contest/694/problem/1849

请注意原题的题意有误。

考虑题意等价于这个过程:维护一个栈,如果栈的大小达到 n 游戏结束,否则每次按照分布随机一个 x,尝试插入 x,与栈顶相同则弹出栈顶并尝试插入 x+1,以此类推。

考虑类似这么设计 dp 状态:一个大小限制为 i 的栈,栈底已经有了一个 j,当栈大小达到限制或栈底变为 j+1 时,得分的期望以及栈底变为 j+1 的概率。

这么设计状态的好处是:对于某个栈,截止到栈被填满或当前栈顶对应元素变化时,概率以及得分期望仅与栈顶元素以及剩余空位数有关,而与剩余元素无关。

那么考虑转移,重新具体地设计状态:设状态 A_{i,j},B_{i,j} 表示大小为 i 的空栈不断操作,某一时刻栈中只有元素 j 的概率,以及此时总得分期望,C_{i,j} 表示大小为 i 的空栈,不断操作后栈被填满,并且栈底为 j,此时总得分期望,D_{i,j} 表示大小为 i 的栈,栈底已经填了 j,不断操作直到栈被填满,此时总得分期望。注意这里的期望均指条件成立前提下的期望乘上条件被满足的概率。

这么设计状态实际上对应了三种情况:接下来填入一个较小元素最终栈底被合并,接下来填入一个较小元素最终栈被填满,接下来填入一个较大元素最终栈被填满。

那么转移实际上就比较简单了:

  • A_{i,j}=p_j+A_{i,j-1}A_{i-1,j-1}

  • B_{i,j}=A_{i,j-1}B_{i-1,j-1}+B_{i,j-1}A_{i-1,j-1}+A_{i,j-1}A_{i-1,j-1}2^{j}

  • C_{i,j}=B_{i,j}(1-A_{i-1,j})+A_{i,j}(\sum_{k=0}^{j-1}C_{i-1,k}+\sum_{k=j+1}p_k D_{i-1,k})

  • D_{i,j}=\sum_{k=0}^{j-1}C_{i-1,k}+\sum_{k=j+1}p_k D_{i-1,k}+A_{i-1,j}(D_{i,j+1}+2^{j+1})+B_{i-1,j}

最终答案即为 \sum_i p_i D_{n,i}

简单前缀和优化即可做到 O(n^2+nm)

Public Easy Round #1 公告

2022-04-20 22:17:39 By p_b_p_b

Public Easy Round #1 将在 2022 年 4 月 23 日 8:00 举行!比赛将进行 5 小时,共 5 道题,OI 赛制。

著名 OIer jiangly 曾经说过,“你不过 T1 你过啥题啊 你不过题你打锤子啊”。为了训练选手迅速通过 T1 的能力(以及过不掉 T1 时调整心态的能力),本次比赛的题目难度均为省选 T1-T1.5 ,并且大多数题目不设部分分。

jiangly.jpg

本次模拟赛的搬题人为 cdw, p_b_p_b ,组题人为 hehezhou ,验题人为 AutumnKite, chenkuowen01

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

共 22 篇博客
  • 1
  • 2
  • 3