课程表

上午

• 讲评考试、$Tarjan$

下午

• 依然$Tarjan$

考试

• 我最讨厌订正了

1. $Task$ $1$：注意细节就可以了，这题不用订。
2. $Task$ $2$：我不知道为什么考试的时候脑子抽了，一道裸的贪心卡不出来，$emm......$竟可能把最高位变得越大即可。
3. $Task$ $3$：我真不知道为什么这题$TLE$了10个点，或许用的空间大跑的就比较慢？？这题可以用滚动数组，因为$dp[i][j][k]$只与$dp[i][...][...]$和$dp[i-1][...][...]$有关。不开心呐~~

4. $Task$ $4$：考试的时候，我一直在想$O(1)$的方法求出解，但是为什么不行呢？？无法证明这一点，我好菜啊$qwq$。可以发现沿着一三象限角平分线分开，左右的格点数是一样的，除了在这条将平分线上的点，即$P(x,y)，x=y$时，这部分可以后面加上，不要算两遍。

   • 核心$Code$：

   for (ll i = 1; i <= t; i++)
       ans = (ans + k / i) % MOD;
   for (ll i = t + 1; i <= k; i = t + 1) {
       t = k / (k / i);
       ans = (ans + (k / i) * (t - i + 1)) % MOD;
   }

5. $Task$ $5$：我觉得这是6题中最难的一道了，一道区间$dp$。先分析一下，发现如果要第$i$个元素出栈，则一定要把$i$上面的元素先出栈，然后再把$i$出栈，最后把$i$下面的出栈。这样，$[1,n]$的区间最值问题就变成了$[1,i]$和$[i+1,n]$两个问题。于是可以开一个$dp[l][r]$的$dp$数组，每次求出$dp[l][k-1]$、$k$、$dp[k+1][r]$这3部分的惩罚值，然后枚举$k$，就可以求出$dp[l][r]$的区间最小值，答案最后存在$dp[1][n]$。

现在来看怎么分别求出$dp[l][k-1]$、$k$、$dp[k+1][r]$。

• $dp[l][k-1]=dp[l][k-1]$，因为在栈的最上面，所以说，和原来的没有任何区别。
• $k=(t_l+t_{l+1}+t_{l+2}+...+t_{k-2}+t_{k-1}+t_k)\times d_k$，完成栈上面的产品的时间和乘以惩罚值即可。
• $$dp[k+1][r]=\sum\limits_{u=k+1}^{r}(t_u+t_l+t_{l+1}+...+t_{k-1}+t_{k})\times d_u$$

  $$=\sum\limits_{u=k+1}^{r}t_u \times d_u+(t_u+t_l+t_{l+1}+...+t_{k-1}+t_{k})\times \sum\limits_{u=k+1}^{r} d_u$$

  $$=dp[k+1][r]+(st_{k-1}-st_{l-1})\times (sd_{r}-sd_k)$$

  PS:上面的$st$和$sd$是前缀和。

然后就可以愉快的$dp$了~~

1. $Task$ $6$：样例也太弱了，我写了一个全裸的$Kruskal$还过了，于是我就$dp[l][k-1]$、$k$、$dp[k+1][r]$没有管。。。。。这题可以先选择那一条边用李牌，然后再$Kruskal$一遍，这样试能拿45分？！正解是先$Kruskal$，然后枚举每一条边，看看是否替换成李牌使整体更优。数据说明说有两个点是只用王牌无法联通这个图，但是我们一样可以进行$Kruskal$，把没有连接的边设为$INF$就可以了，这样又可以顺利进行上面的替换比对。

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/25/
最后修改时间：2020-04-13 11:15:37
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！