似乎是每打一场比赛写一次初体验的节奏……
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)以及它们之间的换算比率。给定初始单位和目标单位,要求进行单位换算。应该是小学生都会的题目吧,主要靠迅速~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class LengthUnitCalculator { public: int dx[4]; string dw[4]; double calc(int amount,string fromUnit,string toUnit) { dx[0]=1;dx[1]=12;dx[2]=36;dx[3]=63360; dw[0]="in";dw[1]="ft";dw[2]="yd";dw[3]="mi"; double ret=amount; REP(i,0,3) if(fromUnit==dw[i]) { ret=ret*dx[i];break; } REP(i,0,3) if(toUnit==dw[i]) { ret=ret/dx[i];break; } return ret; } }; |
B.Shortest Path With Magic
这是一道图论题,题目大意:给定n个点(n<=50)以及每两点间的距离(0<=L<=9,L为整数)。现在你有k瓶魔法药剂,你可以选择某条边服下一瓶药剂,那么这条边的距离就变为原来的1/2,每条边仅可使用一次。求点0到点1的最短距离。
乍一看好像最短路上加个DP就好了嘛,但是漏看一个条件,每条边仅可使用一次,导致终测时跪了,结果样例还竟然都过,果然不能相信~~
看过TopSubmission才发现并不是我状态没表示对,是我姿势不对,DP的顺序错误。正解:用表示到达第
个点还剩
瓶药剂,初始均置为无穷大,然后以0为起点跑一遍Dijkstra,转移应该蛮好想的,注意细节处理。
的最小值就是答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
struct Node { int to,dist,rest; Node(int a=0,int b=0,int c=0):to(a),dist(b),rest(c) {} bool operator < (const Node& b) const {return dist>b.dist;} }; class ShortestPathWithMagic { public: static const int maxn=55; static const int INF=1000; int dist[maxn][maxn],d[maxn][maxn]; priority_queue<Node> Q; double getTime(vector<string> s_dist, int k) { int n=s_dist.size(); REP(i,0,n-1) REP(j,0,n-1) dist[i][j]=(s_dist[i][j]-'0')*2; REP(i,0,n-1) REP(j,0,k) d[i][j]=INF; Q.push(Node(0,0,k)); while(!Q.empty()) { Node s=Q.top();Q.pop(); int u=s.to,dst=s.dist,rest=s.rest; if(dst>d[u][rest]) continue; d[u][rest]=dst; REP(i,0,n-1) { if(d[u][rest]+dist[u][i]<d[i][rest]) Q.push(Node(i,d[u][rest]+dist[u][i],rest)); if(d[u][rest]+dist[u][i]/2<d[i][rest-1]) Q.push(Node(i,d[u][rest]+dist[u][i]/2,rest-1)); } } int ret=INF; REP(i,0,k) ret=min(ret,d[1][i]); return 1.0*ret/2; } }; |
C.Tree And Path Length 2
题目大意:询问是否存在一棵树,满足(1)结点数恰好为n; (2)长度为2的简单路径恰好有s条。(2<=n<=50, 1<=s<=1000)