洛谷 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，不会。