Archive for 四月 5th, 2008
Posted on 四月 5th, 2008.
这道困扰了我许久的题目,终于被我过掉了…
话说当时觉得这道题太难写,于是一直没敢写…然后呢,现在Splay写熟悉了,正好FNOI做这道题,于是咬咬牙开始写.这个东西的调试实在是太恶心人了,不过还好,在用尽方法把file of integer转成text之后,终于能调试了…
写错了两个地方,一个是如果刚插入一个人有x个果冻,而要吃掉的那包也有x个果冻,这是我会把刚插入的那个人的果冻吃掉…加了个小判断搞掉.第二个是,friendID变量用重了…把一些改成了friendID_,过掉~
程序写的不是太恶心.用object写的,然后速度有些慢.于是删了object,加上inline,速度快了些.偶然删去了inline,速度竟然更快!想起了HopCroft那个问题…现在还不知道怎么回事,等着周源来问他…
{
生日快乐; happybirthday; NOI 2006
- sqybi’s code
- Splay
}
//for my winsty
program happybirthday_sqybi;
uses
happybirthday_p;
const
nn = 500000;
type
link = ^obj1;
obj1 = record
v: longint;
[…]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 5th, 2008.
这道题算是十分经典的二分答案+二分图匹配了(怎么都是二分=.=…).
第一行读入一个n,后面n行每行n个数.要求选出n个数,任意两个不在同一行同一列,使它们的最大值最小.可能有经验的OIer看到”最大值最小”就知道了,这道题是二分答案.首先二分最大值x,然后对于所有最大值小于等于x的数在二分图里建边(这里把行和列看做二分图的两组结点,不用特意建边,只要判断一下就可以).接下来就是Hungary了.
刚开始写的有问题的一点是,没有看到二分时会有负数.后来更改之后AC.总体来说是比较简单的题目.P.S.Hungary练习的差不多了,准备开始写KM.另外开始用017899这个SGU的ID…有兴趣的去看看Information~
{Unstable Systems; sgu 218- sqybi’s code- 二分答案+Hungary}//for my winstyprogram sgu218_sqybi; const nn = 500;
var a: array[1..nn, 1..nn]of longint; match: array[1..2, 1..nn]of longint; visit: array[1..nn]of boolean; n, i, j, l, r, mid: longint;
function search(x, y: longint): boolean; var i, t1, t2: longint; begin search := false; if visit[x] then exit; visit[x] := […]
Read Full Post |
Make a Comment ( None so far )