A Ginkgo Numbers

暴力枚举，略。

B Stylish

简单题，就是题意可能不是很好懂…

C One-Dimensional Cellular Automaton

听说是个不是很难的矩阵快速幂，略。

D Find the Outlier

高斯消元还原多项式，略。

E Sliding Block Puzzle

经典推箱子问题，略。除了代码长长长之外没啥特别值得提的地方。

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int dx[][2] = {{-1, -1}, {2, 2}, {0, 1}, {0, 1}}; const int dy[][2] = {{0, 1}, {0, 1}, {-1, -1}, {2, 2}}; const int ddx[] = {-1, 1, 0, 0}, ddy[] = {0, 0, -1, 1}; int n, m, dis[55][55][4], dis2[2][55][55]; char s[55][55]; queue<pair<int, int> > q; struct Node{ int x, y, dir, d; Node(int _x, int _y, int _dir, int _d): x(_x), y(_y), dir(_dir), d(_d){} bool operator < (const Node& nd) const{ return d > nd.d; } }; priority_queue<Node> pq; void bfs(int stx, int sty, int o){ q.emplace(stx, sty); memset(dis2[o], 0x3f, sizeof(dis2[o])); dis2[o][stx][sty] = 0; while (!q.empty()){ int x = q.front().first, y = q.front().second; q.pop(); int dd = dis2[o][x][y]; for (int i = 0, cx, cy; i < 4; ++i){ cx = x + ddx[i], cy = y + ddy[i]; if (s[cx][cy] == '*') continue; if (dis2[o][cx][cy] == INF) dis2[o][cx][cy] = dd + 1, q.emplace(cx, cy); } } } void dijkstra(){ while (!pq.empty()){ int x = pq.top().x, y = pq.top().y, dir = pq.top().dir; int dd = pq.top().d; pq.pop(); if (dd > dis[x][y][dir]) continue; // go one step int cx = x + ddx[dir], cy = y + ddy[dir]; if (dis[cx][cy][dir ^ 1] > dd + 1) dis[cx][cy][dir ^ 1] = dd + 1, pq.push(Node(cx, cy, dir ^ 1, dd + 1)); // to another direction s[x][y] = s[x][y + 1] = s[x + 1][y] = s[x + 1][y + 1] = '*'; bfs(x + dx[dir][0], y + dy[dir][0], 0); bfs(x + dx[dir][1], y + dy[dir][1], 1); s[x][y] = s[x][y + 1] = s[x + 1][y] = s[x + 1][y + 1] = '.'; for (int i = 0, cx1, cy1, cx0, cy0; i < 4; ++i){ cx0 = x + dx[i][0], cy0 = y + dy[i][0]; cx1 = x + dx[i][1], cy1 = y + dy[i][1]; if (s[cx0][cy0] != '*' && s[cx1][cy1] != '*'){ int res = INF; res = min(res, dis2[0][cx0][cy0] + dis2[1][cx1][cy1]); res = min(res, dis2[1][cx0][cy0] + dis2[0][cx1][cy1]); if (res < INF && dis[x][y][i] > dd + res) dis[x][y][i] = dd + res, pq.push(Node(x, y, i, dd + res)); } } } } int main(){ for (; ; ){ scanf("%d%d", &n, &m); if (!n && !m) break; for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); for (int i = 0; i <= m + 1; ++i) s[0][i] = s[n + 1][i] = '*'; for (int i = 0; i <= n + 1; ++i) s[i][0] = s[i][m + 1] = '*'; vector<pair<int, int> > vec; int bx = -1, by; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j){ if (s[i][j] == 'X' && bx == -1) bx = i, by = j; else if (s[i][j] == '.') vec.push_back(make_pair(i, j)); } if (bx == 1 && by == 1){ printf("0\n"); continue ; } memset(dis, 0x3f, sizeof(dis)); s[bx][by] = s[bx][by + 1] = s[bx + 1][by] = s[bx + 1][by + 1] = '*'; bfs(vec[0].first, vec[0].second, 0); bfs(vec[1].first, vec[1].second, 1); s[bx][by] = s[bx][by + 1] = s[bx + 1][by] = s[bx + 1][by + 1] = '.'; while (!pq.empty()) pq.pop(); for (int i = 0, cx1, cy1, cx0, cy0; i < 4; ++i){ cx0 = bx + dx[i][0], cy0 = by + dy[i][0]; cx1 = bx + dx[i][1], cy1 = by + dy[i][1]; if (s[cx0][cy0] != '*' && s[cx1][cy1] != '*'){ int res = INF; res = min(res, dis2[0][cx0][cy0] + dis2[1][cx1][cy1]); res = min(res, dis2[1][cx0][cy0] + dis2[0][cx1][cy1]); if (res < INF) dis[bx][by][i] = res, pq.push(Node(bx, by, i, res)); } } dijkstra(); int ans = min(dis[1][1][1], dis[1][1][3]); if (ans == INF) printf("-1\n"); else printf("%d\n", ans); } return 0; }

F Never Wait for Weights

带权并查集，略。

G Let There Be Light

听说是一个不很难的圆求交，略。

H Company Organization

题意：有 $n$ 个集合，$m$ 个限制。限制有 5 种（第 $i$ 个集合用 $X_i$ 表示）：

$X_i\subset X_j$$X_i=X_j$$X_i\ne X_j$$X_i\cap X_j=\varnothing$$X_i\cap X_j\ne \varnothing$

问最多能满足前多少个限制。

先二分，然后每次只要考虑前若干个限制是否能同时满足即可。

考虑维护“子集”以及“相交为空”这两种关系，以及记录每一个集合是否为空。先处理前两种限制，求出包含关系的传递闭包，然后再处理第四种限制，将 $X_i$ 和 $X_j$ 的“下游集合”（即同时是两者的子集的集合）标记为空集。

最后检查第三种限制和第五种限制，前者很容易判定，后者需要先判定 $X_i$ 或者 $X_j$ 是空集，然后找出是否存在 $X_k$ 和 $X_l$，使得 $X_k\cap X_l=\varnothing ,X_i\subset X_k,X_j\subset X_l$。这部分我不太会，只写了一个暴力，居然还比较快。

时间复杂度理论上是 $O(m{n}^2\log m)$，但可以通过。

#include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp) using namespace std; int read(){ int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } int n, m, cons[10005][3]; bool f[105][105], g[105][105], isempty[105]; bool check(int x){ memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); memset(isempty, 0, sizeof(isempty)); REP(i, 1, n) f[i][i] = true; REP(i, 1, x){ if (cons[i][0] <= 2) f[cons[i][1]][cons[i][2]] = true; if (cons[i][0] == 2) f[cons[i][2]][cons[i][1]] = true; } REP(k, 1, n) REP(i, 1, n) REP(j, 1, n) f[i][j] = f[i][j] || (f[i][k] && f[k][j]); REP(i, 1, x){ if (cons[i][0] == 4){ int u = cons[i][1], v = cons[i][2]; g[u][v] = g[v][u] = true; // 如果在这里预处理所有 g 的传递关系就会 TLE。 REP(j, 1, n) if (f[j][u] && f[j][v]) isempty[j] = true; } } REP(i, 1, x){ if (cons[i][0] == 3){ int u = cons[i][1], v = cons[i][2]; if (f[u][v] && f[v][u]) return false; if (isempty[u] && isempty[v]) return false; } else if (cons[i][0] == 5){ int u = cons[i][1], v = cons[i][2]; if (isempty[u] || isempty[v]) return false; REP(k, 1, n){ if (!f[u][k]) continue; REP(l, 1, n){ if (f[v][l] && g[k][l]) return false; } } } } return true; } void solve(){ int l = 1, r = m; while (l < r){ int mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid - 1; } printf("%d\n", l); } int main(){ for (; ; ){ n = read(), m = read(); if (!n && !m) break; REP(i, 1, m){ REP(j, 0, 2) cons[i][j] = read(); } solve(); } return 0; }

I Beautiful Spacing

简单二分，略。注意“最后一行可以不向右对齐”这个限制。

J Cubic Colonies

待补。。。

小结

比较神奇的一场。

H 这种找到最小限制的题目还是比较考验水平的。

I 这种卡上下界的写法还是要多多注意。