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.csdn.net/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); i++)
int main() {
int n, m, Mina = 100, Maxa = 0, Minb = 100, t;
cin >> 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.csdn.net/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.csdn.net/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.step;
}
int main() {
cin >> 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 << endl;
rep(i, n) {
if (p[i].x > 0)
printf("1 %d R\n", p[i].x);
else if (p[i].x < 0)
printf("1 %d L\n", -p[i].x);
if (p[i].y > 0)
printf("1 %d U\n", p[i].y);
else if (p[i].y < 0)
printf("1 %d D\n", -p[i].y);
printf("2\n");
if (p[i].x > 0)
printf("1 %d L\n", p[i].x);
else if (p[i].x < 0)
printf("1 %d R\n", -p[i].x);
if (p[i].y > 0)
printf("1 %d D\n", p[i].y);
else if (p[i].y < 0)
printf("1 %d U\n", -p[i].y);
printf("3\n");
}
return 0;
}
