某岛

… : "…アッカリ~ン . .. . " .. .
January 4, 2022

Hello 2022

这场和 Youtube 主播 SecondThread 一个房间,(并且差点碾压了他!)
LGM 不过如此

这场掉分的应该都是猜结论失败然后被 D 题拉扯了太多的时间的缘故。。。

传送门

https://codeforces.com/contest/1616
https://t.me/algorithm_daily_of_minako/3222
https://www.facebook.com/dreamoon4/posts/6748183141918539

Problem D. The Winter Hike

给一个 2n x 2n 的矩阵,开始左上角 nxn 的子矩阵有棋子,你需要把这些棋子移动到右下角 nxn 的格子里,支持的操作是 shift 一行 or 一列,
矩阵中有一些障碍,对于每个障碍,你可以花费一个代价删除它,操作没有代价可以任意进行,只要不遇到障碍,问最少花费多少代价满足要求。

结论题,取这 8 个数 + 右下角矩阵的值。
00aa
00aa
aa00
aa00

Why?首先直接缩点 Dijkstra 是不够充分的的,反例是下面这种。

000—
00000-
000-0-
—000
—000
—000

虽然我们成功的将左上角的材料运输到右下角,但是没有足够的空间去华容道。
有简单的方法判断是否有足够的空间调整,就是只对目标区域的四个角进行缩点。

而这于我们开始所说的结论是等价的。

Problem E. New School

等价于动态维护括号序列的合法性。
直离散化 + 线段树即可。

比赛时犹豫了好久最后决定写 SBT(唯一优势大概是不用离散化)。。。不过没能写完。。= =

SBT。。

Problem F. Strange Instructions

给定一个 01 字符串,你可以对子串进行替换操作,使字符串变短同时产生一定得分:

1 – ’00’ -> ‘0’, +=a
2 – ’11’ -> ‘1’, +=b
3 – ‘0’ -> ”, -=c

并且还要求,一些操作之间不能相邻,问最大得分。

dp?

Problem G. Weighted Increasing Subsequences

给定一个数列 A,问所有递增子序列的权重只和。
数列 A 的递增子序列 a 的权重定义为,
a 中有多少项 > Sa,Sa 等于 A 中不包含子序列元素的后缀中的最大值。
(当后缀不存在时 Sa 为无穷大)

dp。