「Log」2023.8.31 小记

发布时间 2023-09-01 08:40:46作者: Eon_Sky

序幕

自然醒,七点出头,到校快八点。
补博客,更新题单。

\(\color{royalblue}{P1545\ [USACO04DEC]\ Dividing\ the\ Path\ G}\)

单调队列优化 DP,转移方式的思考过程较为思维。
\(\text{Link}\)

\(\color{limegreen}{P1442\ 铁球落地}\)

线段树建立关系,简单 DP,调半天,忘记把球横坐标离散化了。
\(\text{Link}\)

间幕 \(1\)

依然是杂题选讲,没胡上,大部分都是图论相关,思维的。
中午不饿,没点饭吃,打几分钟块就接着做题了。

\(\color{blueviolet}{CF960F\ Pathwalks}\)

考虑按顺序加入每一条边,减少了编号的限制,考虑找到所有比当前边权小的点中答案最大的进行转移即可。

贪心地进行转移,想到了用线段树维护,为了方便采用了题解中 map 的方法,第一次知道 map 能这么用。
\(\text{Link}\)

\(\color{blueviolet}{P3506\ [POI2010]\ MOT-Monotonicity 2}\)

不难看出是 DP,注意转移(最优子结构)的正确性证明即可。
\(\text{Link}\)

间幕 \(2\)

下午杂题,吃饭,与 lhy 进行了抽象地交流。

\(\color{blueviolet}{P3628\ [APIO2010]\ 特别行动队}\)

斜率优化简单题,不到为啥调那么半天。
\(\text{Link}\)

\(\color{blueviolet}{P2900\ [USACO08MAR]\ Land Acquisition G}\)

斜率优化,去重后,进行转移,注意细节即可。
\(\text{Link}\)

尾声

配置笔记本到半夜,沉睡。