WA死在00001 00001這種數據上。。后來同學A了之后對拍半天才發現。。
WA*4。。。
//2005年上海交通大學計算機研究生機試題 數字反轉
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
int t1, t2, aa, bb, cc, cse, a, b;
while(~scanf("%d", &cse)) {
while(cse--) {
scanf("%d %d", &a, &b);
t1 = a; t2 = b;
aa = bb = cc = 0;
while(t1 > 0) {
aa = aa * 10 + (t1 % 10);
t1/= 10;
}
while(t2 > 0) {
bb = bb * 10 + (t2 % 10);
t2/= 10;
}
t1 = a + b;
while(t1 > 0) {
cc = cc * 10 + (t1 % 10);
t1/= 10;
}
if(aa + bb == cc) printf("%d\n", a + b);
else
puts("NO");
}
}
return 0;
}
2. 路徑打印
WA*2+PE*3。。。留份代碼供同糾結此題的對拍。。
//2005年上海交通大學計算機研究生機試題 路徑打印
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct M {
char s[100];
}p[20];
bool cmp(M a, M b) {
return strcmp(a.s, b.s) < 0;
}
int n;
int main() {
//freopen("d:\\out.txt", "w", stdout);
int i, j, k, h;
while(scanf("%d", &n), n) {
for(i = 0; i < n; ++i) scanf("%s", p[i].s);
sort(p, p + n, cmp);
for(i = 0; p[0].s[i]; ++i) {
if(p[0].s[i] == '\\') {
if(i < strlen(p[0].s) - 1) {
puts("");
for(j = 0; j < i + 1; ++j) putchar(' ');
}
}
else
putchar(p[0].s[i]);
}
for(i = 1; i < n; ++i) {
j = 0;
while(p[i].s[j] && p[i].s[j] == p[i - 1].s[j]) ++j;
while(j > 0 && p[i].s[j] != '\\') --j;
if(p[i].s[j] == '\\') ++j;
for(k = j; p[i].s[k]; ++k) {
if(p[i].s[k] == '\\') {
if(k < strlen(p[i].s) - 1) {
puts("");
for(h = 0; h < k + 1; ++h) putchar(' ');
}
}
else {
if(k == j) {
puts("");
for(h = 0; h < k; ++h) putchar(' ');
}
putchar(p[i].s[k]);
}
}
}
puts("");
puts("");
}
return 0;
}
3. 棋盤游戲
DFS，注意不能只記錄每個位置的最小值，要同時記錄取到該最小值時的狀態，狀態，位置相同并且dp值更小才更新
//2005年上海交通大學計算機研究生機試題 棋盤游戲
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0x3f3f3f3f
int d[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int dp[6][6][5], a[6][6];
bool ok(int x, int y) {
if(x >= 0 && x < 6 && y >= 0 && y < 6) return 1;
return 0;
}
void DFS(int x, int y, int st, int sum) {
int i, j, tx, ty;
if(~dp[x][y][st] && dp[x][y][st] <= sum) return;
else
dp[x][y][st] = sum;
for(i = 0; i < 4; ++i) {
tx = x + d[i][0];
ty = y + d[i][1];
if(ok(tx, ty)) DFS(tx, ty, st * a[tx][ty] % 4 + 1, sum + st * a[tx][ty]);
}
}
int main() {
int cse, i, j, sx, sy, ex,ey;
scanf("%d", &cse);
while(cse--) {
for(i = 0; i < 6; ++i)
for(j = 0; j < 6; ++j)
scanf("%d", &a[i][j]);
scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
memset(dp, -1, sizeof(dp));
DFS(sx, sy, 1, 0);
int mi = INF;
for(i = 1; i <= 4; ++i) {
if(~dp[ex][ey][i] && dp[ex][ey][i] < mi) mi = dp[ex][ey][i];
}
printf("%d\n", mi);
}
return 0;
}