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阅读(2980)评论(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找出游戏的必胜策略&...

2016-08-09阅读(3665)评论(1)

Codeforces 138D World of Darkraft  暗黑世界：H*W的棋盘中每个点都是L、R、X三者之一，两人轮流选一个点，若为L则向左下和右上发射激光，R向右下和左上发射，X则相当于LR的组合——同时向四个方向...

2016-05-30阅读(4433)评论(0)

POJ 3537 Crosses and Crosses  画叉叉：两人在1*N的格子纸上轮流打叉，最先打出连续3个叉者获胜，问必胜者是谁？ 4.2找出游戏的必胜策略  Nim与Grundy数 任何玩家在位置i处打叉后，...