#include <cstdio> #include <algorithm> #include <string> using std::string; int main() { int first = 1; while (1) { if (!first) { char tmp[10]; if (!gets(tmp)) break; puts(""); } first = 0; char s1[310], s2[310]; gets(s1 + 1); gets(s2 + 1); int i, j, lcs[310][310] = {}, N = 0, max = 0; for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++) if (s1[i] == s2[j]) { lcs[i][j] = lcs[i - 1][j - 1] + 1; if (lcs[i][j] > max) max = lcs[i][j]; } else lcs[i][j] = 0; if (max < 1) { puts("No common sequence."); continue; } string ans[10000]; int k = 0; for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++) if (lcs[i][j] == max) ans[k++] = string(s1 + i - max + 1, s1 + i + 1); sort(ans, ans + k); for (i = 0; i < k; i++) if (i && !(ans[i].compare(ans[i - 1]))) continue; else puts(ans[i].c_str()); } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2012年10月21日
UVa 760 - DNA Sequencing
2012年10月20日
UVa 12241 - Digits Count
#include <stdio.h> void cal(long long n, long long* num) { long long fac = 1; while (n / fac) { long long low = n - (n / fac) * fac, now = (n / fac) % 10, high = n / (fac * 10); int i; for (i = 0; i < 10; i++) { if (now < i) num[i] += high * fac; else if (now == i) num[i] += high * fac + low + 1; else if (now > i) num[i] += (high + 1) * fac; } fac *= 10; } while ((fac /= 10)) num[0] -= fac; } int main() { int start, end; while (scanf("%d%d", &start, &end) && start || end) { long long ans[10] = {}, sub[10] = {}; cal(start - 1, sub); cal(end, ans); int i; for (i = 0; i < 10; i++) printf("%lld%c", ans[i] - sub[i], i == 9 ? '\n' : ' '); } return 0; }
2012年10月15日
UVa 112 - Tree Summing
#include <cstdio> #include <stack> using std::stack; int main() { int ans; while (scanf("%d", &ans) == 1) { int l = 0, r = 0, num = 0, sum = 0; stack<int> tree; char c, old[4] = {0}; bool flag = 0, start = 0, neg = 0; while (!start || l != r) { c = getchar(); switch (c) { case '(': l++; if (start && old[2] != ')') { if (neg) num *= -1; sum += num; tree.push(num); num = 0; neg = 0; } old[0] = old[1]; old[1] = old[2]; old[2] = c; start = 1; break; case ')': r++; if (old[2] != '(' && tree.size()) { sum -= tree.top(); tree.pop(); } else if (old[0] == '(' && old[1] == ')' && old[2] == '(' && sum == ans) { flag = 1; } old[0] = old[1]; old[1] = old[2]; old[2] = c; break; case '-': neg = 1; case ' ': case '\n': break; default: num = num * 10 + c - '0'; } } if (flag) puts("yes"); else puts("no"); } return 0; }
2012年10月11日
UVa 10344 - 23 out of 5
#include <cstdio> #include <algorithm> int num[12], flag; void run(int sum, int times) { if (flag) return; if (times == 5) { if (sum == 23) flag = 1; return; } run(sum + num[times], times + 1); run(sum - num[times], times + 1); run(sum * num[times], times + 1); } int main() { while (scanf("%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4])) { if (!num[0] && !num[1] && !num[2] && !num[3] && !num[4]) break; flag = 0; std::sort(num, num + 5); do { run(num[0], 1); } while (!flag && std::next_permutation(num, num + 5)); if (flag) puts("Possible"); else puts("Impossible"); } return 0; }
UVa 574 - Sum It Up
#include <cstdio> #include <algorithm> #include <string> #include <map> using std::string; using std::map; int num[12], flag, n; map<string, int> dic; void run(int sum, int times, int *check) { if (!sum) { flag = 1; int i; string s; for (i = n - 1; i >= 0; i--) if (check[i]) { char temp[10]; sprintf(temp, "%d", num[i]); s.append(temp); break; } for (i--; i >= 0; i--) if (check[i]) { char temp[10]; sprintf(temp, "+%d", num[i]); s.append(temp); } if (dic[s]) return; else dic[s] = 1; puts(s.c_str()); return; } if (sum < 0 || times == -1) return; check[times] = 1; run(sum - num[times], times - 1, check); check[times] = 0; run(sum, times - 1, check); } int main() { int t; while (scanf("%d%d", &t, &n) && t || n) { dic.erase(dic.begin(), dic.end()); for (int i = 0; i < n; i++) scanf("%d", &num[i]); flag = 0; std::sort(num, num + n); int check[12] = {}; printf("Sums of %d:\n", t); run(t, n - 1, check); if (!flag) puts("NONE"); } return 0; }
2012年10月6日
UVa 750 - 8 Queens Chess Problem
#include <stdio.h> int times, R, C; void run(int r, int *checkC, int *checkL, int *checkR, int *p) { if (r == 8) { printf("%2d ", times++); int i, j; for (j = 0; j < 8; j++) printf(" %d", 8 - p[j]); puts(""); return; } if (r == R) { p[R] = C; run(r + 1, checkC, checkL, checkR, p); return; } int c; for (c = 7; c >= 0; c--) { if (!checkC[c] && !checkL[r + c] && !checkR[r - c + 8]) { p[r] = c; checkC[c] = 1; checkL[r + c] = 1; checkR[r - c + 8] = 1; run(r + 1, checkC, checkL, checkR, p); checkC[c] = 0; checkL[r + c] = 0; checkR[r - c + 8] = 0; } } } int main() { int n; scanf("%d", &n); while (n--) { times = 1; scanf("%d%d", &R, &C); puts("SOLN COLUMN\n # 1 2 3 4 5 6 7 8\n"); int checkC[8] = {}, checkL[16] = {}, checkR[16] = {}, p[8] = {}; R--; C--; int tmp; tmp = R; R = C; C = tmp; C = 7 - C; checkC[C] = 1; checkL[R + C] = 1; checkR[R - C + 8] = 1; run(0, checkC, checkL, checkR, p); if (n) puts(""); } return 0; }
訂閱:
文章 (Atom)