2024.5.21日记

Fireworks_Rise · 2024-05-21 13:19:44 · 个人记录

每日闲话

去还没干的篮球场，打篮球，鞋子全湿了，还bzd是否喝到了一些“篮球场水”...

今天看到了几句很好的话：

dp 的优化基本就是对着原来的代码做等价变形。
对于这种区间覆盖问题大部分情况是贪心，小部分情况是DP，还有极少部分是网络流

练题

Hot Start Up

CF1799D1 (easy version)

CF1799D2 (hard version)

思路

对于我来说非常难想啊。

一、首先看 n,k \le 5000 时，这边很容易想到定义 f_{k,i,j} 为运行完前 k 个程序时，第 1 个 CPU 最后的程序类型是 i，第 2 个 CPU 最后的程序类型是 j 时的最短时间，然后就可以推出：

f_{k-1,i,j}+cold_{a_k} \to f_{k,a_k,j} \\ f_{k-1,i,j}+cold_{a_k} \to f_{k,i,a_k} \\ f_{k-1,i,a_k}+hot_{a_k} \to f_{k,i,a_k} \\ f_{k-1,a_k,j}+hot_{a_k} \to f_{k,a_k,j} \\ \end{cases}

时间复杂度为 O(nk^2)。

接着就玄妙了，可以想到两个 CPU 中肯定有一个是 a_{k-1}，那么就可以优化掉一维，f_{k,i} 为运行完前 k 个程序时，第 1 个 CPU 最后的程序类型是 i，同样也可以推出第 2 个 CPU 最后的程序类型。再通过小小贪心，进行转移即可，时间复杂度为 O(nk)，细见代码。

然后，让我们进发这个问题的“硬版本”，n,k \le 3\times 10^5，可以发现原来的转移方程似乎可以用线段树优化哎，只需要无脑区间修改和区间求最小值操作即可。

Too Many Segments

CF1249D1 (easy version)

CF1249D2 (hard version)

思路

这题就直入正解，跟闲话中的一样，这题考虑贪心，并用优先队列（堆）去维护，对于当前点 i 被覆盖的次数，可以用前缀和 sum_i 维护，若 sum_i > k，那么要删掉 sum_i-k 条线段，可以证得所删掉的线段右端点 r 越远越优，暴力求即可。

拓展

关于优先队列的排序：

struct Node {
    int l,r;
    int id;
} a[N];
struct cmp {
    inline int operator () (const Node& x, const Node& y) const {
        return x.r<y.r;
    }
};
priority_queue<Node,vector<Node>,cmp> q;

这里由于 priority_queue 全部和 sort 等是相反的，且默认是大根堆。

这代码里的 cmp 里虽然定义是 <，可反过来就是 > 了 ~~（口胡解释）~~。详细见文章，其中有讲。

非常nice的文章：

一文讲明白优先级队列为啥按less排序却是从大到小