Qingyu的博客

博客

Public NOIP Round #1 题解

2022-09-10 21:22:33 By Qingyu
  • 搬题人:
    • 一维围棋:Wu_Ren
    • 斜二等轴测图:Wu_Ren
    • 盒子里的糖果:hehezhou
    • 冲塔:p_b_p_b
    • 波特分组:feecle6418
    • 别急:Y25t
  • 组题人:p_b_p_b
  • 验题人:syzf2222, Zeardoe, Dualqwq, yllcm
  • 题解:hehezhou, Wu_Ren, p_b_p_b, Y25t

一维围棋 (Div. 2 Only)

来源:

  • ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem A, AiGo
  • Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem A, AiGo

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

tutorial by Wu_Ren

枚举哪个位置去放棋子,首先如果上面已经有棋子就不能放,然后向左向右如果都是连续一段白再接一段黑,那么也不能放,否则一定能放。放了之后向左向右分别扫一遍即可知道占领了多少黑棋。

复杂度 $O(n)$ 或 $O(n^2)$。

斜二等轴测图 (Div. 1 + Div. 2)

来源:

  • 2018 Multi-University Training Contest 3. Problem B, Visual Cube
  • Petrozavodsk Summer 2020. Day 3: Songyang Chen Contest 3. Problem B, Visual Cube

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

tutorial by Wu_Ren

按照题意模拟即可,复杂度 $O(T(a+b)(b+c))$。

盒子里的糖果 (Div. 2 Only)

来源:

  • Petrozavodsk Summer 2021. Day 4: Shanghai ICPC Camp 2021 Onsite Day 1 by PKU. Problem F, Interval Shuffle

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

tutorial by hehezhou

算法一

令 $dp_{i,j}$ 表示 $i$ 次操作后,$a_j$ 的最大值。

那么有: $$\begin{cases}dp_{i,j}=dp_{i-1,j}&j\in[1,l_i)\bigcup(r_i,n]\\ dp_{i,j}=\max(dp_{i-1,j}+1,\max_{k\in [l_i,r_i]}dp_{i-1,k})&j\in[l_i,r_i]\end{cases}$$

即只需考虑 $i-1$ 步时的最大值即可推出 $i$ 步后的最大值。构造某位的最大值只需按照 dp 转移式逆推即可。

时间复杂度 $O(n^2)$。

算法二

考虑用线段树优化上述过程:

  1. 计算 $\max_{k\in [l_i,r_i]}dp_{k}$ 即为一次查询区间最大值。
  2. 更新 $dp$ 值可以表示为一次区间加和一次区间取 $\max$。

这是一个经典线段树问题,可以在 $O(n\log n)$ 的时间复杂度内解决。

冲塔 (Div. 1 + Div. 2)

来源:

  • National Olympiad in Informatics 2022. Problem 3, Towers

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

tutorial by p_b_p_b

先不管“每列只能冲至多两个塔”的限制,直接先把每行最左和最右的塔都冲掉。

这时候当然可能会出现某一列超过两个塔了。但是往好处想:如果超过两个塔,是不是说明中间那个塔就不需要冲了呢?

因此可以每次找到最靠右的一列,使得这一列有超过两个塔,然后把中间的那些塔全都往左移动一位。

不难发现每次这样操作之后仍然满足每个塔都被覆盖,并且 $O(n)$ 次操作之后就不会存在冲了超过两个塔的列了。

用 set 维护,复杂度 $O(n\log n)$ 。

波特分组 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2020. Day 7: Gennady Korotkevich Contest 5. Problem F, Flip
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Gomel. Problem F, Flip

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

tutorial by feecle6418

设 $S=\sum k$。

算法一

直接枚举每枚硬币哪面朝上,时间复杂度 $O(q2^{2n})$,可以通过第一个子任务,期望得分 $9$。

算法二

考虑先枚举每一种情况,用子集和变换预处理每种输入哪些会有贡献,时间复杂度 $O(2^{2n}n+S)$,可以通过前两个子任务,期望得分 $25$。

此外,可能存在一些高复杂度算法,可以通过前三个子任务。

算法三

首先,给定一种分组状态,它出现的概率是多少?设最后一个分到 A 组的人编号为 $i_A$,最后一个分到 B 组的人编号为 $i_B$,则概率为 $2^{-\min(i_A,i_B)}$。

对于每组询问,不妨假设全分在 A 组,枚举 $\min(i_A,i_B)=p$ 的值,计算分组方案数:

  • $p=b_k$,此时分组方案数为 $\binom{b_k-k}{n-k}$。
  • $p$ 位置分在 B 组,不妨设 $b_i < p < b_{i+1}$,则分组方案数为 $\binom{p-i-1}{n-1}$。对于固定的 $i$,$p-i-1$ 构成区间,恰当预处理前缀和可以 $O(1)$ 求出。
  • $p>b_k$ 且 $p$ 位置在 A 组,则分组方案数为 $\binom{p-k-1}{n-k-1}$。对于每种出现的 $k$,分别 $O(n)$ 预处理该式与概率的乘积的后缀和即可。

