fjnu09暑期训练赛题解
July 30th, 2010
10 comments
题目地址密码:000111
1001Who’s in the Middle
简单题，求中位数
#include <iostream> #include <algorithm> using namespace std; int a[10004]; int main() { int n; while(scanf("%d", &n) != EOF) { for(int i = 0; i < n; ++i) scanf("%d", &a[i]); sort(a, a+n); printf("%d\n", a[n/2]); } return 0; }
1002跑跑卡丁车
每过一段赛道，可以得到20%能量，达到100%换一个加速卡，最多2张加速卡，有2个加速卡而能量再次集满,那么能量清零但得不到加速卡，那么可知总共有15种状态：
加速卡数量 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 能量 0% 20% 40% 60% 80% 0% 20% 40% 60% 80% 0% 20% 40% 60% 80% 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
我们设v[i](0<=i<=14)代表在到达状态i时，所用的最短时间.
假设普通用时为a[i],加速用时为b[i]，如果我们不用加速卡，
那么有v[i] = v[i-1]+a[i],这里还要注意到一点，就是当现在处于状态14时，如果仍旧不用加速卡而保持普通速度行驶一段，则能量清0，加速卡仍旧为2张，即回到状态10，所以有
v[10] = v[14]+a[i]
对于用了加速卡的情况，则有
v[i-5] = v[i]+b[i](i>=5)
最后，注意到总共可能要行驶100*100段，而每一段的状态又只与前一段有关，所以为了节约空间，采用轮转数组。
#include<iostream> using namespace std; const int M = 15; int main() { int l, n; int a[101], b[101], t = 0; unsigned int v[2][M], res; while(scanf("%d%d", &l, &n) != EOF) { for(int i = 0; i < l; ++i) scanf("%d", &a[i]); for(int i = 0; i < l; ++i) scanf("%d", &b[i]); memset(v, 0x0f0f, sizeof(v)); res = 0x0f0f0f0f; v[t][0] = 0; for(int i = 0; i < n; ++i) for(int j = 0; j < l; ++j) { v[!t][0] = 0x0f0f0f0f; for(int k = 0; k < M; ++k) { if(k != M - 1) v[!t][k+1] = v[t][k] + a[j]; if(k >= 5 && v[!t][k-5] > v[t][k] + b[j]) v[!t][k-5] = v[t][k] + b[j]; } //有2个加速卡而能量再次集满的情况如下 if(v[!t][10] > v[t][14] + a[j]) v[!t][10] = v[t][14] + a[j]; t = !t; } for(int i = 0; i < M; ++i) if(res > v[t][i]) res = v[t][i]; printf("%u\n", res); } return 0; }
1003 Rescue
BFS+优先队列
给定一个地图，里面有很多个r,一个a,求这么多个r里，哪个能最快走到a,输出最短时间，如果中间遇到x,则时间要+1
我们可以换个思路，从a出发，去找离它最近的r,这样就可以用BFS解决，又因为遇到x要+1，普通的队列会得不到最优值，所以用优先队列
#include <iostream> #include <queue> using namespace std; int h, w, res; int dx[] = {0, -1, 0, 1}; int dy[] = {1, 0, -1, 0}; char mp[202][202]; struct P { int x, y, v; bool operator<(const P &a) const{ return v > a.v; } P(int xx, int yy, int hh) { x = xx, y = yy, v = hh; } P(){} }tmp; int bfs() { priority_queue<P>Q; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) if(mp[i][j] == 'a') { Q.push(P(i, j, 0)); goto t1; } t1:; while(!Q.empty()) { tmp = Q.top(); Q.pop(); for(int i = 0; i < 4; ++i) { int tx = tmp.x + dx[i], ty = tmp.y + dy[i]; if(tx >= 0 && tx < h && ty >= 0 && ty < w && mp[tx][ty] != '#') { if(mp[tx][ty] == '.') Q.push(P(tx, ty, tmp.v+1)); else if(mp[tx][ty] == 'x') Q.push(P(tx, ty, tmp.v+2)); else if(mp[tx][ty] == 'r') return tmp.v + 1; mp[tx][ty] = '#'; } } } return -1; } int main() { while(scanf("%d%d", &h, &w) != EOF) { for(int i = 0; i < h; ++i) scanf("%s", mp[i]); res = bfs(); if(res == -1) puts("Poor ANGEL has to stay in the prison all his life."); else printf("%d\n", res); } return 0; }
1004统计难题
简单Tire树应用
#include<iostream> using namespace std; struct Tire { Tire *a[26]; int cnt; }tire[1000000], *q; int l = 1; int main() { char tmp[13]; int s, i; while(gets(tmp)) { if(tmp[0] == '\0') break; q = &tire[0]; for(i = 0; tmp[i] != '\0'; ++i) { if(q->a[tmp[i]-'a'] == NULL) q->a[tmp[i]-'a'] = &tire[l++]; q = q->a[tmp[i]-'a']; ++q->cnt; } } while(gets(tmp)) { q = &tire[0]; for(i = 0; tmp[i] != '\0'; ++i) { if(q->a[tmp[i]-'a'] == NULL) break; q= q->a[tmp[i]-'a']; } if(tmp[i] == '\0') printf("%d\n", q->cnt); else puts("0"); } return 0; }
1005Climbing Worm
就是跟着题目意思模拟就行了。。
#include <iostream> using namespace std; int main() { int n, u, d, i, c, t; while(scanf("%d%d%d", &n, &u, &d)) { if(n == 0) break; c = t = 0; while(c < n) { ++t; if(t & 1) c += u; else c -= d; } printf("%d\n", t); } return 0; }
Recent Comments