【水题合集】2.20考试

寒假最后一场考试

认真做了一下居然AK了233

1.题目一

一开始没想到删除怎么搞。。于是写了个配对堆

每次把那个点所在堆分出来pop掉那个点再merge回去 logn

后来听说可以先打个标记之后遇到再删。。于是立即改掉了

然后发现如果交那个配对堆的程序会WA四个点。。【现在改好了

【正常解法】

【配对堆】

2.题目二

一个贪心。。全部翻转到一边就行了

因为找不到反例所以是对的233

【还是给个证明吧

假设我们先把所有点翻到一边 得到一个矩阵
那么若将某个点翻过去后周长变短则它一定在边界上,否则周长只增不减
第二就是这个点不能在靠近y=x直线的两条边(也就是右边和底边)上,否则也是只增不减
假设要翻转的点是矩阵的左上角。。此时高和宽都会先减少肯定比翻转边上的点更优。。
再考虑极限情况,翻转后的矩形的左上角为原矩形的右下角。。这样肯定也是最优的
那么就显而易见了,当且仅当矩阵右下角的点在y=x上时新矩阵与原矩阵周长相等

最后就是这道题最坑的一个地方就是所有的点都要开ll

于是除了我全场爆0 hhhhhh

3.题目三

这题是蒯的立方体大作战啊。。我讲课的时候还讲过

然后陈江伦徐子犇邓杰都爆0也是醉

树状数组解决

4.题目四

这道题以前也做过

去年10.25。。YMD的题 一个dp解决

不过那个简单些因为是对10000取模。。

这道题要写个高精度。。然后压个位。。

【写这道题还发现压位的高精度不能直接输出 否则有可能出现某几位开头是0 压位后0不输出。。解决方法详见代码

说点什么

2 评论 在 "【水题合集】2.20考试"

提醒
排序:   最新 | 最旧 | 得票最多
游客

Orz

wpDiscuz