Codeforces Round #203 (Div. 2) 水果3题

Codeforces Round #203 (Div. 2) 这场在最后千钧一发交了一发过了C，不然又要掉rating了。。。 B敲了太久了，orz编码能力不足

Codeforces Round #203 (Div. 2)

这场在最后千钧一发交了一发过了C，不然又要掉rating了。。。

B敲了太久了，orz编码能力不足啊～

A – TL

求编程比赛的时限，使得正确答案都能过，错误答案都不能过，且至少有一个正确答案的时间能小于时限的一半。

模拟水题，看题目看了好久。。

代码：

/**  Author:      illuz *  Blog:        http://blog.gaodaima.com/hcbbt*  File:        a.cpp*  Create Date: 2013-10-01 23:38:47*  Descripton:  a */#include #include using namespace std;#define rep(i, n) for (int i = 0; i > n >> m;	rep(i, n) {		cin >> t;		Mina = min(Mina, t);		Maxa = max(Maxa, t);	}	rep(i, m) {		cin >> t;		Minb = min(Minb, t);	}	if (Mina * 2 >= Minb || Minb <= Maxa) {		puts("-1");		return 0;	}	cout << max(Mina * 2, Maxa) << endl;	return 0;}

B – Resort

要找一条到达hotel的最长的路，注意路上不能有分叉且路是又向的。

直接dfs+剪枝就行了，图用set存的。。。看别人用一维数组好神。

代码：

/**  Author:      illuz *  Blog:        http://blog.gaodaima.com/hcbbt*  File:        b.cpp*  Create Date: 2013-10-02 00:17:29*  Descripton:  b */#include #include #include #include #include using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define repf(i, a, b) for (int i = (a); i <= (b); i++)#define ms(a, i) memset(a, i, sizeof(a))#define FI(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)const int MAXN = 100010;set pre[MAXN], nex[MAXN];int n, t, obj[MAXN], path[MAXN];int d[MAXN], used[MAXN];int Max = 0, rec;int dp(int o) {	if (d[o] != -1) return d[o];	if (nex[o].size() > 1 || used[o]) return d[o] = 0;	if (pre[o].size() == 0) {		path[o] = 0;		return d[o] = 1;	}	d[o] = 0;	used[o] = 1;	FI(i, pre[o]) {		int ts = dp(*i);		if (ts > d[o]) {			d[o] = ts;			path[o] = *i;		}	}	return d[o] + 1;}void F(int p, int cnt) {	if (p == 0) return;	F(path[p], cnt + 1);	if (cnt) printf("%d ", p);	else printf("%d\n", p);}int main() {	ms(d, -1);	scanf("%d", &n);	rep(i, n) {		scanf("%d", &obj[i + 1]);	}	rep(i, n) {		scanf("%d", &t);		if (t) {			pre[i + 1].insert(t);			nex[t].insert(i + 1);		}	}	repf(i, 1, n) if (obj[i]) {		t = dp(i);		if (Max < t) {			Max = t;			rec = i;		}	}	cout << Max << endl;	F(rec, 0);	return 0;}

C – Bombs

排雷，给出几个雷的地点，挖出那些雷回到原点炸掉。

本来做出b题血槽就已近空了，还有20多分钟，在qq闲侃了几句，无聊过来看看c题，发现是大水题。。。

按距离排下序输出就行了。

代码：

/**  Author:      illuz *  Blog:        http://blog.gaodaima.com/hcbbt*  File:        c.cpp*  Create Date: 2013-10-02 01:14:06*  Descripton:  c */#include #include #include using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)typedef long long LL;const int MAXN = 100010;struct P {	int x, y;	int step;} p[MAXN];int n;bool cmp(P a, P b) {	return a.step <b>> n;	LL cnt = 0;	rep(i, n) {		scanf("%d%d", &p[i].x, &p[i].y); 		p[i].step = abs(p[i].x) + abs(p[i].y);		if (p[i].x) cnt+= 2;		if (p[i].y) cnt+=2;		cnt += 2;	}	sort (p, p + n, cmp);	cout << cnt < 0)			printf("1 %d R\n", p[i].x);		else if (p[i].x  0)			printf("1 %d U\n", p[i].y);		else if (p[i].y  0)			printf("1 %d L\n", p[i].x);		else if (p[i].x  0)			printf("1 %d D\n", p[i].y);		else if (p[i].y < 0)			printf("1 %d U\n", -p<a>本文来源gao*daima.com搞@代#码&网6</a>[i].y);		printf("3\n");	}	return 0;}

喜欢 (0)赏

[搞代码]

分享 (0)