最近打的几场比赛。。。

上周参加了SRM 613。。。

250和500都很简单。。。但是900感觉可以说是一道还不错的题目。。

题目大意是给你一个n*m的borad,要你在上面放一些棋子,每列最多一个,并且第i行的前L[i]个和后R[i]中都要各有正好一个,并且满足L[i]+R[i]<=m。

当时我不怎么会做。。。第二天灵光一闪反而想明白了:

首先注意到我们可以交换两行的L[i]或R[i]值而不影响结果。

第一眼的想法往往是按L[i]从小到大排序,然后一个个放,那么第一个思路就是L[i] R[i]都从小到大排序然后dp。但是这样的到后面可能会有L[i]+R[i]>m,重叠了就没法做了。

仔细想想我们还有另一个dp方法,把L[i]从大到小排序然后从少的那一列往多的那一列放。这样需要记录还有几个行没有放棋子。

那么考虑整个问题,实际上我们L[i]从小到大,R[i]从大到小排序然后两个dp一起跑,既记录L[i]这边这行还有几个列能用,又记录R[i]那一边有几个行没有放旗子。然后就能解决这个问题了。。。

因为有事情没打CF 238。。。后面补了一下。。。

卧槽。。。这哪是2个2000啊。。。我觉得这题目难度只有500 500 1000 1000 1500好吗。。。

A还有点意思。。。注意到mod 2下只有对角线有意义。

C 直接dfs暴力构造,注意到无向图上dfs树上所有边都是回边的性质是很好做的。。。

D不说啥了>_>。。。。

E。。。。不说啥了。。。>_>。。。。

 

4 thoughts on “最近打的几场比赛。。。

Leave a Reply to Jecvay Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>