(联考)noip90

本文主要是介绍(联考)noip90，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1

sbdp

设 \(dp_{i,j,k,l}\) 表示矩形左上角为 \((i,j)\) ，右下角坐标为 \((k,l)\) ，往外扩展转移即可，暴力做是 \(O(n^{4})\) 的。

发现只有 \(i+j+k+l=n+m+2\) 才有用，于是可以去掉第四维，\(O(n^3)\) 。

T2

阅读完它写的_垃圾程序后就能发现，排序就是把后边所有比当前数小的都挪到当前数的前面，如果是nan则不去后边找。

模拟上述过程即可，将所有非nan的数预先排序就可以做到 \(O(n\log{n})\) 。

T3

44pts：_傻瓜背包。

44+8pts：判掉 \(n=m\) 的。

100pts：

如果 \(n\) 为奇数，则加一个0到这个序列中，方便处理。

将 \(a_{i}\) 排序，求个差分数组 \(d_{i}=a_{2i}-a_{2i-1}\) 。

再求个 \(sum=\sum_{i}d_{i}\) ，此时的 \(sum\) 表示的便是离0差了多少。

将 \(d_{i}\) 从大到小排序，如果交换一个 \(d_{i}\) 对应的 \(a_{2i},a_{2i-1}\) ，那么 \(d_{i}\gets -d_{i}\) ，于是 \(sum\gets sum-2d_{i}\)（后边的 \(d_{i}\) 是没交换之前的 \(d_{i}\) ）。

所以扫一遍排完序的 \(d_{i}\) ，能减就减，可以证明这么做一定将 \(sum\) 消到0。

证明？推小马的blog。

T4

48pts：按照题目说的用类似线段树的形式来写。

100pts：

不会，待填，咕。

这篇关于(联考)noip90的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！