Zju 1163 The Staircases -- 冗余的代码-- 编程爱好者博客

2174729 2006-12-18 23:13:20 Accepted 1163 C++ 00:00.02 2384K Crux.D 很好的一道dp题，积压已久。这让我想起小学生时代的作文了： “今天我又做了一件好事，我真高兴呀。” 这道题的陷阱是大数，用double即可避过。方程是b[i][k] = b[i - k][k - 1]，i代表N，k代表最高层的块数。然后把b[i][k]累加起来就可。另外这题只用了23行，和今天做的另一道题1111比起来，简直是他喵的奇迹。那道题整整花了我半个下午，调试了3次，写了400多行…… #include <cstdio>#include <string> double a[505][505]; int main(){ int i, k, n; memset(a, 0x00, sizeof(a)); a[0][0] = 1; for(i = 0; i < 505; i ++) { for(k = 1; k <= i; k ++) a[i][k] = a[i - k][k - 1] + a[i][k - 1]; for(k = i + 1; k < 505; k ++) a[i][k] = a[i][i]; } while(scanf("%d", &n) && n) { printf("%0.0f\n", a[n][n] - 1); } return 0;} ---------------------------- 对比的程序，zju 1111 #include <iostream>#include <string>using namespace std; int bw, ww, tie, t_b, t_w; struct card{ int v, s;} b[5], w[5]; void pc(card *a){ int i; for(i = 0; i < 5; i ++) { printf("%d ", a[i].v, a[i].s); } printf("\n");} void print(){ pc(b); pc(w); printf("%d %d\n", t_b, t_w);} int high(card *a){ int i, sum = 0; for(i = 0; i < 5; i ++) { sum *= 14; sum += a[i].v; } return sum;} void atoc(string str, card &c){ int sv, ss; if(str[0] == 'A') sv = 13; else if(str[0] == 'T') sv = 9; else if(str[0] == 'J') sv = 10; else if(str[0] == 'Q') sv = 11; else if(str[0] == 'K') sv = 12; else sv = str[0] - '0' - 1; if(str[1] == 'C') ss = 0; else if(str[1] == 'D') ss = 1; else if(str[1] == 'H') ss = 2; else if(str[1] == 'S') ss = 3; c.s = ss, c.v = sv;} void s_sort(card *a){ int i, k, j, mx; for(i = 0; i < 4; i ++) { j = i, mx = a[j].v; for(k = i + 1; k < 5; k ++) { if(a[k].v > mx) { mx = a[k].v; j = k; } } int tv, ts; tv = a[j].v, ts = a[j].s; a[j].v = a[i].v, a[j].s = a[i].s; a[i].v = tv, a[i].s = ts; }} int str_flush(card *a){ int i; for(i = 0; i < 5; i ++) { if(a[i].s != a[0].s) return 0; if(a[i].v != a[0].v - i) return 0; } return a[0].v;} int four_kind(card *a){ int i, l[14]; memset(l, 0, sizeof(l)); for(i = 0; i < 5; i ++) { l[a[i].v] ++; } for(i = 0; i < 14; i ++) { if(l[i] == 4) { return i; } } return 0;} int full_house(card *a){ int i, l[14], tp = 0, db = 0; memset(l, 0, sizeof(l)); for(i = 0; i < 5; i ++) { l[a[i].v] ++; } for(i = 1; i <= 13; i ++) { if(l[i] == 3) tp = i; if(l[i] == 2) db = i; if(l[i] == 1) return 0; } if(tp && db) return tp;} int one_flush(card *a){ int i; for(i = 0; i < 5; i ++) { if(a[i].s != a[0].s) return 0; } return high(a);} int straight(card *a){ int i; for(i = 0; i < 5; i ++) { if(a[i].v != a[0].v - i) return 0; } return a[0].v;} int tp_kind(card *a){ int i, l[14]; memset(l, 0, sizeof(l)); for(i = 0; i < 5; i ++) { l[a[i].v] ++; } for(i = 0; i < 14; i ++) { if(l[i] == 3) return i; } return 0;} int db_db(card *a){ int i, l[14], sum = 0, d[2], t; memset(l, 0, sizeof(l)); for(i = 0; i < 5; i ++) { l[a[i].v] ++; } for(i = 0; i < 14; i ++) { if(l[i] == 2) d[sum ++] = i; if(l[i] == 1) t = i; } if(sum == 2) return (d[1] * 14 + d[0]) * 14 + t; return 0;} int db_kind(card *a){ int i, l[14], f = 0, d[5], sum = 0; memset(l, 0, sizeof(l)); for(i = 0; i < 5; i ++) { l[a[i].v] ++; } for(i = 0; i < 14; i ++) { if(l[i] == 2) f = i; if(l[i] == 1) d[sum ++] = i; } if(f) return ((f * 14 + d[2]) * 14 + d[1]) * 14 + d[0]; return 0;} void compare(){ s_sort(b); s_sort(w); t_b = 9, t_w = 9; bw = 0, ww = 0, tie = 0; bw = str_flush(b), ww = str_flush(w); if(bw) t_b = 0; if(ww) t_w = 0; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = four_kind(b), ww = four_kind(w); if(bw) t_b = 1; if(ww) t_w = 1; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = full_house(b), ww = full_house(w); if(bw) t_b = 2; if(ww) t_w = 2; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = one_flush(b), ww = one_flush(w); if(bw) t_b = 3; if(ww) t_w = 3; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = straight(b), ww = straight(w); if(bw) t_b = 4; if(ww) t_w = 4; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = tp_kind(b), ww = tp_kind(w); if(bw) t_b = 5; if(ww) t_w = 5; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = db_db(b), ww = db_db(w); if(bw) t_b = 6; if(ww) t_w = 6; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = db_kind(b), ww = db_kind(w); if(bw) t_b = 7; if(ww) t_w = 7; if(bw && !ww || ww && !bw) return; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } } bw = 0, ww = 0, tie = 0; bw = high(b), ww = high(w); if(bw) t_b = 8; if(ww) t_w = 8; if(bw && ww) { if(bw > ww) { ww = 0; return; } else if(ww > bw) { bw = 0; return; } else { bw = 0, ww = 0, tie = 1; return; } }} int main(){ //freopen("in.txt", "r", stdin); string str; while(cin >> str) { atoc(str, b[0]); int i; for(i = 0; i < 4; i ++) { cin >> str; atoc(str, b[i + 1]); } for(i = 0; i < 5; i ++) { cin >> str; atoc(str, w[i]); } compare(); //print(); if(bw) printf("Black wins.\n"); if(ww) printf("White wins.\n"); if(tie) printf("Tie.\n"); } return 0;}

博客介绍

正文

Zju 1163 The Staircases2006-12-18 23:19:00

评论