SRM 477

我震惊了。。

显然这次人品爆发的有点厉害。。话说每次我SRM的时候人品总会很好。。。这次好到了令人发指的程度。。。。
Problem 250 显然是水题,表示忽略。。
Problem 500 就是给你一堆数,每两个平方和是平方数的数能凑成一对,最对凑出几对?
我毫无思路。其实这个图是二分图那么就很显然了。。但很悲剧的是当时我想不出这个。。。。由于我信春哥。。我正好做过Ural 1099。。。于是写了个随机化交了。。居然过了。。
恩。。写个是二分图的证明吧。。
由于对两个数x,y来说,gcd(x,y)=1,所以不能都是偶数,同时一个数平方mod4只能是0或1.。显然如果两个都是1就不对了。。。所以只能一个是0一个是1,那么按平方mod4的余数分成两部分就可以了。。
Problem 1000 这题显然是APIO-2010巡逻那题的一个变种。。。所以同样算法可以无压力AC。。好像不能用O(n)的那个找直径的算法。。所以我写了个n^2的。。一开始写了个n^3的。。发现会TLE只好resubmit。。。
额。。差5分就可以变红了。。看来注定是个悲剧啊。。下次肯定没这么好RP就要掉Rating了。。。

3 thoughts on “SRM 477

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>