NOIP 计划 R14

haozexu / 2024-10-25 / 原文

洛谷 NOIP 计划 14

2024 年 10 月 17 日

Status: CLOSED

Author: 云浅知处

\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单,10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等,能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难,独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难,独立思考只能想出 \(50\%\) 以下

Overview

\(\HD\)

\(205/400\) Good!

Note: 最后一题的那个暴力比较赖,期望 5 分实际 100 实在是不太好。

A. 澈明之泉 (fountain)

\(\EZ^{+}\)

性质一 一种简单情况是,如果有现成的一行为满,则直接把这一行进行复制是最优的

性质二 我们还发现,如果一行满的都没造出来,肯定是不可能达成目标的

所以必须考虑怎么造出一行满的

性质三 如果原本不存在一列为满,则在构造一行为满的过程中不可能凑出
一列为满的,最优方案中,也不可能把一列为满给破坏掉

性质四 最优方案可以只对一行使魔法来构造满的一行

我们检查每一行,看那一行对那一行使用魔法能够最快构造“满的”一行,随后加上 n-(满的列的数量) 即可

UPD 性质四不对,没有考虑多次操作组合作用

00000
00000
00000
10101
00000

可以将第四行先复制一次,这样就构造了一个可以影响到第四行的黑格子。

换言之,如果要把第 \(x\) 行变成黑的行,假如第 \(x\) 列不存在黑的格子,若本行有黑色也可以。不会从其他地方借黑色,因为如果自己有黑色,则用自己的黑色更优,如果没有,则换成那个有黑色的做这个操作一定更优。

B.String Theocracy (theocracy)

\(\EZ\)

整体二分复习题可是没学会而且以为 \(\log^2n\)\(\sqrt{n}\) 快没写莫队写了个树状数组上倍增套平衡树浪费 2h 没想成 T3 且成功被卡常.jpg

C. 吃鱼流经(blossom)

\(\HD^{+}\)

\(70\) 分应该是比较能拿的,但是由于 B 题那个 SB 树套树写了太久导致没时间想。


注意到最终的图上,若只留下仍然存在的、跨块的关键点之间的边,连通性不改变。

至此结合 A 性质的 DP 能够获取 \(50\) 分,应该是无法进行优化,必须转化角度。

考虑由具体方案处理变成考虑一对数对的贡献,转化计数单位,这其实非常常见。

D. 背包 (pack)

神秘 DP,不会。