Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
在THU的机试题里算是很水的一套吧。。

1. 最小花费
    简单DP,一开始理解错题意了。。以为a[]是相邻两站间的距离,结果WA*6。。以为我DP都不会写了。。
//2011年清华大学计算机研究生机试题 最小花费
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;
#define N 100010
#define I long long
#define INF -1

int a, b, n;
I l1, l2, l3, c1, c2, c3, w[N], dp[N];

int main() {
    
int i, j;
    I tp, wt;
    
while(~scanf("%lld %lld %lld %lld %lld %lld"&l1, &l2, &l3, &c1, &c2, &c3)) {
        scanf(
"%d %d"&a, &b);
        
if(a > b) swap(a, b);
        scanf(
"%d"&n);
        
for(i = 2; i <= n; ++i) scanf("%lld"&w[i]);
        w[
1= 0;
        
if(a == b) {
            puts(
"0");
            
continue;
        }
        
for(i = a; i <= b; ++i) dp[i] = INF;
        dp[a] 
= 0;
        
for(i = a; i <= b; ++i) {
            
for(j = i + 1; j <= b; ++j) {
                
if(dp[i] == -1continue;
                tp 
= w[j] - w[i];
                
if(tp > l3) break;
                
if(l2 < tp && tp <= l3) wt = c3;
                
else if(l1 < tp && tp <= l2) wt = c2;
                
else
                    wt 
= c1;
                
if(dp[j] == -1 || dp[i] + wt < dp[j]) dp[j] = dp[i] + wt;
            }
        }
        printf(
"%lld\n", dp[b]);
    }
    
return 0;
}


2. 约数的个数
    暴力就行,不过只需算到sqrt
//2011年清华大学计算机研究生机试题 约数的个数
#include<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
int n, a[1010];
 
int main() {
    
int i, tp, j;
    
while(~scanf("%d"&n)) {
        
for(i = 0; i < n; ++i) scanf("%d"&a[i]);
        
for(i = 0; i < n; ++i) {
            
if(a[i] == 1) {
                puts(
"1");
                
continue;
            }
            
else {
                tp 
= (int)sqrt(a[i]);
                
int cnt = 0;
                
for(j = 1; j <= tp; ++j) {
                    
if(a[i] % j == 0) cnt++;
                }
                cnt 
+= cnt;
                
if(a[i] == tp * tp) cnt--;
                printf(
"%d\n", cnt);
            }
        }
    }
    
return 0;
}


3. 剩下的树
    暴力水过
//2011年清华大学计算机研究生机试题 剩下的树
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
int L, M, fg[10010];
 
int main() {
    
int i, a, b;
    
while(~scanf("%d %d"&L, &M)) {
        memset(fg, 
0sizeof(fg));
        
while(M--) {
            scanf(
"%d %d"&a, &b);
            
for(i = a; i <= b; ++i) fg[i] = 1;
        }
        
int ans = 0;
        
for(i = 0; i <= L; ++i)
            
if(!fg[i]) ans++;
        printf(
"%d\n", ans);
    }
    
return 0;
}

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