2014-09-17阅读(4763)评论(5)

在工程中遇到这么一个问题，有两个升序集合A和B，a是A中的元素，b是B中的元素，希望求解a与b之差绝对值(abs(a-b))的最小值。 二分 朴素算法复杂度是O(n*n)，二分算法O(n*logn)，又因为两个集合都是升序的，所以可以优化到...

2014-09-15阅读(4629)评论(0)

POJ 2836 Rectangular Covering 铺地板：坐标平面上有n各点，用任意大小（非零）的地板砖覆盖它们，求最省的地板砖总面积。 3.4熟练掌握动态规划 状态压缩DP 先预处理数据，将n个点两两组合形成n * (n-1) ...

2014-09-14阅读(5904)评论(0)

POJ 3254 Corn Fields 种玉米：农夫约翰有n*m块地，其中一些地荒掉了。玉米是一种傲娇的植物，种在相邻的地里会导致不孕不育。求所有种法数对100000000求余。 3.4熟练掌握动态规划 状态压缩DP 今天换了CLion，...

2014-08-06阅读(5247)评论(0)

POJ 2441 Arrange the Bulls 公牛队：农夫约翰有N支公牛队，分别独占M个球场中的若干个，求分配方案的个数？ 3.4熟练掌握动态规划 状态压缩DP 白天写代码混饭，晚上写代码寻欢。 基本上是个带记忆的枚举，难点在对集合...

2014-08-03阅读(5011)评论(0)

UVa 11990 Inversion 逆序对：从一个长N的序列中逐渐移除M个数，求每次移除前序列的逆序对的个数？ 3.3活用各种数据结构 线段树和平方分割 如果将第i个数映射到点(i,X_i)的话，那么这个点左上和右下的点的个数之和就是逆...

2014-08-03阅读(4966)评论(3)

POJ 1201 Intervals 乞巧：从一系列区间[a_i,b_i]中至少取出c_i个数构成集合s，求s的最小size？ 3.3活用各种数据结构 线段树和平方分割 呵呵，白天睡了一天，晚上吃完翔后怎么也睡不着，爬起来再A一题吧。 这题...

2014-08-02阅读(5123)评论(0)

POJ 3470 Walls 傻鸟：在二维平面上有N堵水平或垂直的墙，放M只傻鸟，每只傻鸟会撞死在最近的那堵墙上。求最后每堵墙上有多少团血肉模糊的尸体！ 3.3活用各种数据结构 线段树和平方分割 中国人出的题目就是这么和谐，不过难度还是有的...

2014-07-28阅读(5025)评论(0)

  POJ 3368 Frequent values 最频繁的数：给定一个非严格单调增数列，请快速求解一个区间内出现最频繁的数的频次。 3.3活用各种数据结构 线段树和平方分割 采用线段树充分利用中间计算结果，定义区间的最大长度为...

2014-07-23阅读(5286)评论(1)

POJ 3264 Balanced Lineup 岳父与小明：农夫约翰有N头牛排成一列，他从第A头牛到第B头牛里挑出最高的那头取名叫岳父，最矮的那头取名叫小明。求岳父与小明的身高差？ 3.3活用各种数据结构 线段树和平方分割 平方分割我觉得...

2014-07-08阅读(5530)评论(3)

POJ 2886 Who Gets the Most Candies? 抢糖：N个熊孩子围成一个圈，从第K个开始淘汰，每淘汰一个，出示手中的数字，决定下一个淘汰者，正数表示左手第n个，负数反之。每个人可以拿到的存活回数的因数个数的糖果，求拿...