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

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

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

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

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

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

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

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

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

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

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

POJ 2723 Get Luffy Out  鸳鸯锁：你的基友路飞被关进了一座M层的监狱，每层的门上由两把锁锁住，打开任意一把即可入内。这些锁的钥匙一共有2N种，两两互斥，当使用了一把钥匙后，另一把与其互斥的钥匙就会消失，造成鸳...

2016-12-28阅读(3527)评论(0)

POJ 3678 Katu Puzzle  某组合电路有N个输入，M个与或异或门将其两两相连构成多个输出，问是否存在满足给定输出的输入。 4.3成为图论大师之路  2-SAT 每条边都是某个2输入门，最终输出为门的合取范...

2016-10-28阅读(3470)评论(0)

POJ 1236 Network of Schools  校园网：给定N所学校和网络，目标是分发软件其他学校都可收到，求①所需最少分发学校数；②若任选学校都能收到，最低新增边数。 4.3成为图论大师之路  强连通分量分解...

2016-10-28阅读(2870)评论(0)

POJ 3180 The Cow Prom  奶牛圆舞：N头牛，M条有向绳子，能组成几个歌舞团？要求顺时针逆时针都能带动舞团内所有牛。 4.3成为图论大师之路  强连通分量分解 睡不着，刷一题解解闷。 所谓能带动，就是舞...

2016-10-28阅读(3416)评论(0)

POJ 2315 Football Game  国足：两名球员轮流从N个球中挑出不多于M个射门，每个球半径都是R，离球门S。由于国脚技术高超，每次只能踢出L以内的距离。进最后一个球者胜，求谁有必胜策略？ 4.2找出游戏的必胜策略&...