POJ-2240 解题报告

题意简述

输入货币名称以及货币间的汇率(A到B的汇率可能与B到A的不同),判断是否有可能实现套汇(即从某指定货币开始,通过一系列的货币兑换操作,最终换回某货币并实现盈利)。

问题有多组数据,对于每组数据,第一行代表货币类别数量,第二行起的n行为各货币名称;接下来一行是允许的兑换方式总数,而后每行有三个部分,第一个和第三个分别是原始货币和兑换后货币的名称,第二个是汇率。数据的输入以0结束。

对于每组数据,输出是否可能实现套汇(YES或NO)。 Continue reading “POJ-2240 解题报告”

POJ-1125 解题报告

题意简述

股票经纪人之间的关系形成了一个有向关系网。每个股票经纪人向与他关联的另一个人传递一条谣言需要花费的时间各不相同。A向B传播谣言耗时并不一定等于B向A传播耗时。某经纪人收到谣言后会同时开始向他所有关联的经纪人传播谣言。给定股票经纪人之间的关系网以及每个经纪人向特定经纪人传播消息的耗时,问谣言从哪个股票经纪人开始传播能最快的使整个网所有人知道该谣言,并输出最短耗时。如果存在某经纪人无论如何无法得知该谣言,输出disjoint。

Continue reading “POJ-1125 解题报告”

POJ-1062 解题报告

题意简述

你想娶酋长的女儿,但酋长要求你给一定数额金钱的聘礼。除了金钱外,酋长也允许你用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。部落里的每个人有一个等级。你的整个交易过程涉及的人的等级只能在一个限定的差值内。问你最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。

例:

最高最低等级差不超过1,共4个物品

酋长的女儿    等级3     要求现金10000元     或甲的物品+8000元     或乙的物品+5000元

甲的物品        等级2     要求现金1000元        或丙的物品+200元

乙的物品        等级2     要求现金3000元        或丙的物品+200元

丙的物品        等级2      要求现金50元

在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。

Continue reading “POJ-1062 解题报告”

POJ-2253 解题报告

题意简述

湖中有N(2<=N<=200)块石头,标号从1到N。青蛙1在石头1上,青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2,它可以经由任意石头组成的路径。在所有可能路径中找出一条路径,使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为,点1与点2间存在若干条路径,每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

Continue reading “POJ-2253 解题报告”

POJ-1860 解题报告

题意简述

某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。 Continue reading “POJ-1860 解题报告”

POJ-3259 解题报告

题意简述

农夫共有F(1≤F≤5)个农场,每个农场有N块田(1 ≤ N ≤ 500)和M条普通无向路(1 ≤ M ≤ 2500),走过这些路需要一定时间。同时还存在W条有向虫洞(1 ≤ W ≤ 200),走这些虫洞可倒流一定时间。问对于各个农场,农夫是否有可能从某点出发,回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES,否则为NO。 Continue reading “POJ-3259 解题报告”

POJ-2996 解题报告

题意简述

将一个棋盘翻译为文字表达。如下:

大写字母表示白方,小写表示黑方。输出时按照KQRBNP的顺序;棋盘格子编号的表示:从下往上是1~8,从左往右是a~h。
遇到相同棋子,白方表示时按从下往上从左往右的顺序,黑方按从上往下从左往右的顺序。
输出格式:

White: Ke1,Qd1,Ra1,Rh1,Bc1,Bf1,Nb1,a2,c2,d2,f2,g2,h2,a3,e4
Black: Ke8,Qd8,Ra8,Rh8,Bc8,Ng8,Nc6,a7,b7,c7,d7,e7,f7,h7,h6

Continue reading “POJ-2996 解题报告”