|
|
Posted on 2011-06-25 23:34 Uriel 阅读(378) 评论(0) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
再做一套玩玩~~
1. 最小长方形
就是分别找到x, y的最小, 最大值, 水题, 不解释
 //浙大计算机研究生复试上机考试-2007年 最小长方形
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int mx, my, ax, ay, x, y;
  int main()  {
 bool flg = false;
  while(1) {
mx = my = 300;
ax = ay = -300;
while(scanf("%d %d", &x, &y)) {
if(!x && !y && flg) return 0;
if(!x && !y) {
flg = true;
break;
 }
mx = min(mx, x);
my = min(my, y);
ax = max(ax, x);
ay = max(ay, y);
flg = false;
}
printf("%d %d %d %d\n", mx, my, ax, ay);
}
return 0;
 }
2. 统计字符
大水, 不解释
//浙大计算机研究生复试上机考试-2007年 统计字符
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int cnt[300];
char s[10], str[100];
int main() {
int i;
while(gets(s), strcmp(s, "#")) {
gets(str);
memset(cnt, 0, sizeof(cnt));
for(i = 0; str[i]; ++i) {
cnt[str[i]]++;
}
for(i = 0; s[i]; ++i) {
printf("%c %d\n", s[i], cnt[s[i]]);
}
}
return 0;
}
3. 游船出租
大水, 不解释
//浙大计算机研究生复试上机考试-2007年 游船出租
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 110
struct boat{
int id, st, tt, bg;
}p[N];
int cnt;
double ti;
int main() {
int id, t, h, m;
char op[3];
while(1) {
while(scanf("%d", &id)) {
if(id == -1) return 0;
scanf("%s %d:%d", op, &h, &m);
if(!id) break;
t = h * 60 + m;
if(op[0] == 'S') {
if(p[id].st == 1) continue;
else {
p[id].st = 1;
p[id].bg = t;
}
}
else if(op[0] == 'E') {
if(!p[id].st) continue;
else {
p[id].st = 0;
ti += t - p[id].bg;
cnt++;
}
}
}
if(cnt)printf("%d %.0lf\n", cnt, ti / cnt);
else
puts("0 0");
cnt = 0;
ti = 0.0;
}
return 0;
}
4. EXCEL排序
考sort的大水题
//浙大计算机研究生复试上机考试-2007年 EXCEL排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100010
struct M {
int sco;
char id[10], name[10];
}p[N];
bool cmp1(M a, M b) {
return strcmp(a.id, b.id) < 0;
}
bool cmp2(M a, M b) {
if(strcmp(a.name, b.name))return strcmp(a.name, b.name) < 0;
else
return strcmp(a.id, b.id) < 0;
}
bool cmp3(M a, M b) {
if(a.sco != b.sco)return a.sco < b.sco;
else
return strcmp(a.id, b.id) < 0;
}
int c, n;
int main() {
int i, g = 1;
while(scanf("%d %d", &n, &c), n | c) {
for(i = 0; i < n; ++i) {
scanf("%s %s %d", p[i].id, p[i].name, &p[i].sco);
}
if(c == 1) sort(p, p + n, cmp1);
else if(c == 2) sort(p, p + n, cmp2);
else if(c == 3) sort(p, p + n, cmp3);
printf("Case %d:\n", g++);
for(i = 0; i < n; ++i)
printf("%s %s %d\n", p[i].id, p[i].name, p[i].sco);
}
return 0;
}
5. 畅通工程
注意重边, 一开始有个地方NC了, 一开始我最后判'?'是算出最小生成树的所有边权值和大于INF就输出'?', 这样有可能每条边其实都没超过INF, 但总和超过了, 被我判成'?', 实际上这种情况是符合要求的. 改为判断每条边都小于INF就过了
//浙大计算机研究生复试上机考试-2007年 畅通工程
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 110
#define INF 0x3f3f3f3f
int n, m, ans, adj[N][N], lowcost[N], closest[N];
void prim(int c[][N]) {
bool s[N];
s[1] = true;
for(int i = 2; i <= n; ++i) {
lowcost[i] = c[1][i];
closest[i] = 1;
s[i] = false;
}
for(int i = 1; i < n; ++i) {
int mi = INF, j = 1;
for(int k = 2; k <= n; ++k)
if(lowcost[k] < mi && !s[k]) {
mi = lowcost[k];
j = k;
}
s[j] = true;
for(int k = 2; k <= n; ++k)
if(c[j][k] < lowcost[k] && !s[k]) {
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}
int main() {
int i, j, a, b, c;
while(scanf("%d %d", &m, &n), m) {
for(i = 1; i <= n; ++i) {
for(j = 1; j <= n; ++j) {
if(i == j) adj[i][j] = 0;
else
adj[i][j] = adj[j][i] = INF;
}
}
for(i = 0; i < m; ++i) {
scanf("%d %d %d", &a, &b, &c);
adj[a][b] = min(c, adj[a][b]);
adj[b][a] = adj[a][b];
}
prim(adj);
ans = 0;
bool ok = true;
for(i = 1; i <= n; ++i) {
if(lowcost[i] >= INF) {
ok = false;
break;
}
ans += lowcost[i];
}
if(!ok) puts("?");
else
printf("%d\n", ans);
}
return 0;
}
6. 最大报销额
0-1背包, 以物品项数作为dp数组的下标
这题很坑爹, 那个单张发票中A, B, C三种物品以外的物品都不考虑, 而且这三种物品在同一张发票中可能重复出现, 要把它们全加起来, 单张发票的A或者B或者C都不能超过600.0 ... ...因为这个WA到死啊... ...
//浙大计算机研究生复试上机考试-2007年 最大报销额
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 50
struct tic {
int nt;
double mon;
}p[N];
int n, nn, aa, cnt[3];
double q, ans, dp[10100];
void DP() {
for(int i = 0; i <= aa; ++i) dp[i] = 0;
for(int i = 0; i < nn; ++i) {
for(int j = aa; j >= p[i].nt; --j) {
double tp = dp[j - p[i].nt] + p[i].mon;
if(dp[j] < tp && dp[j - p[i].nt] + p[i].mon <= q) dp[j] = tp;
}
}
}
int main() {
int i, j, k;
char c[10];
double x, tp, ttp;
while(scanf("%lf %d", &q, &n), n) {
nn = aa = 0;
for(i = 0; i < n; ++i) p[i].mon = 0.0;
for(i = 0; i < n; ++i) {
scanf("%d", &p[nn].nt);
aa += p[nn].nt;
bool ok = true;
cnt[0] = cnt[1] = cnt[2] = 0;
for(j = 0; j < p[nn].nt; ++j) {
scanf("%s", c);
if(c[0] == 'A' || c[0] == 'B' || c[0] == 'C') {
for(k = 0; c[k] != ':'; ++k);
for(k++, tp = 0; c[k] != '.'; ++k) tp = tp * 10 + c[k] - '0';
for(ttp = 0, k = strlen(c) - 1; c[k] != '.'; --k) ttp = ttp / 10 + c[k] - '0';
tp += ttp / 10;
p[nn].mon += tp;
cnt[c[0] - 'A'] += tp;
if(cnt[c[0] - 'A'] > 600.0) ok = false;
}
}
if(ok && p[nn].mon <= 1000.0) nn++;
}
DP();
ans = 0;
for(i = 0; i <= aa; ++i)
if(ans < dp[i]) ans = dp[i];
printf("%.2lf\n", ans);
}
return 0;
}
发现茫茫多想考研的同学都复习了好多了, 表示还木有开始复习的鸭梨很大... ...
不切水题玩了, 要开始好好复习了!!
|