2014-07-05阅读(5523)评论(2)

POJ 2155 Matrix 矩阵：频繁翻转一个二进制矩阵，求任一点值。 3.3活用各种数据结构 Binary Indexed Tree 好久没刷题了，感觉智商跌了一半。这道题是二维的Range Sum Query，直接用二维的BIT太慢...

2014-06-08阅读(6576)评论(3)

POJ 3109 Inner Vertices 黑白棋・改：无限大的棋盘上，在横向和纵向上被包围的白子会变成黑子，求最终黑子个数？ 3.3活用各种数据结构 Binary Indexed Tree 首先需要了解一下扫描线算法，扫描线算法是计算...

2014-06-05阅读(5621)评论(1)

POJ 1990 MooFest 奶牛节：N头奶牛每头耳背程度v，坐标x。两牛交流需要音量为distance * max(v(i),v(j))，求所有牛两两交流所需总和？ 3.3活用各种数据结构 Binary Indexed Tr...

2014-05-22阅读(6000)评论(3)

AOJ 0531 Paint Color 涂色：（日文题目，自己翻译成了中文）为了宣传信息竞赛，要在长方形的三合板上喷油漆来制作招牌。三合板上不需要涂色的部分预先贴好了护板。被护板隔开的区域要涂上不同的颜色，比如上图就应该涂上5种颜色。 请...

2014-05-22阅读(8508)评论(12)

在解AOJ 0531 Paint Color时，学到了一个累积和的妙用——imos法，由于原文是日语，所以特意翻译过来。值得一提的是，作者Kentaro Imajo跟鄙人同龄，却已取得如此多的成就，而鄙人一无所成，实在汗颜。 imos法 i...

2014-05-22阅读(5619)评论(0)

POJ 2549 Sumsets 子集：从S中找出子集{a,b,c,d}使得 a + b + c = d且d最大。 3.2常用技巧精选（一） 折半枚举 睡不着，A一题提提神。子集最多有1000C4*4个，时限只有一秒。折半枚举有些...

2014-05-20阅读(5115)评论(0)

POJ 3977 Subset 子集：从N个数中挑出非空子集使得和的绝对值最小。 3.2常用技巧精选（一） 折半枚举 子集最多有(2^N)235个，根本枚举不过来。所以折半先枚举前半，记录和及个数。在枚举后半时，使用二分法查找与相反数最相近...

2014-05-20阅读(4886)评论(2)

POJ 2674 Linear world 线性世界：一条线上N只蚂蚁，每只蚂蚁速度固定，方向和坐标不同，碰头后掉头，求最后掉下去那只蚂蚁的名字。 3.2常用技巧精选（一） 弹性碰撞 首先想象整个世界只有一只蚂蚁，于是可以计算出爬行时间最长...

2014-05-18阅读(5403)评论(1)

POJ 1222 Extended Lights Out 灭灯：有6 * 5的灯，一把下去可能关掉或点亮上下左右中5个灯，希望灭掉所有的灯，求灭灯方案。 3.2常用技巧精选（一） 反转 枚举第一行是否需要按开关就行了，第一行固定了的话，第二...

2014-05-16阅读(4303)评论(0)

POJ 3185 The Water Bowls 翻盖有奖：将一列碗翻成口朝上，一把下去可能同时反转3个或2个（首尾），求最小翻转次数。 3.2常用技巧精选（一） 反转 似乎穷举也能过，不过太蠢了。反转法只需枚举2次，分别是从第一个开始翻和...