Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

    再做一套玩玩~~

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(!&& !&& flg) return 0;
            
if(!&& !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, 
0sizeof(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 == -1return 0;
            scanf(
"%s %d:%d", op, &h, &m);
            
if(!id) break;
            t 
= h * 60 + m;
            
if(op[0== 'S'{
                
if(p[id].st == 1continue;
                
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;
}



    发现茫茫多想考研的同学都复习了好多了, 表示还木有开始复习的鸭梨很大... ...
    不切水题玩了, 要开始好好复习了!!


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理