因为不同的 $k$ 只有 $\sqrt S$ 个,所以时间复杂度 $O(n\sqrt S+S)$,期望得分 $100$。注意边界。

本题也存在线性做法。

别急 (Div. 1 Only)

来源:

  • XXII Open All-Siberian Programming Contest named after I.V. Pottosin Final tour, II day. Problem 11: Captivating process
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Siberia. Problem 11: Captivating process

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

tutorial by Y25t

建两张有向图 $F,G$,对所有 $1\le i\le n$ 在 $F$ 中连有向边 $(i,f_i)$,在 $G$ 中连边 $(i,g_i)$。那么它们分别形成基环内向森林。

对于一个点 $u$ ,若它能沿着 $F$(或 $G$)中唯一出边走若干步能回到 $u$,则称它为 $F$(或 $G$)中的环点,否则称它为 $F$(或 $G$)中的树点。定义 $dep^F_u$ 为在 $F$ 中 $u$ 第一次走到环点所需步数。若 $u$ 在 $F$ 中是环点,则 $dep^F_u=0$,同时定义 $l^F_u$ 为 $u$ 所在环的长度,$d^F_u$ 为 $u$ 在其所在环上的编号(满足 $0\le d^F_u< l^F_u$ 且 $d^F_{f_u}\equiv d^F_{u}+1\pmod{l^F_u}$)。类似地定义 $dep^G,l^G,d^G$。

对于一块石板 $(x,y)$,不妨设 $dep^F_x\le dep^G_y$。考虑将时间分为 $[0,dep^F_x),[dep^F_x,dep^G_y),[dep^G_y,+\infty)$ 三段,分别判断是否会裂开。

$[0,dep^F_x)$

在这段时间里,$x$ 为在 $F$ 中的树点,$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $dep^F_x-dep^F_u=dep^G_y-dep^G_u$,即 $dep^F_u-dep^G_u=dep^F_x-dep^G_y$。
  • 在 $F$ 中 $u$ 是树点,且为 $x$ 的祖先。
  • 在 $G$ 中 $u$ 是树点,且为 $y$ 的祖先。

于是将询问离线后在 $G$ 的树部分进行 dfs。用 std::set 或动态开点线段树维护 $2n$ 个线段集合 $S_i(-n\le i\le n)$。在进入一个点 $u$ 时,在 $S_{dep^F_u-dep^G_u}$ 中插入线段 $[dfn^F_u,dfn^F_u+sz^F_u-1]$(其中 $dfn^F,sz^F$ 为在 $F$ 中的 dfs 序和子树大小),回溯时撤销。对于询问 $(x,y)$,在进入 $y$ 后判断 $S_{dep^F_x-dep^G_y}$ 中是否有线段覆盖了 $dfn^F_x$ 即可。

该算法加一些简单特判后可通过子任务 7。

$[dep^F_x,dep^G_y)$

在这段时间里,$x$ 为在 $F$ 中的环点,$y$ 为在 $G$ 中的树点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $d^F_u-d^F_x\equiv dep^G_y-dep^G_u\pmod{l^F_u}$ 即 $d^F_u+dep^G_u\equiv d^F_x+dep^G_y\pmod{l^F_u}$。
  • 在 $F$ 中 $u$ 是环点,且与 $x$ 在同一环中。
  • 在 $G$ 中 $u$ 是树点,且为 $y$ 的祖先。

于是可以用类似的 dfs 进行求解。

该算法加一些简单特判后可通过子任务 6。

$[dep^G_y,+\infty)$

在这段时间里,$x$ 为在 $F$ 中的环点,$y$ 为在 $G$ 中的环点。

该石板会在这段时间中裂开,当且仅当存在点 $u$ 使得以下三个条件同时满足:

  • $d^F_u-d^F_x\equiv d^G_u-d^G_y\pmod{\gcd(l^F_u,l^G_u)}$
  • 在 $F$ 中 $u$ 是环点,且与 $x$ 在同一环中。
  • 在 $G$ 中 $u$ 是环点,且与 $y$ 在同一环中。

std::set 维护三元组即可简单判断。

该算法可直接通过子任务 5。

结合以上三个算法即可通过本题。

评论

ytb2024
mike
  • 2023-10-04 15:39:32
  • Reply
specialuser
ytb2024
  • 2023-10-04 15:45:59
  • Reply
specialuser
mike
  • 2023-10-04 15:46:12
  • Reply
specialuser
normaluser
  • 2023-10-04 15:46:22
  • Reply
specialuser
specialuser
  • 2023-10-04 15:46:30
  • Reply
specialuser
@syr
  • 2023-10-04 15:46:48
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。