
POJ 3368 Frequent values 题解 《挑战程序设计竞赛》
POJ 3368 Frequent values 最频繁的数:给定一个非严格单调增数列,请快速求解一个区间内出现最频繁的数的频次。 3.3活用各种数据结构 线段树和平方分割 采用线段树充分利用中间计算结果,定义区间的最大长度为...
POJ 3368 Frequent values 最频繁的数:给定一个非严格单调增数列,请快速求解一个区间内出现最频繁的数的频次。 3.3活用各种数据结构 线段树和平方分割 采用线段树充分利用中间计算结果,定义区间的最大长度为...
POJ 3264 Balanced Lineup 岳父与小明:农夫约翰有N头牛排成一列,他从第A头牛到第B头牛里挑出最高的那头取名叫岳父,最矮的那头取名叫小明。求岳父与小明的身高差? 3.3活用各种数据结构 线段树和平方分割 平方分割我觉得...
POJ 2886 Who Gets the Most Candies? 抢糖:N个熊孩子围成一个圈,从第K个开始淘汰,每淘汰一个,出示手中的数字,决定下一个淘汰者,正数表示左手第n个,负数反之。每个人可以拿到的存活回数的因数个数的糖果,求拿...
POJ 2155 Matrix 矩阵:频繁翻转一个二进制矩阵,求任一点值。 3.3活用各种数据结构 Binary Indexed Tree 好久没刷题了,感觉智商跌了一半。这道题是二维的Range Sum Query,直接用二维的BIT太慢...
POJ 3109 Inner Vertices 黑白棋・改:无限大的棋盘上,在横向和纵向上被包围的白子会变成黑子,求最终黑子个数? 3.3活用各种数据结构 Binary Indexed Tree 首先需要了解一下扫描线算法,扫描线算法是计算...
POJ 1990 MooFest 奶牛节:N头奶牛每头耳背程度v,坐标x。两牛交流需要音量为distance * max(v(i),v(j)),求所有牛两两交流所需总和? 3.3活用各种数据结构 Binary Indexed Tr...
AOJ 0531 Paint Color 涂色:(日文题目,自己翻译成了中文)为了宣传信息竞赛,要在长方形的三合板上喷油漆来制作招牌。三合板上不需要涂色的部分预先贴好了护板。被护板隔开的区域要涂上不同的颜色,比如上图就应该涂上5种颜色。 请...
POJ 2549 Sumsets 子集:从S中找出子集{a,b,c,d}使得 a + b + c = d且d最大。 3.2常用技巧精选(一) 折半枚举 睡不着,A一题提提神。子集最多有1000C4*4个,时限只有一秒。折半枚举有些...
POJ 3977 Subset 子集:从N个数中挑出非空子集使得和的绝对值最小。 3.2常用技巧精选(一) 折半枚举 子集最多有(2^N)235个,根本枚举不过来。所以折半先枚举前半,记录和及个数。在枚举后半时,使用二分法查找与相反数最相近...
POJ 2674 Linear world 线性世界:一条线上N只蚂蚁,每只蚂蚁速度固定,方向和坐标不同,碰头后掉头,求最后掉下去那只蚂蚁的名字。 3.2常用技巧精选(一) 弹性碰撞 首先想象整个世界只有一只蚂蚁,于是可以计算出爬行时间最长...