重庆市科学素养大赛有没有树枝
  • 板块灌水区
  • 楼主_determination_
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/6/29 21:34
  • 上次更新2024/6/30 09:03:14
查看原帖
重庆市科学素养大赛有没有树枝
530468
_determination_楼主2024/6/29 21:34

5.18 的比赛,热热还能吃。

内容概括:

在决赛的时候,我们的和蔼可亲的,认真负责的老师给我们出了这样四道题目(全是原),具体如下:

  1. 输入输出+基本表达式模板
  2. bfs 板子
  3. 石子合并 (n<=2000)
  4. __int128 的使用。

注意到石子合并的一般做法是 n3n^3 的dp,而优化到n2n^2需要四边形不等式优化。而剩下的题目均在橙一下。。。

我们知道,石子合并有一个非常经典的假贪心,就是每次选合并代价最少的两堆进行合并,暴力找的话是n2n^2的,但是很好卡。

于是我1000一下dp,以上贪心,然后过了。

重庆市科学素养大赛是这样的,选手只需要做题就好了,而出题人要考虑的事情就多了。

主要谴责的就是全是原全简单但是放个T3防AK数据还烂,烂到这么经典的贪心都没卡。

2024/6/29 21:34
加载中...