NOIP2018简要题解

PJ

标题统计

按照题意模拟即可。

龙虎斗

枚举即可。记得开 $\texttt{long long}$ 。

摆渡车

设 $f[i]$ 表示前 $i$ 时刻的答案,容易得到 $\displaystyle f[i]=\min_{j\leq i-m}\{f[j]+\sum_{j<k\leq i}i-t_k\}$ 。直接前缀和优化即可得到 $50$ 分。

考虑优化。可以发现 $j$ 只需要从 $i-2m+1$ 开始枚举即可。于是可以得到 $70\sim 100$ 分。

注意到可能会有 $(i-m,i]$ 中没有人的情况,此时直接 $f[i]=f[i-m]$ 即可。这样子就有 $100$ 分了。

代码

对称二叉树

暴力比较即可。加上 $sz$ 的剪枝后复杂度是正确的。

代码

TG

铺设道路

原题不讲了

货币系统

戳这里

赛道修建

先考虑一些有启发性的 SubTask :

  • 链:直接二分答案,然后扫一遍 check 即可。
  • 菊花:把所有边记下来排序,答案为 $\min\{w_i+w_{2m-i}\}$ 。
  • 二叉树:二分答案,如果某个分支长度 $\geq mid$ 就直接作为一条赛道,否则考虑把两个分支拼起来,如果拼不起来就往上传。

那么正解就很简单了。所有传上来的长度可以分成两种:$l\geq mid$ 和 $l_1+l_2\geq mid$ 。

第一种直接作为一条赛道即可,第二种就对于每个最小的元素 $x$ 找到一个最小的 $\geq mid-x$ 的元素,然后一起删去。

然后如果有剩下的值就把最大的那个往上传即可。

感觉正确性还是很显然的...如果没有看懂可以康康代码。

代码

旅行

树的情况很简单,dfs 的时候优先走编号小的点即可。

基环树就枚举断掉哪条边就好了。

代码

填数游戏

这种题真的不知道该说什么好...

系数的推导过程留给读者作为练习

代码

保卫王国

戳这里

最后修改:2019 年 09 月 27 日 01 : 08 PM

6 条评论

  1. xgzc

    M_sea AK NOIP2019

    1. smy
      @xgzc

      这么显然的事情还用说出来?

      1. M_sea
        @smy

        您们怎么一起嘲讽我啊

    2. M_sea
      @xgzc

      那是您

  2. Siyuan

    M_sea AK NOIP 2018!

    1. M_sea
      @Siyuan

      假人 dsy 怎么又来嘲讽我这种小菜鸡了啊 /kel

发表评论