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

South Central USA 2002 解题报告


A . The Hardest Problem Ever

       PKU 1298 http://poj.org/problem?id=1298

         题意:解码题,按照如下对应关系解码:

       密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
      
原文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 

       题解:简单题。

 

B. Polar Explorer

PKU 1299 http://poj.org/problem?id=1299

题意:给定圆的半径X,求圆周上两个点AB的距离,其中圆心角AOB的角度为Z(0 <= Z <= 360)

题解:核心是Z如果大于180,则Z = 360 - Z,即走劣弧。而且题目求的是来回一次,所以计算的时候弧长要乘2

 

C. Door Man

PKU 1300 http://poj.org/problem?id=1300

题意:给定一些边和起点s,求能否找到一条从s0的通路,并且要求访问所有的边。

题解:欧拉回路可行解判定。

首先利用flood fills遍历全图,如果0点没有被访问到则必定不存在;然后判断度数不为0的点是否有未被访问到的,如果有,说明图不连通,也必定不存在解;最后统计度数为奇数的点的个数P,以及具体的点:

1)  P = 0,则必定有解;

2)  P > 2,则无解;

3)  P =2, 那么有解的前提是两个奇度数点中一个是s,另一个是0;否则无解。

 

D . The Umbrella Problem 2054

PKU 1301 http://poj.org/problem?id=1301

题意:给定一个10X10的地图,玩家从第一行的某一个点出发,每一步行编号+1,列编号增量有三种选择(-1, 0, 1),图中标记为S(laser gun)的点不能走,并且S的点会发出镭射光,第0秒朝上发射,第1秒朝右,第2秒朝下,第3秒朝左,循环往复,发射长度一直到地图边缘。问能否走到最后一行标记为G(grass)的地方。

题解:广搜。

hash[4][R][C]表示状态,每走一步,利用步数 mod 4计算出镭射光的方向,然后将所有的镭射光可达区域全部标记出来,未标记的点为可达点,枚举三个方向进行搜索。

E. Blue Gene, Jr.

       PKU 1302 http://poj.org/problem?id=1302

       题意:一个长度为N(N <= 20)的病毒基因串A[1...N]进行变异,变异过程从左往右,分情况讨论:

       1) 如果第i个字符是 A-Z,则它将变异成数字n mod 10n表示A[i+1...N]中变异基因的数目;

       2) 如果第i个字符是 1-9,则它变异成A[i] - 1,并且如果第p (p = i + A[i])个基因存在的话,从第p个基因开始变异;否则从第i+1个基因开始变异;

       题解:题意理解后就是个水题了,递归求解。

 

F . Byte Me!

       PKU 1303 http://poj.org/problem?id=1303

       题意:二进制二十一点(二进制黑杰克)是由两种牌组成的游戏,一种称为bytes(一个8比特的序列表示0-255之间的数),一种称为nibbles((一个4比特的序列表示0-15之间的数),游戏玩法如下:

       1) 游戏的目标是获得尽量接近510分,并且不能超过它;

       2) 每个玩家有两张牌,一张面朝上,一张面朝下(庄家不知道是什么牌)

       3) 每个玩家有四次叫牌机会,可以叫bytes,也可以叫nibbles,但是如果分数超过510则不能再叫牌;

       4) 所有的叫牌都是面朝上的;

       5) 如果玩家分数超过510,立即判为输;

       5) 庄家最后一个叫牌;

       7) 平局的情况庄家胜(如果所有人都超过510分,庄家还是赢的)

      

庄家的规则如下:

       1) 当看到自己和其他人面朝上的牌,判断已经必胜时不要再叫牌了;

       2) 如果总分小于382 需要叫一次byte牌;

       3) 如果总分小于等于500 需要叫一次nibble牌;

 

还有两个隐藏规则:

       1) 你是庄家;

       2) 每个非庄家的玩家面朝下的牌是11111111(但是庄家不知道),面朝上的牌给定;

       3) 非庄家不会叫牌(因为他们比较笨)

      

       给定庄家的牌和其他玩家面朝上的牌,以及牌堆中的bytes牌和nibble牌,求庄家的四次叫牌能否获胜;

 

       题解:题目说了一大堆,最后非庄家的玩家都不会叫牌,o(╯□╰)o...所以只要根据庄家的规则进行叫牌,然后判断是否能够胜出即可;

       因为其他人都不叫牌,每个人都有两张牌,所以其他人的总分不可能超过510分,所以,如果庄家叫牌超过510分直接被判为负。

       每次叫牌前先判断所有玩家的朝上的卡片分数加上255和庄家当前得分进行比较,如果有一个玩家分数大于庄家分数,则庄家按照382500这两个区间进行叫牌。

       四次叫牌结束,如果所有玩家分数都小于等于庄家分数,则判断庄家分数是否大于510,如果是,输出Bust!,否则输出Win!;如果小于某个玩家的分数,那么输出Lose!

 

G . World's Worst Bus Schedule

       PKU 1304 http://poj.org/problem?id=1304

       题意:公交车站有N(N <= 20)辆车,每辆车的发车时间间隔为a1 a2 a3 a4... a1 a2 a3 a4... a1 a2 a3 a4...,循环发车,问某人在T时刻赶到公交车站,最少需要等待多少时间能够乘上公交车。

       题解:对于每辆公交车,设它的所有时间间隔之和为S,令T' = T mod S,然后枚举所有的发车间隔,前i个发车间隔a[i]之和减去T'中的最小正值就是等这辆公交车需要的时间,取所有公交车的最小时间就是所求。

 

posted on 2014-07-31 11:31 英雄哪里出来 阅读(1129) 评论(1)  编辑 收藏 引用 所属分类: 区域赛 解题报告

评论

# re: South Central USA 2002 解题报告  回复  更多评论   

( ⊙o⊙ )哇,原来1301少考虑了方向,怪不得一直wa
2014-08-04 22:35 | zhangzhuojun123

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