随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Ulm local 1998 解题报告

 

 


AArtificial 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的边不可达,二分的最大值就是答案。

 

posted on 2014-07-19 22:42 英雄哪里出来 阅读(1023) 评论(0)  编辑 收藏 引用 所属分类: 区域赛 解题报告


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理