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. Fibonacci
    裸求Fibonacci且用不着矩阵加速
//2006年上海交通大学计算机研究生机试题 Fibonacci
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
int main() {
    
int n, i, t, pre, cur;
    
while(~scanf("%d"&n)) {
        
if(!n) puts("0");
        
else if(n == 1) puts("1");
        
else {
            pre 
= 0; cur = 1;
            
for(i = 2; i <= n; ++i) {
                t 
= cur + pre;
                pre 
= cur;
                cur 
= t;
            }
            printf(
"%d\n", cur);
        }
    }
    
return 0;
}


2. WERTYU
    直接模拟
//2006年上海交通大学计算机研究生机试题 WERTYU
#include<ctype.h>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
char s[100010];
 
char num[] = {'9''`''1''2''3''4''5''6''7''8'};
char exg[] = {'A''V''X''S''W''D''F''G''U''H''J''K''N''B''I''O''Q''E''A''R''Y''C''Q''Z''T''Z'};
 
int main() {
    
int i;
    
while(gets(s) != NULL) {
        
for(i = 0; s[i]; ++i) {
            
if(isspace(s[i])) putchar(s[i]);
            
else if(isupper(s[i])) putchar(exg[s[i] - 'A']);
            
else if(isdigit(s[i])) putchar(num[s[i] - '0']);
            
else if(s[i] == '[') putchar('P');
            
else if(s[i] == ']') putchar('[');
            
else if(s[i] == '\\') putchar(']');
            
else if(s[i] == ';') putchar('L');
            
else if(s[i] == '\'') putchar(';');
            else if(s[i] == ',') putchar('M');
            
else if(s[i] == '.') putchar(',');
            
else if(s[i] == '/') putchar('.');
            
else if(s[i] == '-') putchar('0');
            
else if(s[i] == '=') putchar('-');
        }
        puts(
"");
    }
    
return 0;
}


3. String Matching
    KMP应用,POJ3461代码直接AC
//2006年上海交通大学计算机研究生机试题 String Matching
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
int nxt[100001];
char a[1000010], b[1000010];
 
void getnxt(char *s) {
    nxt[
0= -1;
    
int i = 1, j = 0;
    
while(s[i]) {
        
if(j == -1 || s[i] == s[j]) {
            
++i; ++j;
            
if(s[i] != s[j]) nxt[i] = j;
            
else
                nxt[i] 
= nxt[j];
        }
        
else
            j 
= nxt[j];
    }
}
 
int kmp(char *src, char *dest) {
    
int i = 0, j = 0, s_len, p_len, sum = 0;
    s_len 
= strlen(src);
    p_len 
= strlen(dest);
M:  
while(i < s_len && j < p_len) {
        
if(j == -1 || src[i] == dest[j]) {
            
++i; ++j;
        }
        
else
            j 
= nxt[j];
    }
    
if(j == p_len && i < s_len) {
        sum
++; j = nxt[j]; goto M;
    }
    
else if(j == p_len && i == s_len) {sum++return sum;}
    
else
        
return sum;
    
return -1;
}
 
int main() {
    
while(~scanf("%s %s", a, b)) {
        getnxt(b);
        printf(
"%d\n", kmp(a, b));
    }
    
return 0;
}


4. 2的幂次方
    以为大数这样表示会很长很长。。还担心MLE啥的。。其实手算一下就知道这样表示很短的其实。。
//2006年上海交通大学计算机研究生机试题 2的幂次方
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
 
int n;
int f[] = {1248163264128256512102420484096819216384};
char s[20001][500];
 
int main() {
    
int tp, i, j, fg;
    memset(s, 
0x00sizeof(s));
    strcat(s[
0], "0");
    strcpy(s[
1], "2(0)");
    strcpy(s[
2], "2");
    
for(i = 3; i <= 20000++i) {
        tp 
= i;
        fg 
= 0;
        
for(j = 14; j >= 0--j) {
            
if(f[j] > i) continue;
            
if(f[j] == i) {
                strcat(s[i], 
"2(");
                strcat(s[i], s[j]);
                strcat(s[i], 
")");
                
break;
            }
            
else {
                
while(tp >= f[j]) {
                    tp 
-= f[j];
                    
if(fg) strcat(s[i], "+");
                    strcat(s[i], s[f[j]]);
                    fg 
= 1;
                }
            }
        }
    }
    
while(~scanf("%d"&n)) {
        puts(s[n]);
    }
    
return 0;
}

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