A3.

/****************************************************************************** A3.imcc---糟糕的向导 Solved by pladene@bbs.whnet.edu.cn 问题：给定一个简单图（不一定连通），找出其所有割点（articulation points） 算法: 二分查找 + 搜索 if (ans[i] == true)，第二个地点就是割点 *******************************************************************************/ #include <stdlib.h> #include <string.h> #include <iostream.h> #define MAX 100 char name[MAX][35], src[35], des[35]; bool w[MAX][MAX], ans[MAX]; int nv, ne, sum, cnt; int dfn[MAX], father[MAX], low[MAX]; int min(int a, int b) { return (a < b ? a : b); } int cmp(const void* s1, const void* s2) { return (strcmp((char*)s1, (char*)s2)); } // Find the given string using bi-search int bisearch(char str[]) { int mid, s = 0, e = nv - 1; while (s <= e) { mid = (s + e) / 2; if (!strcmp(str, name[mid])) return mid; else if (strcmp(str, name[mid]) < 0) e = mid - 1; else s = mid + 1; } return 0; } void input_init() { int i, j, k; memset(w, false, sizeof(w)); for (i = 0; i < nv; i++) cin >> name[i]; // sort the strings in in alphabetic order qsort((void*)name, nv, sizeof(name[0]), cmp); cin >> ne; for (i = 0; i < ne; i++) { cin >> src >> des; j = bisearch(src); k = bisearch(des); w[j][k] = w[k][j] = true; } memset(ans, false, sizeof(ans)); memset(dfn, 0, sizeof(dfn)); sum = 0; } // Find all the articulation point using DFS void solve(int cur, int val) { int i; val++; low[cur] = dfn[cur] = val; for (i = 0; i < nv; i++) if (w[cur][i]) { w[cur][i] = w[i][cur] = false; if (!dfn[i]) { father[i] = cur; solve(i, val); } else low[cur] = min(dfn[i], low[cur]); } if (dfn[father[cur]] == 1) { cur = father[cur]; for (i = 0; i < nv; i++) if (w[cur][i]) { ans[cur] = true; w[cur][i] = w[i][cur] = false; if (!dfn[i]) { father[i] = cur; solve(i, val); } else low[cur] = min(dfn[i], low[cur]); } } else { if (low[cur] < dfn[father[cur]]) low[father[cur]] = min(low[father[cur]], low[cur]); else ans[father[cur]] = true; } } // output the result void output() { int i; for (i = 0; i < nv; i++) if (ans[i]) sum++; cout << "City map #" << cnt++ << ": " << sum << " camera(s) found\n"; for (i = 0; i < nv; i++) if (ans[i]) cout << name[i] << endl; } int main() { int i; cnt = 1; bool isFirst = false; while (cin >> nv) { if (!nv) break; if (isFirst) cout << endl; else isFirst = true; input_init(); for (i = 0; i < nv; i++) { if (!dfn[i]) { father[i] = i; solve(i, 0); } } output(); } return 0; }

A4.

/****************************************************************************** A4.Buy the Ticket Solved by pladene@bbs.whnet.edu.cn 问题：Catalan经典问题的推广 算法: Catalan数推广 + 高精度 输入m, n，结果是 (m-n+1)*(m+n)!/(m+1) *******************************************************************************/ #include <iostream.h> #define MAX 800 int digit[MAX]; void init() { for (int i = 0; i < MAX; i++) digit[i] = 0; digit[0] = 1; } void print() { int i = MAX - 1; while (digit[i] == 0 && i >= 0) i--; while (i >= 0) { cout << (char)('0' + digit[i]); i--; } cout << endl; } void mul(int factor) { int i, carry = 0; for (i = 0; i < MAX; i++) { carry += digit[i] * factor; digit[i] = carry % 10; carry /= 10; } } void div(int dividend) { int tmp = 0, i = MAX - 1; while (digit[i] == 0 && i >= 0) i--; while (i >= 0) { tmp = tmp * 10 + digit[i]; digit[i] = 0; if (dividend <= tmp) { digit[i] = tmp / dividend; tmp %= dividend; } i--; } } int main() { int i, m, n, testCnt = 1; while (cin >> m >> n) { if (!m && !n) break; cout << "Test #" << testCnt++ << ":\n"; if (m < n) { cout << "0\n"; continue; } init(); for (i = 2; i <= m + n; i++) mul(i); mul(m - n+ 1); div(m + 1); print(); } return 0; }

A5.

/****************************************************************************** A5.Power Management Solved by pladene@bbs.whnet.edu.cn 问题：模拟题 算法: 散列 + 离散化处理 *******************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #define clr(a) memset(a, 0, sizeof(a)); int n, m, max_power; char equip_name[50000][33], tmp_name[33]; int power[50000], pos[2500], len[50000], hash[50000][30]; int w[33], start[2500], end[2500], total[5000], diff[5000], ans, p; void init() { clr(len); for (int i = 0; i <= 32; i++) w[i] = rand() % 50000+5000; } int get_hash_index(char name[]) { int l = strlen(name), j = 0; for(int i = 0; i < l; i++) j += name[i] * w[i]; return j % 50000; } void hash_insert(char name[], int index) { int i = get_hash_index(name); hash[i][len[i]++] = index; } int hash_retrieve(char name[]) { int i = get_hash_index(name); for(int j = 0; j < len[i]; j++) if (!strcmp(name,equip_name[hash[i][j]])) return hash[i][j]; return -1; } int bisearch(int x) { int mid, p = 0, q = 2 * m - 1; while (p <= q) { mid = (p + q) / 2; if (total[mid] == x) return mid; else if (total[mid] < x) p = mid + 1; else q = mid - 1; } return 0; } int main() { int i, j; init(); scanf("%d", &n); for (i = 0; i < n; i++) { while (getchar() != '['); j = 0; while ((equip_name[i][j++]=getchar()) != ']'); equip_name[i][j-1] = '\0'; scanf("%d", &power[i]); hash_insert(equip_name[i], i); } while (scanf("%d%d", &m, &max_power) == 2) { for (i = 0; i < m; i++) { while (getchar() != '['); j = 0; while ((tmp_name[j++]=getchar()) != ']'); tmp_name[j-1] = '\0'; pos[i] = hash_retrieve(tmp_name); scanf("%d%d", &start[i], &end[i]); total[2*i] = start[i]; total[2*i+1] = end[i]; } std::sort(total, total + 2 * m); clr(diff); // diff[i]表示在total[i]这个时刻power变化值，正表示增加， 负表示减少 for (i = 0; i < m; i++) { diff[bisearch(start[i])] += power[pos[i]]; diff[bisearch(end[i])] -= power[pos[i]]; } ans = p = 0; // 遍历total数组，找最大的power值 for (i = 0; i < 2 * m; i++) { p += diff[i]; if (p > ans) ans = p; if (p > max_power) break; } if (i < 2 * m) printf("The power will be out at time %d because the power is %d Watts and overloaded.\n",total[i], ans); else printf("The maximum power needed is %d Watts.\n",ans); } return 0; }

作者的话：//嘿嘿

    我12号传的那个rar（A5008@0412）里面的A3.exe有点小问题。上传之前我发现A3.cpp有点小问题（呵呵，少写了一个++），更改以后，忘记重新编译就传上来了，今天才发现。

    这次的这个版本跟12号的没有别的区别，就是把A3.cpp重新编译了一遍，生成了新的A3.exe