2019.4.7高中部集训

课程表

上午
  • 讲评考试、$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$:
    1
    2
    3
    4
    5
    6
    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$,完成栈上面的产品的时间和乘以惩罚值即可。

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

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

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×