5.18 的比赛,热热还能吃。
内容概括:
在决赛的时候,我们的和蔼可亲的,认真负责的老师给我们出了这样四道题目(全是原),具体如下:
- 输入输出+基本表达式模板
- bfs 板子
- 石子合并 (n<=2000)
- __int128 的使用。
注意到石子合并的一般做法是 n3 的dp,而优化到n2需要四边形不等式优化。而剩下的题目均在橙一下。。。
我们知道,石子合并有一个非常经典的假贪心,就是每次选合并代价最少的两堆进行合并,暴力找的话是n2的,但是很好卡。
于是我1000一下dp,以上贪心,然后过了。
重庆市科学素养大赛是这样的,选手只需要做题就好了,而出题人要考虑的事情就多了。
主要谴责的就是全是原全简单但是放个T3防AK数据还烂,烂到这么经典的贪心都没卡。