TEXT Graph Theory

介绍了图论中的基本概念。 邻接矩阵也可以做矩阵乘法！不带权的邻接矩阵的k次幂是任意两点间恰好经过k条边的路径数。按照这个思路，我们也可以求任意两点间恰好经过k条边的最短路。

TEXT Flood Fill

用于找无向图连通块的算法。介绍了一种Breadth-First Scanning实现，也就是去掉队列的BFS……

PROB The Castle

给一张房子的平面图，求房间数、最大的房间面积、自选一堵墙拆掉后的最大面积、拆掉了哪堵墙。

英文有些奇怪……choosing the module farthest to the west (and then, if still tied, farthest to the south)

farthest不是最远吗？然而这里指的是最近。

/* ID: chrt2001 PROG: castle LANG: C++ */ #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; const char dict[] = {'W', 'N', 'E', 'S'}; int M[51][51], comp[51][52], sz[2501]; int m, n, cnt; struct Node { int x, y; }; void bfs(int x0, int y0) { queue<Node> Q; sz[comp[y0][x0] = ++cnt] = 1; Q.push((Node){x0, y0}); Node u; while (!Q.empty()) { u = Q.front(); Q.pop(); for (int i = 0; i < 4; ++i) { Node v = (Node){u.x+dx[i], u.y+dy[i]}; if (~M[u.y][u.x] & (1<<i) && !comp[v.y][v.x]) { ++sz[comp[v.y][v.x] = cnt]; Q.push(v); } } } } int main() { freopen("castle.in", "r", stdin); freopen("castle.out", "w", stdout); scanf("%d %d", &m, &n); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &M[i][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (!comp[i][j]) bfs(j, i); int mx = 0, ans = 0, x, y, d; for (int j = 1; j <= m; ++j) for (int i = n; i >= 1; --i) { int c = comp[i][j]; mx = max(mx, sz[c]); for (int k = 1; k <= 2; ++k) { int c1 = comp[i+dy[k]][j+dx[k]]; if (M[i][j] & (1<<k) && c1 != c && c1 && sz[c]+sz[c1] > ans) { y = i; x = j; d = k; ans = sz[c]+sz[c1]; } } } printf("%d\n%d\n%d\n%d %d %c\n", cnt, mx, ans, y, x, dict[d]); return 0; }

PROB Ordered Fractions

求[0, 1]里所有既约分数，分母不超过N，按数值自小向大排列。

我写了一个简单的分数类，然后枚举。可以只把分子、分母互质的分数加入答案，我是全部丢给set去重。ANALYSIS里有一种非常棒的方法，但我不知道原理。把主要部分附在了后面。

/* ID: chrt2001 PROG: frac1 LANG: C++ */ #include <cstdio> #include <set> using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } struct Frac { int a, b; Frac(int x, int y) { int z = gcd(x, y); a = x/z; b = y/z; } bool operator<(const Frac& rhs) const { return (b*rhs.a-a*rhs.b)*b*rhs.b > 0; } }; set<Frac> S; int main() { freopen("frac1.in", "r", stdin); freopen("frac1.out", "w", stdout); int n; scanf("%d", &n); S.insert(Frac(0, 1)); S.insert(Frac(1, 1)); for (int i = 2; i <= n; ++i) for (int j = 1; j < i; ++j) S.insert(Frac(j, i)); for (set<Frac>::iterator ix = S.begin(); ix != S.end(); ++ix) printf("%d/%d\n", ix->a, ix->b); return 0; } // by Russ Cox /* print the fractions of denominator <= n between n1/d1 and n2/d2 */ void genfrac(int n1, int d1, int n2, int d2) { if(d1+d2 > n) /* cut off recursion */ return; genfrac(n1,d1, n1+n2,d1+d2); fprintf(fout, "%d/%d\n", n1+n2, d1+d2); genfrac(n1+n2,d1+d2, n2,d2); }

PROB Sorting a Three-Valued Sequence

用交换操作给一个每项值域为{1, 2, 3}的序列排序，求最小交换次数。前面讲贪心的TEXT讲解了这一问题。

实现上无须真的交换，参见ANALYSIS，但是我这样写了，算是实践一下“两个指针一扫”这种技术。

