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. 质因数的个数
    这个还比较水。。
//2007年清华大学计算机研究生机试题 质因数的个数
#include<math.h>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int main() {
    
int n, i, cnt;
    
while(~scanf("%d"&n)) {
        i 
= 2; cnt = 1;
        
while(i <= sqrt(n)) {
            
if(n % i == 0{
                n 
/= i;
                cnt
++;
            }

            
else
                
++i;
        }

        printf(
"%d\n", cnt);
    }

    
return 0;
}


2. 10进制 VS 2进制
    这题木有什么好想法。。发现网上一位大牛http://blog.csdn.net/herechaos/article/details/5397430也是直接做的。。就直接模拟之了。。结果就是跑得暴慢。。路过的大牛有什么好想法的不吝赐教啊。。
    PS: 方法见上面链接的大牛Blog,不过网上这位大牛的源码AC不能,有几处小bug。。
//2007年清华大学计算机研究生机试题 10进制 VS 2进制
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int b[8010], c[80100], la, lb, lc;
char a[8010];

void pw(int x) {
    
int i, j, k;
    memset(c, 
0sizeof(c));
    c[
0= 1;
    lc 
= 1;
    
for(i = 0; i < x; ++i) {
        
for(j = 0; j < lc; ++j) c[j] *= 2;
        
for(k = 0; k < lc || c[k]; ++k) {
            c[k 
+ 1+= (c[k] / 10);
            c[k] 
%= 10;
        }

        lc 
= k;
    }

    la 
= (lc > la ? lc : la) + 1;
    
for(i = 0; i < la; ++i) {
        a[i] 
+= c[i];
        a[i 
+ 1+= (a[i] / 10);
        a[i] 
%= 10;
    }

}


void div() {
    
int i, j, cf, st, tp;
    la 
= strlen(a);
    
for(i = 0; i < la; ++i) a[i] -= '0';
    st 
= 0;
    lb 
= 0;
    
while(a[la - 1|| st < la) {
        
if(a[la - 1& 1) b[lb++= 1;
        
else
            b[lb
++= 0;
        cf 
= 0;
        
for(j = st; j < la; ++j) {
            tp 
= cf * 10 + a[j];
            a[j] 
= tp >> 1;
            cf 
= tp & 1;
        }

        
if(!a[st]) st++;
    }

    memset(a, 
0sizeof(a));
    
for(i = 0; i < lb; ++i)
        
if(b[i]) pw(lb - i - 1);
    
while(!a[la - 1]) la--;
}


int main() {
    
while(~scanf("%s", a)) {
        
if(!strcmp(a, "0")) puts("0");
        
else {
            div();
            
for(int i = la - 1; i >= 0--i) printf("%d", a[i]);
            puts(
"");
        }

    }

    
return 0;
}


3. 最小邮票数
    01背包。。一开始NC忘记判输出0的情况了。。WA*n
//2007年清华大学计算机研究生机试题 最小邮票数
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;
#define INF 0x3f3f3f3f

int n, m, dp[1000], w[100];

int main() {
    
int i, j;
    
while(~scanf("%d"&m)) {
        scanf(
"%d"&n);
        
for(i = 0; i < n; ++i) scanf("%d"&w[i]);
        
for(i = 1; i <= m; ++i) dp[i] = INF;
        dp[
0= 0;
        
for(i = 0; i < n; ++i) {
            
for(j = m; j >= w[i]; --j) {
                
if(dp[j - w[i]] == INF) continue;
                
else
                    dp[j] 
= min(dp[j], dp[j - w[i]] + 1);
            }

        }

        
if(dp[m] == INF) puts("0");
        
else
            printf(
"%d\n", dp[m]);
    }

    
return 0;
}

Feedback

# re: 清华大学计算机研究生机试题-2007年[未登录]  回复  更多评论   

2012-02-19 22:45 by lau
第一个你貌似跑的话会超时。你可以尝试一下

# re: 清华大学计算机研究生机试题-2007年  回复  更多评论   

2012-02-19 23:13 by Uriel
@lau
尝试又交了一次,10ms AC(九度OJ)
不过我这个确实是过于偷懒,暴力了。。= =||
有更快的方法分解质因数,我也没太搞过。。

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