「贪心」做题记录

1. P2672 [NOIP2015 普及组] 推销员

   由于不会走多余的路，所以行走产生的疲劳值只和最远的被推销的住户有关。设 \(f_X(i)\) 表示总共选 \(X\) 家住户，且第 \(i\) 户是最远的被推销的住户的情况下，最大的疲劳值。显然可以贪心地在前 \(i-1\) 户中选择 \(X-1\) 户疲劳值最大的住户，所以 \(f_X(i) = 2S_i + A_i + 前(i-1)个A_j中最大的(X-1)个A_j的和\)。

   可以用小根堆（优先队列）维护前 \(k\) 大和。由于要枚举 \(X\)，总的时间复杂度为 \(O(N^2\log N)\)，可以得到 60 分。代码

   下面是本题的正解贪心做法。

   考虑贪心地选取前 \(X\) 个疲劳值最大的住户。但这并不一定是最优的：我们可能选取一个疲劳值更小，但比原来所有住户都更远的住户，从而通过行走距离获得更大的疲劳值。

   具体地，我们要放弃原先的多少个住户呢？实际上最多放弃 1 个，然后选择未被选择的住户中，\(2S_i+A_i\) 最大的住户 \(i\)。如果放弃多于 1 个住户，一定不优于只放弃 1 个。（不知道怎么表达证明过程）

   AC 代码

2. [ABC137D] Summer Vacation

   如果一个工作在某一天做完之后，直到结束都不能领到工资，那么还不如不做。所以可以把一个工作可以做的区间看作一段前缀。从后往前枚举天数，维护可以做的工作的集合，每次选择集合中价值最大的工作来做。（不会严谨证明，但前缀的观点或许有助于理解。）

   提交记录

3. [AGC004D] Teleporter

   洛谷的题解都他妈是什么东西？怎么都这么意识流，还有的是如写

   首先根据题目中图的性质，可以得出在忽略 \(1\) 出发的边以后，图一定是一棵以 \(1\) 为根的内向树。

   证明：删去 \(1\) 出发的边显然不影响其它点到 \(1\) 的可达性，这时边数 \(=\) 点数 \(-1\)。根据连通性，可以得知图是树。再根据除了 \(1\) 之外的点都可达 \(1\)，可以得知图是以 \(1\) 为根的内向树。

   从树的角度来看，可以得出 \(1\) 必须指向自己。因为在树上两点的路径唯一，而且是内向树，如果一个点的深度小于 \(K\)，并且没有这个自环，它就无法通过恰好 \(K\) 次传送到达 \(1\)。

   如果一个点的深度大于 \(K\)，那么它显然无法经过恰好 \(K\) 次传送到达根节点；否则一定可以，缺少的部分可以通过一直走 \(1\) 的自环来补足。那么我们把问题转化成了：给定一棵树，修改最少的边，使得所有点的深度不大于 \(K\)。

   这个问题还可以进一步转化：删除最少的边，使得剩下的所有弱连通块（每个弱连通块都是树）都满足以下条件：

   • 如果根节点为 \(1\)，那么树的高度不超过 \(K\)。
   • 否则，树的高度不超过 \(K - 1\)。

   采用 dfs ，自下往上解决此问题。如果一棵子树的高度大于等于 \(K - 1\)，并且它的父节点不是 \(1\)，那么需要删除它连向父节点的边，否则更新父节点的高度。

   function<void(int)> dfs = [&](int u)
   {
       h[u] = 0;
       for(int v: G[u])
       {
           dfs(v);
           if(u != 1 && h[v] == K - 1)
               ans++;
           else
               h[u] = max(h[u], h[v] + 1);
       }
   };
   dfs(1);
   

   这样得出来的图一定满足条件，但删边数的最少性不会证明。官方题解用的就是这个做法。

   完整代码