TC SRM 675 Div.2

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

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

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)以及它们之间的换算比率。给定初始单位和目标单位，要求进行单位换算。应该是小学生都会的题目吧，主要靠迅速~

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;
	}
};

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的顺序错误。正解：用 $d(i,j)$ 表示到达第 $i$ 个点还剩 $j$ 瓶药剂，初始均置为无穷大，然后以0为起点跑一遍Dijkstra，转移应该蛮好想的，注意细节处理。 $d(1,j)$ 的最小值就是答案。

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;
	}
};

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)

AC. 梦想

TC SRM 675 Div.2

A.Length Unit Calculator

B.Shortest Path With Magic

C.Tree And Path Length 2

快速访问

随便看看

友情链接

标签