難度還行的一套
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[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384};
char s[20001][500];
int main() {
int tp, i, j, fg;
memset(s, 0x00, sizeof(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;
}