ICPC World Finals-2010

看了看WF 2010的题目。。发现好难啊天哪。。我真是太弱菜啦悲剧。。。
Problem A:
烦的跟鬼一样的模拟题,而且情况很多。。我好不容易搞懂了题目已经半疯了。。

Problem C:
离散化一下。。然后倒过来求出能到达终点的面积就OK了。。

Problem E:
这到题是裸的带连通性的状态压缩问题啊,直接上状态压缩Dp。。为了重建路径干脆把路径保存在状态里面好了。反正空间够的。。

Problem G:
还算简单的动归题。。。

Problem I:
有点意思饿。。就是一个n*m的图,给你三个点以及它们必须在那个次序到达,让你统计满足这个条件的从左上角到左下角的路径数。。说白了还是带连通性的状态压缩问题。。关键是要记录一些附加的量,然后转移的时候小心一点就可以了。。。

Problem J:
这道题说的是给你一个X*Y的矩阵,然后让你用切割的办法(每次必须一刀或横或竖切成两块)分成N块,面积分别为你的N个朋友的要求面积。。
1<=X,Y<=100,N<=15。。很显然要Dp。。状态就是当前矩形的长宽,还有当前矩形要切出的子集。。但是这样的话状态会很多。。实际上不多,因为当前矩形的面积一定等于当前子集的和。所以开个Map保存所有状态就OK了。。

3 thoughts on “ICPC World Finals-2010

Leave a 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>