AC. 梦想

frank_c1

TC SRM 675 Div.2

发布于2015年12月08日 | 暂无评论 | 967阅读 | 比赛经历

似乎是每打一场比赛写一次初体验的节奏……

TopCoder SRM 675于2015/12/10 20:00 (CST)举行。前面说过,TC是一个十分神奇的网站,不仅是它的提交方式,而且打开方式也是如此。为什么一定要用Arena呢?如果加载一个小时还没好怎么破?比赛开始后一直被卡在Loading怎么破?打开后终于看到题目,发现自己先前辛苦设置的环境全没了,怎么破?反正就是这样,折腾到20:20左右才开始打,我的分数就这样一分一秒地溜走。

先记录一下成绩吧:比赛时测试样例通过2道,System Test通过1道(Problem A),总成绩196.42,Div.2排名224,rating升为1153。在此吐槽一句,发现新参赛的选手只要迅速通过A题,rating就可以上升到1200+,直接晋级Div.1,这也真是……

A.Length Unit Calculator

送分题。给四个单位inches (in), feet (ft), yards (yd), miles (mi)以及它们之间的换算比率。给定初始单位和目标单位,要求进行单位换算。应该是小学生都会的题目吧,主要靠迅速~

B.Shortest Path With Magic

这是一道图论题,题目大意:给定n个点(n<=50)以及每两点间的距离(0<=L<=9,L为整数)。现在你有k瓶魔法药剂,你可以选择某条边服下一瓶药剂,那么这条边的距离就变为原来的1/2,每条边仅可使用一次。求点0到点1的最短距离。

乍一看好像最短路上加个DP就好了嘛,但是漏看一个条件,每条边仅可使用一次,导致终测时跪了,结果样例还竟然都过,果然不能相信~~

看过TopSubmission才发现并不是我状态没表示对,是我姿势不对,DP的顺序错误。正解:用d(i,j)表示到达第i个点还剩j瓶药剂,初始均置为无穷大,然后以0为起点跑一遍Dijkstra,转移应该蛮好想的,注意细节处理。d(1,j)的最小值就是答案。

C.Tree And Path Length 2

题目大意:询问是否存在一棵树,满足(1)结点数恰好为n; (2)长度为2的简单路径恰好有s条。(2<=n<=50, 1<=s<=1000)