日记

这周只要考两次，今天不考。

Shuffling Songs# Link to

一眼做法 + 一眼实现 + 亿眼优化。

第一眼就看出来是个转图论。对于有相同的建边，然后搜出来最长的路径。然后就打了一个暴力。不出所料，T 了。于是加上了神秘小剪枝。不出意外，T 的地方变晚了。但是优化不动了。考虑记搜。因为 $n \le 18$，所以 vis 可以塞进一个二进制数里面，时空复杂度都是 $O(n^2 \times 2^n)$，十分的劣。

Messenger in MAC# Link to

两眼做法 + 两眼实现 + 调了 2h 的优化

第一道题的剪枝剪不动了就来看这题，但是写挂了，于是去把 T1 写出来就来写这道题了。

发现 $a_i$ 对于答案的贡献无关顺序，但是 $b_i$ 就有关，于是考虑把信息按照 $b_i$ 排序，然后做 dp，$dp_{i,j}$ 表示钦定 $i$ 一定被选，$[1,i]$ 里选了 $j$ 个的最小花费。答案就循环每个状态，找到最大的 $j$ 使得 $dp_{i,j} \le l$。

本来想的是单调栈优化的，但是好像不行，改成了前缀 $\min$ 优化就过了。

Vlad and Trouble at MIT# Link to

一眼做法 + 一眼实现 + 不用优化

这道题总共就花了 20min。那我上午苦思冥想的 2h 和调洪文的 2h 算什么？

对于每个点 $u$ 有 $dp_{u,0}$ 表示这个钦定这个点为 $\texttt{S}$ 时的最小代价，$dp_{u,1}$ 表示钦定它为 $\texttt{P}$ 的最小代价。对于本来就是 $\texttt{S}$ 的点 $u$，$dp_{u,1}$ 显然为 $\inf$，不进行转移。反之亦然。转移方式显然。

剩下 $3$ 题都是看题解过的。还需要巩固。

后日谈 # Link to 后日谈

然后下午就挺无所事事的，于是去把昨天 arc 的 b 改出来了。感谢 yzp 晚自习问我这道题，不然我绝对不会记得这道题。

改完了 arc194_b，去随便掏了两道 dp 写了，领悟 dp 小技能：状态存不下就把答案塞到状态里。

然后又去写了一道概期。起码是知道了怎么用高斯消元。

NOIp 是 11 月下旬，现在是 3 月中旬，我还有 8 个月的时间。