HDU 5884 Sort (二分+队列)

HDU 5884 Sort (二分+队列)

题目链接:点我~~ 题意:n个有序序列的归并排序.每次可以选择不超过k个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问k最小是多少。 思路:先对所有数排序,另外一个队列维护合并后的值,取值时从两个序列前端取小的即可。如果(n−1)mod(k−1)≠0,要把最小的(n−1)%(k−1)+1个数先合并一下。剩下的恰好可以每次合并k个数 ...
09月18日 239
HDU 5754 Life Winner Bo (博弈)

HDU 5754 Life Winner Bo (博弈)

题目链接:点我~~ 题意:~~ 思路: 我们依次分析每一种棋子。 ①王。 首先注意一个3*3的棋盘,开始在(1,1),问走到(3,3)谁有必胜策略。 穷举所有情况,容易发现这是后手赢。 对于N和M更大的情况,我们把横坐标每隔3、纵坐标每隔3的点都画出来,这些点都是符合后手胜的。 (因为无论先手怎么移动,后手都能重新移动到这些格子,直到到了终点) 如果初始点不...
07月26日 303
HDU 5762 Teacher Bo (鸽笼原理)

HDU 5762 Teacher Bo (鸽笼原理)

题目链接:点我~~ 题意:~~ 思路:考虑一种暴力,每次枚举两两点对之间的曼哈顿距离,并开一个桶记录每种距离是否出现过,如果某次枚举出现了以前出现的距离就输 YES,否则就输 NO . 注意到曼哈顿距离只有 O(M) 种,根据鸽笼原理,上面的算法在 O(M)步之内一定会停止.所以是可以过得. 一组数据的时间复杂度 O(min{N^2,M}) . ...
07月26日 237
HDU 5726 GCD (RMQ+二分)

HDU 5726 GCD (RMQ+二分)

题目链接:点我~~ 题意:给你n个数,m个询问,每次询问某个区间,求这段区间所有数的gcd,然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~ 思路:对于求区间gcd可以用线段树维护,或者RMQ,因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd,考虑枚举左端点,二分区间进行预处理~例如12467,以1为左端点,1~5为右端点5个...
07月20日 253
显示更多
  1. .01
  2. .02