2017年01月的文章

2017-01-20阅读(2645)评论(0)

AOJ 1070 FIMO sequence  FIMO序列：对空序列执行如下十种操作： 0、将x插入序列尾部，同一个x只出现一次 1、删除中点元素并输出该元素 2、输出前半段的最小元素 3、输出后半段的最小元素 4、假设重复2和...

2017-01-19阅读(2834)评论(0)

POJ 1180 Batch Scheduling  批任务调度：N个顺序任务，分别耗时Ti，权重Fi。 若批处理，每批任务耗时S+Ti之和，同批次任务视作同时完成。总耗时等于每个任务完成的时刻乘以其权重，求最少耗时？ 4.4常用...

2017-01-16阅读(3545)评论(0)

POJ 3260 The Fewest Coins  最小货币流通：用面值Vi，个数Ci的硬币购买价格T的商品，假设商店每种面值的硬币都有无限个，求最小货币流通量。 4.4常用技巧精选（二）  双端队列  流通...

2017-01-15阅读(2901)评论(0)

POJ 2823 Sliding Window  滑动最大小最值：给定长度为n的数组，求长度为k的滑动窗口内的最大最小值。 4.4常用技巧精选（二）  双端队列  没什么好说的，把书上的模板简单拓展一下就行了：...

2017-01-14阅读(2817)评论(0)

POJ 3494 Largest Submatrix of All 1’s  最大子矩阵：给定M*N的01矩阵，求元素最多且都是1的子矩阵。 4.4常用技巧精选（二）  栈  还是先来跟书上的例题做个对比，借鉴...

2017-01-13阅读(3677)评论(0)

POJ 2082 Terrible Sets  最大矩形：柱状图是由一些宽度相等的长方形下端对齐后横向排列得到的图形。现在有由n个宽度分别为wi，高度分别为hi的长方形从左到右依次排列组成的柱状图。问里面包含的长方形的最大面积是多...

2017-01-12阅读(3371)评论(0)

POJ 3250 Bad Hair Day  洗剪吹：N个人排队理发，每个人只能看到更矮的人的头，否则视线被挡住。给定他们的身高，求所有人能看到的人头之和。 4.4常用技巧精选（二）  栈  两种思路，第一种是...

2017-01-11阅读(3132)评论(0)

POJ 3728 The merchant  游吟商人：N个城市同种商品价格不同，任意两个城市间有且仅有一条简单路径。请快速计算商人在指定两点的路线上做一次买卖所能赚到的最大利润。 4.3成为图论大师之路  LCA 中国...

2017-01-10阅读(3367)评论(0)

POJ 1986 Distance Queries  LCA距离：快速查询树中任意两个节点间的最短距离。 4.3成为图论大师之路  LCA 也就是两个节点到最近公共祖先的距离之和，求出每个节点到根节点的距离之后，uv两点...

2017-01-06阅读(2976)评论(0)

POJ 2749 Building roads  阳关路与独木桥：有N个农场，其中A对相互讨厌，不能碰面；B对相互喜欢，必须碰面。给定两个中转站S1和S2、各个农场的坐标，让每个农场连接到其中一个中转站。求最小化任意两个农场通过中...