![](/images/cppblog_com/menjitianya/ulm1998.png)
A. Artificial Intelligence?
PKU 2256 http://poj.org/problem?id=2256
题意:功率的计算公式为P = UI,给定一句话,这句话中一定会包含三个变量中的两个,求另外一个,并且单位会有三种前缀m(毫),k(千),M(兆)。
题解:字符串扫描。
gets读入字符串,进行一次遍历,查找是否包含子串’P=’, ‘U=’, ‘I=’, 格式化它后面的数字,需要用double来存,然后检查单位前缀,m需要将原值除上103,k需要将原值乘上103,M需要将原值常上106。然后分三种情况计算未知的那个值即可。
B. Balancing Bank Accounts
PKU 2257 http://poj.org/problem?id=2257
题意:给定N(N <= 20)个人,以及M(M <= 1000)条关系,每条关系的描述为nameA nameB C,表示nameA这个人给了nameB这个人C块钱,为了让所有人都不亏,需要再给出至多N-1条关系,使得所有人都收支平衡。
题解:贪心。
首先将所有人分成两堆,from_set表示收入大于支出的人的集合,to_set表示支出大于收入的人的集合,并且记录他们各自的 |收入-支出|,然后对于所有的from_set的人按 |收入-支出| 进行递增排序,枚举每个from_set中的人f,去to_set中找到一个人t,满足f剩余的钱小于等于t亏损的钱,并且t是to_set中亏损最少的人,如果找不到这样的人,那么找到亏损最多的那个人,将f的钱给t,循环往复,直到f的钱给完为止。
当from_set中的所有人将钱全部给了to_set中的人后,to_set中也就没有人亏损了,所有人达到收支平衡。
C. The Settlers of Catan
PKU 2258 http://poj.org/problem?id=2258
题意:给定一个N(N <= 25)个点,M(M <= 25)条边的图,求图的最长路,点允许重复,边不允许重复。
题解:前向星 + dfs。
利用前向星存双向边,以每个点为起点深搜遍历整个图,访问过的边哈希,搜索过程更新最长路即可。
D. Team Queue
PKU 2259 http://poj.org/problem?id=2259
题意:Team Queue是这样一种queue,每个元素都有一个Team。
对于queue的push操作,被push的元素从queue中从头到尾扫描,如果扫到一个元素和它属于同一个Team,那么直接将它插入到这个元素后面;如果没有扫到,直接插到对列尾。
对于queue的pop操作,等同于普通queue的pop操作。
队伍数N小于等于1000。
题解:模拟,开1000个队列。
对于插入操作,每个Team的元素插入到对应的队列中,并且记录当前Team的最早插入时间。O(1)
对于弹出操作,枚举所有Team的队列首元素,从中找时间最早的,然后对那个队列执行弹出操作。O(N)。
E. Error Correction
PKU 2260 http://poj.org/problem?id=2260
题意:给定N*N(N < 100)的01矩阵,问是否所有 行和 和 列和 都是偶数,如果是输出OK,如果不是,是否能够通过改变一个值保证 都是偶数, 都不行输出Corrupt。
题解:扫描。
扫描所有 行和 和 列和,如果正好有其中一行R是奇数,并且其中一列C是奇数,那么改变(R, C)的值就能保证全是偶数,否则要么是OK,要么是Corrupt。
F. France '98
PKU 2261 http://poj.org/problem?id=2261
题意:给定16个国家进行淘汰赛,以及一个16*16的矩阵A,其中A[i][j]表示i号国家打败j号国家的概率,问每个国家取得冠军的概率。
题解:动态规划。
dp[0][i] 表示 1/2决赛 第i个人获胜的概率
dp[1][i] 表示 1/4决赛 第i个人获胜的概率
dp[2][i] 表示 1/8决赛 第i个人获胜的概率
dp[3][i] 表示 总决赛 第i个人获胜的概率
1) 那么显然dp[0][i] = A[i][i^1]
2) dp[1][i]的概率取决于1/2决赛时第i个人获胜的概率乘上他打败1/4决赛中同组的那两个人的概率;
3) dp[2][i]的概率取决于1/4决赛时第i个人获胜的概率乘上他打败1/8决赛中同组的那四个人的概率;
4) dp[3][i]的概率取决于1/8决赛时第i个人获胜的概率乘上他打败 总决赛中同组的那八个人的概率;
直接递推求解,dp[3][i]就是所求。
G. Goldbach's Conjecture
PKU 2262 http://poj.org/problem?id=2262
题意:将一个数分解成两个奇素数的和。
题解:素数筛选,枚举。
H. Heavy Cargo
PKU 2263 http://poj.org/problem?id=2263
题意:给定一个有向图,边权W(u, v)表示从u到v的最大载重为W(u, v),在给定s和t,求s到t 的最大可能载重。
题解:二分答案 + 判断连通性。
二分枚举答案T,然后从起点到终点进行连通性判定,如果边权小于T的边不可达,二分的最大值就是答案。