/* ID: chrt2001 PROG: sort3 LANG: C++ */ #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1000; int cnt, n, a[MAXN], l[3], r[3], tot[3]; void replace(int x, int y) { for (int i = l[x], j = l[y]; i < r[x] && j < r[y]; ++i) if (a[i] == y) { while (j < r[y] && a[j] != x) ++j; if (j != r[y]) { ++cnt; swap(a[i], a[j++]); } } } void replace(int x) { for (int i = 0, j = l[x]; i < n && j < r[x]; ++i) if ((i < l[x] || i >= r[x]) && a[i] == x) { while (j < r[x] && a[j] == x) ++j; if (j != r[x]) { ++cnt; swap(a[i], a[j++]); } } } int main() { freopen("sort3.in", "r", stdin); freopen("sort3.out", "w", stdout); scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); ++tot[--a[i]]; } r[0] = tot[0]; for (int i = 1; i < 3; ++i) r[i] = (l[i] = r[i-1]) + tot[i]; replace(0, 1); replace(1, 2); replace(2, 0); replace(0); replace(1); printf("%d\n", cnt); return 0; }

PROB Healthy Holsteins

在G个(1 <= G <= 15)V维(1 <= V <= 25)向量中选尽量少的向量，使它们的和的每一维分别大于一个指定数。

V=1的时候可以贪心，V=2时举了个反例。又因为G比较小，枚举子集再验证即可。由于要输出“字典序”最小的方案，用二进制数枚举就不太合适了。这里用位向量来构造，进行了一些改进，避免了重复枚举。

/* ID: chrt2001 PROG: holstein LANG: C++ */ #include <cstdio> #include <cstring> using namespace std; const int MAXV = 25, MAXG = 15; int n, m, best = 1<<30, ans, v[MAXV], f[MAXG][MAXV]; bool check(int s) { int sum[n]; memset(sum, 0, sizeof(sum)); for (int i = 0; i < m; ++i) if (s & (1<<i)) for (int j = 0; j < n; ++j) sum[j] += f[i][j]; for (int i = 0; i < n; ++i) if (sum[i] < v[i]) return false; return true; } void solve(int s, int b, int c) { if (c >= best) return; if (check(s)) { best = c; ans = s; return; } for (int i = b; i < m; ++i) solve(s|(1<<i), i+1, c+1); } int main() { freopen("holstein.in", "r", stdin); freopen("holstein.out", "w", stdout); scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &v[i]); scanf("%d", &m); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) scanf("%d", &f[i][j]); solve(0, 0, 0); printf("%d", best); for (int i = 0; i < m; ++i) if (ans & (1<<i)) printf(" %d", i+1); putchar('\n'); return 0; }

PROB Hamming Codes

求一个含N个(1 <= N <= 64)B维(1 <= B <= 8)位向量的集合，要求任意两个向量之间不同的维数不小于D(1 <= D <= 7)，且“字典序”最小。

很神奇……猜测可以贪心，于是试了试，AC了。ANALYSIS中给的是DFS，网上的题解也多用DFS，也有人注意到似乎贪心能通过。

注意到这个贪心和最小生成树的Kruskal算法很像，进而想到拟阵。和拟阵上找最大独立集的贪心算法本质相同，但它不是拟阵。比如，B=2，{00}和{01, 10}之间不满足交换性质。有空再来对拍。如果阅读这段文字的您找到反例或者能给出证明，请留言，欢迎讨论。

/* ID: chrt2001 PROG: hamming LANG: C++ */ // 贪心，正确性有待考证 #include <cstdio> using namespace std; const int MAX_N = 64; int b, d, S[MAX_N], top = 1; int hamming_dist(int x, int y) { int cnt = 0, z = x^y; for (int i = 0; i < b; ++i) if (z & (1<<i)) ++cnt; return cnt; } bool check(int x) { for (int i = 0; i < top; ++i) if (hamming_dist(S[i], x) < d) return false; return true; } int main() { freopen("hamming.in", "r", stdin); freopen("hamming.out", "w", stdout); int n; scanf("%d %d %d", &n, &b, &d); for (int i = 1; top < n && i < (1<<b); ++i) if (check(i)) S[top++] = i; if (top != n) return 0; for (int i = 0; i < top; ++i) { if (i % 10) putchar(' '); printf("%d", S[i]); if (i % 10 == 9 || i == top-1) putchar('\n'); } return 0; }

---

离开学不到两星期了，最近要搞搞文化课。 离IOI 2016 Round 2结束还有2h，加油！ CN OI, best OI !