<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nchar s[20][20];\nint d[20][20];\nqueue<int> q;\nint dx[] = {0, 0, 1, -1};\nint dy[] = {1, -1, 0, 0};\nbool in(int x, int y) {\n return 0 <= x && x < 10 && 0 <= y && y < 10;\n}\nint main() {\n freopen(\"buckets.in\", \"r\", stdin);\n freopen(\"buckets.out\", \"w\", stdout);\n for (int i = 0; i < 10; i++) {\n scanf(\"%s\", s[i]);\n }\n memset(d, -1, sizeof d);\n for (int i = 0; i < 10; i++) {\n for (int j = 0; j < 10; j++) {\n if (s[i][j] == 'L') {\n d[i][j] = 0;\n q.push(i);\n q.push(j);\n }\n }\n }\n while (q.size()) {\n int x = q.front();\n q.pop();\n int y = q.front();\n q.pop();\n for (int k = 0; k < 4; k++) {\n int nx = x + dx[k];\n int ny = y + dy[k];\n if (in(nx, ny) && d[nx][ny] == -1 &&s[nx][ny] != 'R') {\n d[nx][ny] = d[x][y] + 1;\n q.push(nx);\n q.push(ny);\n }\n }\n }\n for (int i = 0; i < 10; i++) {\n for (int j = 0; j < 10; j++) {\n if (s[i][j] == 'B') {\n printf(\"%d\\n\", d[i][j] - 1);\n }\n }\n }\n return 0;\n}\n<\/code><\/pre>\nB2<\/h2>\n#include <bits\/stdc++.h>\nusing namespace std;\nbool v[100020];\nint n, x, y;\nint main() {\n freopen(\"factory.in\", \"r\", stdin);\n freopen(\"factory.out\", \"w\", stdout);\n cin >> n;\n for (int i = 1; i < n; i++) {\n cin >> x >> y;\n v[x] = true;\n }\n int cnt = 0, choose;\n for (int i = 1; i <= n; i++) {\n if (!v[i]) {\n cnt++;\n choose = i;\n }\n }\n if (cnt == 1) {\n cout << choose << endl;\n } else {\n cout << -1 << endl;\n }\n}\n<\/code><\/pre>\nB3<\/h2>\nimport sys\nsys.stdin = open('evolution.in', 'r')\nsys.stdout = open('evolution.out', 'w')\nn = input()\ng = {}\ncnt = 0\na = []\nfor i in range(n):\n b = raw_input().split()[1:]\n for j in range(len(b)):\n if b[j] not in g:\n g[b[j]] = cnt\n cnt += 1\n b[j] = g[b[j]]\n a.append(set(b))\n\ne = [[] for i in range(cnt)]\nd = [0 for i in range(cnt)]\nfor i in range(n):\n for j in range(i):\n f = a[i] & a[j]\n g = a[i] ^ a[j]\n for x in f:\n for y in g:\n e[x].append(y)\n d[y] += 1\n\nq = []\nfor i in range(cnt):\n if d[i] == 0:\n q.append(i)\nwhile len(q):\n u = q.pop()\n for i in e[u]:\n d[i] -= 1\n if d[i] == 0:\n q.append(i)\n\nif sum(d) == 0:\n print 'yes'\nelse:\n print 'no'\n<\/code><\/pre>\nSilver<\/h1>\nS1<\/h2>\n#include <bits\/stdc++.h>\nusing namespace std;\nint n;\nint a[1020][1020];\nint b[1020][1020];\nchar c;\nvoid row(int i) {\n for (int j = 0; j < n; j++) {\n a[i][j] ^= 1;\n }\n}\nvoid column(int j) {\n for (int i = 0; i < n; i++) {\n a[i][j] ^= 1;\n }\n}\nbool gao(int x, int y) {\n\/\/ return true;\n a[x][y] ^= 1;\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n for (int di = 1; di <= 2 && i + di < n; di++) {\n for (int dj = 1; dj <= 2 && j + dj < n; dj++) {\n if ((a[i][j] ^ a[i][j + dj] ^ a[i + di][j] ^ a[i + di][j + dj]) == 1) {\n return false;\n }\n }\n }\n }\n }\n return true;\n}\nint main() {\n freopen(\"leftout.in\", \"r\", stdin);\n freopen(\"leftout.out\", \"w\", stdout);\n scanf(\"%d\", &n);\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n scanf(\" %c\", &c);\n if (c == 'L') {\n a[i][j] = 0;\n } else {\n a[i][j] = 1;\n }\n }\n }\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n b[i][j] = 1;\n }\n }\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n for (int di = 1; di <= 2 && i + di < n; di++) {\n for (int dj = 1; dj <= 2 && j + dj < n; dj++) {\n if ((a[i][j] ^ a[i][j + dj] ^ a[i + di][j] ^ a[i + di][j + dj]) == 0) {\n b[i][j] = 0;\n b[i][j + dj] = 0;\n b[i + di][j] = 0;\n b[i + di][j + dj] = 0;\n }\n }\n }\n }\n }\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n if (b[i][j] == 1) {\n if (gao(i, j)) {\n printf(\"%d %d\\n\", i + 1, j + 1);\n return 0;\n } else {\n printf(\"-1\\n\");\n return 0;\n }\n }\n }\n }\n printf(\"-1\\n\");\n return 0;\n}\n<\/code><\/pre>\nS2<\/h2>\n
\u8fd9\u4efd\u4ee3\u7801\u6709\u5de8\u5927\u7684\u9519\u8bef\uff0c\u4f46\u662f\u4f9d\u7136AC\u4e86\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n;\nstruct P{\n int x, y;\n P(int x = 0, int y = 0): x(x), y(y) {\n\n }\n void scan() {\n scanf(\"%d%d\", &x, &y);\n }\n};\nbool operator<(const P&a, const P&b) {\n return a.x < b.x || (a.x == b.x && a.y < b.y);\n}\nP operator-(const P&a, const P&b) {\n return P(a.x - b.x, a.y - b.y);\n}\nstruct L{\n int id;\n P a, b;\n void scan() {\n a.scan();\n b.scan();\n if (b < a) {\n swap(a, b);\n }\n }\n}a[1000020];\n\nstruct cmp\n{\n bool operator()(int u, int v)const{\n return a[u].a.y < a[v].a.y || (a[u].a.y == a[v].a.y && a[u].id < a[v].id);\n }\n};\n\n\nlong long det(P a, P b) {\n return (long long)a.x * b.y - (long long)b.x * a.y;\n}\nint sgn(long long x) {\n if (x < 0) {\n return -1;\n }\n if (x > 0) {\n return 1;\n }\n return 0;\n}\nbool judge(const L &u, const L &v) {\n int sgnva = sgn(det(v.a - u.a, u.b - u.a));\n int sgnvb = sgn(det(v.b - u.a, u.b - u.a));\n if (sgnva * sgnvb == 1) {\n return false;\n }\n int sgnua = sgn(det(u.a - v.a, v.b - v.a));\n int sgnub = sgn(det(u.b - v.a, v.b - v.a));\n if (sgnua * sgnub == 1) {\n return false;\n }\n return true;\n}\nset<int, cmp> s;\npair<int, int> e[200020];\nint work() {\n for (int i = 0; i < 2 * n; i++) {\n if (e[i].second > 0) {\n set<int>::iterator it = s.lower_bound(e[i].second);\n if (judge(a[e[i].second], a[*it])) {\n return e[i].second;\n }\n if (judge(a[e[i].second], a[*--it])) {\n return e[i].second;\n }\n s.insert(e[i].second);\n } else {\n set<int>::iterator it = s.lower_bound(-e[i].second);\n set<int>::iterator ti = it;\n ti--;\n if (judge(a[*ti], a[*it])) {\n return *ti;\n }\n s.erase(-e[i].second);\n }\n }\n return -1;\n}\nint main() {\n freopen(\"cowjump.in\", \"r\", stdin);\n freopen(\"cowjump.out\", \"w\", stdout);\n scanf(\"%d\", &n);\n for (int i = 1; i <= n; i++) {\n a[i].id = i;\n a[i].scan();\n e[2 * i - 2] = make_pair(a[i].a.x, +i);\n e[2 * i - 1] = make_pair(a[i].b.x, -i);\n }\n {\n a[n + 1].id = n + 1;\n a[n + 1].a = P(-1000000007, -1000000007);\n a[n + 1].b = P(1000000007, -1000000007);\n a[n + 2].id = n + 2;\n a[n + 2].a = P(-1000000007, 1000000007);\n a[n + 2].b = P(1000000007, 1000000007);\n s.insert(n + 1);\n s.insert(n + 2);\n }\n sort(e, e + 2 * n);\n int res = work();\n assert(res != -1);\n vector<int> inter;\n for (int i = 1; i <= n; i++) {\n if (i != res && judge(a[i], a[res])) {\n inter.push_back(i);\n }\n }\n if (inter.size() == 1) {\n printf(\"%d\\n\", min(inter[0], res));\n } else {\n printf(\"%d\\n\", res);\n }\n return 0;\n}\n<\/code><\/pre>\nS3<\/h2>\n#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nvector<int> a[100020];\nint xx[100020];\nint yy[100020];\nint v[100020];\nint maxx, minx;\nint maxy, miny;\nint ans;\nvoid dfs(int x) {\n if (v[x]) {\n return;\n }\n v[x] = true;\n maxx = max(maxx, xx[x]);\n minx = min(minx, xx[x]);\n maxy = max(maxy, yy[x]);\n miny = min(miny, yy[x]);\n for (int i = 0; i < a[x].size(); i++) {\n dfs(a[x][i]);\n }\n}\nint main() {\n freopen(\"fenceplan.in\", \"r\", stdin);\n freopen(\"fenceplan.out\", \"w\", stdout);\n scanf(\"%d%d\", &n, &m);\n for (int i = 1; i <= n; i++) {\n scanf(\"%d%d\", &xx[i], &yy[i]);\n }\n for (int i = 0; i < m; i++) {\n int x, y;\n scanf(\"%d%d\", &x, &y);\n a[x].push_back(y);\n a[y].push_back(x);\n }\n ans = 1e9;\n for (int i = 1; i <= n; i++) {\n if (!v[i]) {\n maxx = maxy = 0;\n minx = miny = 1e9;\n dfs(i);\n ans = min(ans, (maxx - minx + maxy - miny) * 2);\n }\n }\n printf(\"%d\\n\", ans);\n return 0;\n}\n<\/code><\/pre>\nGold<\/h1>\nG1<\/h2>\n
\u5bf9\u4e8ea[l + 1], a[l + 2], …, a[r] \u5171r-l\u4e2a
\n\u6240\u9700\u8981\u7684\u4ee3\u4ef7\u662f
\n(mx[l + 1][r] * (r – l) – (s[r] – s[l]))
\n\u8bbef[i][j]\u8868\u793a\u53ea\u8003\u8651\u524di\u4e2a\u7ec4\u86c7\uff0c\u7528\u4e86j\u79cd\u5927\u5c0f\u7684\u7f51
\n\uff08\u6ce8\u610f\u53ef\u4ee5\u6539\u53d8k\u6b21\u7f51\u7684\u5927\u5c0f\uff0c\u76f8\u5f53\u4e8e\u53ef\u4ee5\u7528k+1\u79cd\u4e0d\u540c\u7684\u7f51\u7684\u5927\u5c0f\u3002\uff09<\/p>\n
\u679a\u4e3e\u6700\u540e\u4e00\u6bb5\u7684\u8d77\u70b9\uff0c\u5047\u8bbe\u6700\u540e\u4e00\u6bb5\u662fa[k+1], a[k+2], …, a[i]
\n\u90a3\u4e48\u8f6c\u79fb\u662f f[i][j] = min(f[i][j], f[k][j – 1] + (mx[k + 1][i] * (i – k) – (s[i] – s[k])));<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nlong long f[420][420];\nlong long a[420];\nlong long mx[420][420];\nlong long s[420];\n\nint n, m;\nint main() {\n freopen(\"snakes.in\", \"r\", stdin);\n freopen(\"snakes.out\", \"w\", stdout);\n cin >> n >> m;\n m++;\n for (int i = 1; i <= n; i++) {\n cin >> a[i];\n s[i] = s[i - 1] + a[i];\n }\n for (int i = 1; i <= n; i++) {\n mx[i][i] = a[i];\n for (int j = i + 1; j <= n; j++) {\n mx[i][j] = max(mx[i][j - 1], a[j]);\n }\n }\n memset(f, 0x3f, sizeof f);\n f[0][0] = 0;\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= m; j++) {\n for (int k = 0; k < i; k++) {\n f[i][j] = min(f[i][j], f[k][j - 1] + (mx[k + 1][i] * (i - k) - (s[i] - s[k])));\n }\n }\n }\n cout << f[n][m] << endl;\n return 0;\n}\n<\/code><\/pre>\nG2<\/h2>\n
\u8fd9\u662f\u4e00\u4e2an\u4e2a\u70b9\u7684\u5b8c\u5168\u56fe
\n\u7528Prim\u7b97\u6cd5\u6c42\u6700\u5c0f\u751f\u6210\u6811\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(n^2)
\n\u8bb0\u5f55\u6700\u5c0f\u751f\u6210\u6811\u4e0a\u6240\u6709\u8fb9\u7684\u8fb9\u6743
\n\u8f93\u51fa\u6700\u5c0f\u751f\u6210\u6811\u7684\u7b2cm\u5927\u7684\u8fb9\u5373\u53ef<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nvector<pair<long long, pair<int, int> > >e;\nint f[10000];\nlong long d[10000];\nint p[10000];\nbool v[10000];\nlong long get(long long x, long long y) {\n if (x > y) {\n swap(x, y);\n }\n return ((2019201913 * x + 2019201949 * y) % 2019201997);\n}\n\nint main() {\n freopen(\"walk.in\", \"r\", stdin);\n freopen(\"walk.out\", \"w\", stdout);\n cin >> n >> m;\n memset(d, 0x3f, sizeof d);\n d[1] = 0;\n for (int i = 1; i <= n; i++) {\n long long mindis = 1e18;\n int minidx = -1;\n for (int j = 1; j <= n; j++) {\n if (!v[j]) {\n if (d[j] < mindis) {\n mindis = d[j];\n minidx = j;\n }\n }\n }\n v[minidx] = true;\n if (minidx != 1) {\n assert(p[minidx] != 0);\n\/\/ cerr << minidx << ' ' << p[minidx] << ' ' << d[minidx] << endl;\n e.push_back(make_pair(d[minidx], make_pair(minidx, p[minidx])));\n\/\/ cerr << minidx << ' ' << p[minidx] << ' ' << d[minidx] << endl;\n }\n for (int j = 1; j <= n; j++) {\n if (!v[j]) {\n long long dd = get(minidx, j);\n if (dd < d[j]) {\n d[j] = dd;\n p[j] = minidx;\n }\n }\n }\n }\n sort(e.begin(), e.end());\n assert(e.size() == n - 1);\n for (int i = 0; i < n - 1; i++) {\n\/\/ cerr << e[i].first << ' ' << e[i].second.first << ' ' << e[i].second.second << endl;\n }\n cout << e[n - m].first << endl;\n return 0;\n}\n<\/code><\/pre>\nG3<\/h2>\n
\u5047\u8bbe\u524dn\u4e2a\u6570\u5b57\u548c\u540en\u4e2a\u6570\u5b57\u4e0d\u4ea4\u6362
\n\u90a3\u4e48\u6bcf\u6b21\u4ea4\u63620\u548c1\u53ef\u4ee5\u8ba9\u9006\u5e8f\u5bf9\u4e2a\u6570+1\u6216\u8005-1
\n\u90a3\u4e48\u53ea\u9700\u8981\u8ba1\u7b97\u51fa\u524dn\u4e2a\u6570\u5b57\u9006\u5e8f\u5bf9\uff0c\u548c\u540en\u4e2a\u6570\u5b57\u9006\u5e8f\u5bf9\u7684\u4e2a\u6570\u5373\u53ef
\n\u7b54\u6848\u5373\u4e3a2\u4e2a\u7684\u5dee<\/p>\n
\u63a5\u4e0b\u6765\u8981\u8003\u8651\u4e24\u8fb90\u548c1\u7684\u4ea4\u6362
\n\u7528\u5de6\u8fb9\u7684\u4e00\u4e9b1\u6362\u53f3\u8fb9\u7684\u4e00\u4e9b0
\n\u6216\u8005\u662f
\n\u7528\u5de6\u8fb9\u7684\u4e00\u4e9b0\u6362\u53f3\u8fb9\u7684\u4e00\u4e9b1<\/p>\n
\u4e00\u5b9a\u662f\u5de6\u8fb9\u6700\u9760\u53f3\u7684\u51e0\u4e2a1\uff0c\u6362\u53f3\u8fb9\u6700\u9760\u5de6\u7684\u51e0\u4e2a0
\n\u5de6\u8fb9\u76841\u88ab\u6539\u6389\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a1\u548c\u53f3\u8fb9\u76840\u5f62\u6210\u7684\u9006\u5e8f\u5bf9\u6d88\u5931
\n\u5e76\u4e14\u56e0\u4e3a\u6539\u62100\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a0\u548c\u5de6\u8fb91\u5f62\u6210\u65b0\u7684\u9006\u5e8f\u5bf9<\/p>\n
\u53f3\u8fb9\u76840\u88ab\u6539\u6389\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a0\u548c\u5de6\u8fb9\u76841\u5f62\u6210\u7684\u9006\u5e8f\u5bf9\u6d88\u5931
\n\u5e76\u4e14\u56e0\u4e3a\u6539\u62101\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a1\u548c\u53f3\u8fb90\u5f62\u6210\u65b0\u7684\u9006\u5e8f\u5bf9<\/p>\n
\u679a\u4e3e\u6539\u4e86\u51e0\u4e2a\u5373\u53ef\u3002<\/p>\n
\u4e00\u5b9a\u662f\u5de6\u8fb9\u6700\u9760\u53f3\u7684\u51e0\u4e2a0\uff0c\u6362\u53f3\u8fb9\u6700\u9760\u5de6\u7684\u51e0\u4e2a1
\n\u5de6\u8fb9\u76840\u6539\u62101\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a0\u548c\u5de6\u8fb9\u76841\u5f62\u6210\u7684\u9006\u5e8f\u5bf9\u6d88\u5931\uff0c\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u9006\u5e8f\u5bf9
\n\u53f3\u8fb9\u76841\u6539\u62100\uff0c\u4f1a\u4f7f\u5f97\u8fd9\u4e2a1\u548c\u53f3\u8fb9\u76840\u5f62\u6210\u7684\u9006\u5e8f\u5bf9\u6d88\u5931\uff0c\u4e0d\u4f1a\u4ea7\u751f\u65b0\u7684\u9006\u5e8f\u5bf9<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nlong long ans;\nint a[200020];\nint n;\nvoid work1() {\n long long ansl = 0, cntl0 = 0;\n long long ansr = 0, cntr1 = 0;\n vector<pair<int, int> > L;\n vector<pair<int, int> > R;\n for (int i = n - 1; i >= 0; i--) {\n if (a[i] == 0) {\n cntl0++;\n } else {\n L.push_back(make_pair(i, cntl0));\n ansl += cntl0;\n }\n }\n for (int i = n; i < 2 * n; i++) {\n if (a[i] == 1) {\n cntr1++;\n } else {\n R.push_back(make_pair(i, cntr1));\n ansr += cntr1;\n }\n }\n ans = min(ans, abs(ansl - ansr));\n long long tmp = 0;\n for (int i = 0; i < L.size() && i < R.size(); i++) {\n tmp += (R[i].first - L[i].first);\n ansl -= L[i].second;\n ansl += L.size() - i + 1;\n ansr -= R[i].second;\n ansr += R.size() - i + 1;\n\/\/ cerr << ansl << ' ' << ansr << ' ' << tmp << endl;\n ans = min(ans, abs(ansl - ansr) + tmp);\n }\n return;\n}\nvoid work2() {\n long long ansl = 0, cntl1 = 0;\n long long ansr = 0, cntr0 = 0;\n vector<pair<int, int> > L;\n vector<pair<int, int> > R;\n for (int i = 0; i < n; i++) {\n if (a[i] == 0) {\n L.push_back(make_pair(i, cntl1));\n ansl += cntl1;\n } else {\n cntl1++;\n }\n }\n for (int i = 2 * n - 1; i >= n; i--) {\n if (a[i] == 1) {\n R.push_back(make_pair(i, cntr0));\n ansr += cntr0;\n } else {\n cntr0++;\n }\n }\n reverse(L.begin(), L.end());\n reverse(R.begin(), R.end());\n ans = min(ans, abs(ansl - ansr));\n\/\/ cerr << ansl << ' ' << ansr << endl;\n long long tmp = 0;\n for (int i = 0; i < L.size() && i < R.size(); i++) {\n tmp += (R[i].first - L[i].first);\n ansl -= L[i].second;\n ansr -= R[i].second;\n\/\/ cerr << ansl << ' ' << ansr << ' ' << tmp << endl;\n ans = min(ans, abs(ansl - ansr) + tmp);\n }\n return;\n}\nint main() {\n freopen(\"balance.in\", \"r\", stdin);\n freopen(\"balance.out\", \"w\", stdout);\n scanf(\"%d\", &n);\n for (int i = 0; i < 2 * n; i++) {\n scanf(\"%d\", &a[i]);\n }\n ans = 1e18;\n work1();\n work2();\n printf(\"%lldn\", ans);\n return 0;\n}\n<\/code><\/pre>\nPlatinum<\/h1>\nP1<\/h2>\n
\u628a\u56fe\u753b\u5728\u5e73\u9762\u4e0a\uff0cLCA\u3002<\/p>\n
\u6bcf\u4e2a\u70b9\u5de6\u4e0a\u89d2\u7684\u533a\u57df\u8868\u793a\u81ea\u5df1\u8fd9\u4e2a\u5b50\u6811<\/p>\n
\u4e4b\u6240\u4ee52\u4e2a\u77e9\u5f62\uff0c\u662f\u56e0\u4e3a\u4e00\u4e2a\u77e9\u5f62\u53ea\u80fd\u8986\u76d6 \u67d0\u4e2a\u70b9\u5230\u81ea\u5df1\u7956\u5148\u7684\u8def\u5f84
\n\u4efb\u610f2\u70b9\u4e4b\u95f4\u7684\u8def\u5f84\u8981\u75282\u4e2a \u77e9\u5f62\u8986\u76d6
\n\uff08x\u5230lca\uff0cy\u5230lca\uff0c\u4f46\u662f\u8fd9\u6837lca\u4f1a\u88ab\u8986\u76d6\u4e24\u6b21\uff0c\u9700\u8981\u5904\u7406\u4e00\u4e0b\uff09<\/p>\n
#include \"grader.h\"\n#include <bits\/stdc++.h>\nusing namespace std;\n\n\/*\nvoid addBox(int x1, int y1, int x2, int y2) {\n printf(\"addBox %d %d %d %dn\", x1, y1, x2, y2);\n}\n\nvoid setFarmLocation(int id, int x, int y) {\n printf(\"setFarmLocation %d %d %dn\", id, x, y);\n}\n*\/\n\nvector<int> a[100020];\nint f[100020][20];\nint d[100020];\nint xx[100020], xc;\nint yy[100020], yc;\nvoid dfs(int x, int y) {\n f[x][0] = y;\n d[x] = d[y] + 1;\n for (int i = 1; i < 20; i++) {\n f[x][i] = f[f[x][i - 1]][i - 1];\n }\n for (int i = 0; i < a[x].size(); i++) {\n if (a[x][i] != y) {\n dfs(a[x][i], x);\n }\n }\n}\n\nvoid dfs1(int x, int y) {\n xx[x] = ++xc;\n for (int i = 0; i < a[x].size(); i++) {\n if (a[x][i] != y) {\n dfs1(a[x][i], x);\n }\n }\n}\n\nvoid dfs2(int x, int y) {\n yy[x] = ++yc;\n setFarmLocation(x, xx[x], yy[x]);\n for (int i = a[x].size() - 1; i >= 0; i--) {\n if (a[x][i] != y) {\n dfs2(a[x][i], x);\n }\n }\n}\n\nvoid addRoad(int x, int y) {\n a[x].push_back(y);\n a[y].push_back(x);\n}\n\nvoid buildFarms() {\n dfs(0, -1);\n dfs1(0, -1);\n dfs2(0, -1);\n}\n\nvoid notifyFJ(int X, int Y) {\n if (d[X] < d[Y]) {\n swap(X, Y);\n }\n int x = X;\n int y = Y;\n int dd = d[x] - d[y];\n for (int i = 0; i < 20; i++) {\n if (dd >> i & 1) {\n x = f[x][i];\n }\n }\n if (x == y) {\n addBox(xx[x], yy[y], xx[X], yy[X]);\n return;\n }\n for (int i = 20 - 1; i >= 0; i--) {\n if (f[x][i] != f[y][i]) {\n x = f[x][i];\n y = f[y][i];\n }\n }\n addBox(xx[f[x][0]], yy[f[x][0]], xx[X], yy[X]);\n addBox(xx[y], yy[y], xx[Y], yy[Y]);\n}\n\n\/*\nint main() {\n addRoad(1, 2);\n addRoad(1, 3);\n addRoad(2, 4);\n addRoad(2, 5);\n addRoad(3, 6);\n addRoad(3, 7);\n buildFarms();\n notifyFJ(5, 6);\n notifyFJ(1, 7);\n}\n*\/\n\n<\/code><\/pre>\nP2<\/h2>\n
\u9010\u683c\u7684\u63d2\u5934DP
\n\u72b6\u6001\u6570\u6709132\u4e2a<\/p>\n
\u72b6\u6001\u5c31\u662f\u628a6\u4e2a\u70b9\u5206\u7ec4\uff0c\u7ec4\u4e0d\u80fd\u76f8\u4ea4
\n\u6bd4\u5982\u5206\u6210
\n1 2 1 2 3 3
\n\u662f\u4e0d\u884c\u7684\uff0c1\u548c2\u76f8\u4ea4\u4e86
\n\u4f46\u662f
\n1 2 1 3 1 4
\n\u662f\u53ef\u4ee5\u7684<\/p>\n
\u7136\u540e
\n30000 * 6 * 132\uff0c\u8fd8\u8981\u518d\u4e58\u4e00\u4e2a\u8f6c\u79fb\u7684\u590d\u6742\u5ea64
\n\u5927\u6982\u5c31\u662f\u679a\u4e3e\u6bcf\u4e2a\u70b9\u662f\u5426\u548c\uff0c\u5de6\u8fb9\uff0c\u4e0a\u8fb9\u8fde\u8d77\u6765
\n\u5982\u679c\u4e0d\u548c\u5de6\u8fb9\u8fde\u8fb9\uff0c\u9700\u8981\u6ce8\u610f\u5de6\u8fb9\u662f\u5426\u662f\u552f\u4e00\u4e00\u4e2a\uff08\u5426\u5219\u56fe\u5c31\u4e0d\u8fde\u901a\u4e86\uff09
\n\u5982\u679c\u548c\u5de6\u8fb9\u4e0a\u8fb9\u90fd\u8fde\u8fb9\uff0c\u9700\u8981\u6ce8\u610f\u4e0d\u8981\u51fa\u73af<\/p>\n
\u9884\u5904\u7406\u51fa\u6765132\u4e2a\u72b6\u6001\uff0c\u5728\u6bcf\u4e2a\uff086\u4e2a\uff09\u4f4d\u7f6e\uff0c\u7684\u6240\u6709\uff084\u4e2a\uff09\u8f6c\u79fb\u53ef\u80fd\uff0c\u8bb0\u4e0b\u6765
\n\u6240\u6709DP\u72b6\u6001\u90fd\u9700\u8981\u8bb0\u5f55\u6700\u5c0f\u4ee3\u4ef7\u548c\u65b9\u6848\u6570<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int mod = 1000000007;\nint n, m;\nint a[30020][9];\nint b[30020][9];\ntypedef long long ll;\nint c[8];\nlong long timecount = 0;\nvoid decode(int x) {\n for (int i = 0; i < m; i++) {\n c[i] = x >> (3 * i) & 7;\n timecount++;\n }\n}\nint visited[20], stamp;\nint mapped[20];\nint encode() {\n stamp++;\n int cnt = 0;\n int re = 0;\n for (int i = 0; i < m; i++) {\n if (visited[c[i]] != stamp) {\n visited[c[i]] = stamp;\n mapped[c[i]] = cnt++;\n c[i] = mapped[c[i]];\n } else {\n c[i] = mapped[c[i]];\n }\n re |= c[i] << (3 * i);\n }\n return re;\n}\npair<ll, int> add(pair<ll, int> a, pair<ll, int> b) {\n if (a.first == b.first) {\n return make_pair(a.first, (a.second + b.second) % mod);\n }\n if (a.first < b.first) {\n return a;\n }\n if (a.first > b.first) {\n return b;\n }\n assert(false);\n}\nint stateid[262145];\nint stateis[262145];\nint trans[132][6][4];\nint cnt = 0;\nnamespace qiachangshu {\n int a[10];\n bool ok() {\n for (int i = 0; i < m; i++) {\n for (int j = i + 1; j < m; j++) {\n for (int k = j + 1; k < m; k++) {\n for (int l = k + 1; l < m; l++) {\n if (a[i] == a[k] && a[j] == a[l] && a[i] != a[j]) {\n return false;\n }\n }\n }\n }\n }\n return true;\n }\n void dfs(int x, int y, int z) {\n if (x == m) {\n if (ok()) {\n stateid[z] = cnt;\n stateis[cnt] = z;\n cnt++;\n }\n } else {\n for (int i = 0; i <= y; i++) {\n a[x] = i;\n dfs(x + 1, max(i + 1, y), z | (i << (3 * x)));\n }\n }\n }\n}\npair<ll, int> f[132], g[132];\nvoid insert(int enc, pair<ll, int> d) {\n assert(stateid[enc] != -1);\n enc = stateid[enc];\n g[enc] = add(g[enc], d);\n}\n\nint main() {\n freopen(\"escape.in\", \"r\", stdin);\n freopen(\"escape.out\", \"w\", stdout);\n\n scanf(\"%d%d\", &n, &m);\n for (int i = 0; i < n; i++) {\n for (int j = 1; j < m; j++) {\n scanf(\"%d\", &a[i][j]);\n }\n }\n for (int j = 0; j < m; j++) {\n for (int i = 1; i < n; i++) {\n scanf(\"%d\", &b[i][j]);\n }\n }\n memset(stateid, -1, sizeof stateid);\n qiachangshu::dfs(0, 0, 0);\n for (int j = 0; j < m; j++) {\n for (int k = 0; k < cnt; k++) {\n {\/\/ no up, no left\n int cnt = 0;\n for (int l = 0; l < m; l++) {\n if ((stateis[k] >> (3 * l) & 7) == (stateis[k] >> (3 * j) & 7)) {\n cnt++;\n }\n }\n if (cnt > 1) {\n decode(stateis[k]);\n c[j] = 17;\n trans[k][j][0] = encode();\n } else {\n trans[k][j][0] = -1;\n }\n }\n {\/\/ no up, left\n trans[k][j][1] = stateis[k];\n }\n {\/\/ up, no left\n if (j > 0) {\n decode(stateis[k]);\n int cnt = 0;\n for (int l = 0; l < m; l++) {\n if (c[l] == c[j]) {\n cnt++;\n }\n }\n if (cnt > 1) {\n c[j] = c[j - 1];\n trans[k][j][2] = encode();\n } else {\n trans[k][j][2] = -1;\n }\n } else {\n trans[k][j][2] = -1;\n }\n }\n {\/\/ up, left\n if (j > 0) {\n decode(stateis[k]);\n if (c[j] != c[j - 1]) {\n int cj = c[j];\n for (int l = 0; l < m; l++) {\n if (c[l] == cj) {\n c[l] = c[j - 1];\n }\n }\n trans[k][j][3] = encode();\n } else {\n trans[k][j][3] = -1;\n }\n } else {\n trans[k][j][3] = -1;\n }\n }\n }\n }\n\n {\n for (int k = 0; k < cnt; k++) {\n f[k] = make_pair(1e18, 0);\n }\n f[0] = make_pair(0, 1);\n }\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n if (i == 0 && j == 0) {\n continue;\n }\n for (int k = 0; k < cnt; k++) {\n g[k] = make_pair(1e18, 0);\n }\n for (int k = 0; k < cnt; k++) {\n if (f[k].first == 1e18 || f[k].second == 0) {\n continue;\n }\n {\/\/ no up, no left\n if (trans[k][j][0] != -1) {\n insert(trans[k][j][0], f[k]);\n }\n }\n {\/\/ no up, left\n if (i > 0) {\n if (trans[k][j][1] != -1) {\n insert(trans[k][j][1], make_pair(f[k].first + b[i][j], f[k].second));\n }\n }\n }\n {\/\/ up, no left\n if (trans[k][j][2] != -1) {\n insert(trans[k][j][2], make_pair(f[k].first + a[i][j], f[k].second));\n }\n }\n {\/\/ up, left\n if (i > 0) {\n if (trans[k][j][3] != -1) {\n insert(trans[k][j][3], make_pair(f[k].first + a[i][j] + b[i][j], f[k].second));\n }\n }\n }\n }\n swap(f, g);\n }\n }\n cout << f[0].second << endl;\n\/\/ cerr << f[0].first << ' ' << f[0].second << endl;\n\/\/ cerr << \"TIME COUNT \" << timecount << endl;\n return 0;\n}\n<\/code><\/pre>\nP3<\/h2>\n
\u6ce8\u610f\u5230\u9ad8\u5ea6\u6ca1\u6709\u76f8\u540c\u7684
\n\u4ece\u4f4e\u5230\u9ad8\u4f9d\u6b21\u52a0\u5165\uff0c\u6bcf\u6b21\u5f62\u6210\u7684\u8fde\u901a\u533a\u57df\uff0c\u5c31\u662fvalley\u3002
\n\u4f46\u662f\u8fd9\u6837\u53ef\u80fd\u52a0\u51fa\u6765\u7684\u4e1c\u897f\u6709\u6d1e\uff0c\u600e\u4e48\u529e\u5462\u3002<\/p>\n
\u4ece\u9ad8\u5230\u4f4e\u8003\u8651\u6240\u6709\u4f9d\u6b21\u52a0\u5165\uff0c
\n\u611f\u89c9\u5c31\u50cf\u6d1e\u8d8a\u6765\u8d8a\u5927\uff0c\u7136\u540e\u67d0\u4e2a\u65f6\u523b\u5927\u5230\u548c\u8fb9\u754c\u8fde\u901a\uff0c\u5c31\u4e0d\u518d\u662f\u6d1e\u4e86\u3002
\n\u90a3\u4e48\u5728 \u5bfc\u81f4\u4ed6\u4e0d\u518d\u662f\u6d1e\u7684\u90a3\u4e00\u6b21 \u8bb0\u5f55\u4e0b\u8fd9\u4e2a\u6d1e\u7684\u5f00\u59cb\u65f6\u95f4<\/p>\n
\u8fd9\u6837\u5728\u4ece\u4f4e\u5230\u9ad8\u4f9d\u6b21\u52a0\u5165\u7684\u65f6\u5019\uff0c\u5982\u679c\u52a0\u5165\u4e86\u8fd9\u4e2a\u70b9\uff0c\u6211\u4eec\u5c31\u77e5\u9053
\n\u8fd9\u4e2a\u70b9\u4e3a\u6211\u4eec\u5e26\u6765\u4e86\u4e00\u4e2a\u6d1e\uff0c\u9700\u8981\u7b49\u5230 \u8fd9\u4e2a\u6d1e\u7684\u5f00\u59cb\u65f6\u95f4 \u4e4b\u540e
\n\uff08\u8fd9\u4e2a\u65f6\u5019\u8fd9\u4e2a\u6d1e\u5c31\u88ab\u586b\u6210\u5b9e\u5fc3\u7684\u4e86\uff09
\n\u518d\u7edf\u8ba1\u8fd9\u4e2avalley\u7684\u5927\u5c0f<\/p>\n
\u4f46\u662f\u8fd9\u6837\u6709\u4e00\u4e2a\u5fae\u5c0f\u7684bug\uff0c\u5c31\u662f\u53ef\u80fd\u6d1e\u4e2d\u6709\u6d1e
\n\u4e00\u4e2a\u8865\u4e01\u662f<\/p>\n
\u4e0d\u4ec5\u8981\u5728
\n\u67d0\u4e2a\u65f6\u523b\u5927\u5230\u548c\u8fb9\u754c\u8fde\u901a
\n\u8bb0\u5f55\u4e0b\u8fd9\u4e2a\u6d1e\u7684\u5f00\u59cb\u65f6\u95f4<\/p>\n
\u800c\u4e14\u8981\u5728\u5bfc\u81f4\u4e24\u4e2a\uff08\u6216\u80053\u4e2a\uff0c4\u4e2a\uff09\u5c0f\u6d1e\uff0c\u8fde\u901a\u8d77\u6765\u7684\u65f6\u5019
\n\u8bb0\u5f55\u4e0b\u6240\u6709\u6d1e\u65f6\u95f4\u4e2d\u7b2c\u4e8c\u5927\u7684
\n\uff08\u8fb9\u754c\u4e4b\u5916\u7684\u533a\u57df\u770b\u505a\u65e0\u9650\u5927\uff09<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\npair<int, pair<int, int> > b[1000020];\nint n;\nint a[751][751];\nint f[1000020];\nint c[1000020];\nint d[1000020];\nint w[751][751];\nbool v[751][751];\nint dx[] = {0, 0, -1, 1, -1, -1, 1, 1};\nint dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};\nint F(int x) {\n return f[x] != x ? f[x] = F(f[x]) : x;\n}\nbool U(int x, int y) {\n x = F(x);\n y = F(y);\n if (x != y) {\n f[y] = x;\n c[x] += c[y];\n d[x] = max(d[x], d[y]);\n return true;\n }\n return true;\n}\nbool in(int x, int y) {\n return 0 <= x && x < n && 0 <= y && y < n;\n}\nvoid print() {\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n printf(\"%d\", v[i][j]);\n }\n printf(\"n\");\n }\n}\nint main() {\n freopen(\"valleys.in\", \"r\", stdin);\n freopen(\"valleys.out\", \"w\", stdout);\n scanf(\"%d\", &n);\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n scanf(\"%d\", &a[i][j]);\n b[i * n + j] = make_pair(a[i][j], make_pair(i, j));\n }\n }\n sort(b, b + n * n);\n for (int i = 0; i <= n * n; i++) {\n f[i] = i;\n c[i] = 1;\n d[i] = 0;\n }\n memset(v, 0, sizeof v);\n for (int i = n * n - 1; i >= 0; i--) {\n v[b[i].second.first][b[i].second.second] = true;\n if (b[i].second.first == 0 || b[i].second.first == n - 1) {\n U(n * n, b[i].second.first * n + b[i].second.second);\n }\n if (b[i].second.second == 0 || b[i].second.second == n - 1) {\n U(n * n, b[i].second.first * n + b[i].second.second);\n }\n for (int k = 0; k < 8; k++) {\n int nx = b[i].second.first + dx[k];\n int ny = b[i].second.second + dy[k];\n if (in(nx, ny) && v[nx][ny] && F(nx * n + ny) == F(n * n)) {\n U(b[i].second.first * n + b[i].second.second, nx * n + ny);\n }\n }\n int ff = F(b[i].second.first * n + b[i].second.second);\n d[ff] = max(d[ff], i);\n if (ff != F(n * n)) {\n vector<int> pending;\n for (int k = 0; k < 8; k++) {\n int nx = b[i].second.first + dx[k];\n int ny = b[i].second.second + dy[k];\n if (in(nx, ny) && v[nx][ny]) {\n if (F(b[i].second.first * n + b[i].second.second) != F(nx * n + ny)) {\n pending.push_back(d[F(nx * n + ny)]);\n }\n U(b[i].second.first * n + b[i].second.second, nx * n + ny);\n }\n }\n assert(pending.size() <= 4);\n if (pending.size() >= 2) {\n sort(pending.begin(), pending.end());\n int &ref = w[b[i].second.first][b[i].second.second];\n ref = max(ref, pending[pending.size() - 2]);\n }\n } else {\n for (int k = 0; k < 8; k++) {\n int nx = b[i].second.first + dx[k];\n int ny = b[i].second.second + dy[k];\n if (in(nx, ny) && v[nx][ny] && F(nx * n + ny) != F(n * n)) {\n int &ref = w[b[i].second.first][b[i].second.second];\n ref = max(ref, d[F(nx * n + ny)]);\n U(b[i].second.first * n + b[i].second.second, nx * n + ny);\n }\n }\n }\n }\n\n for (int i = 0; i < n * n; i++) {\n f[i] = i;\n c[i] = 1;\n d[i] = w[i \/ n][i % n];\n\/\/ printf(\"%d %d %dn\", i \/ n, i % n, d[i]);\n }\n \/*\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n printf(\"%d \", w[i][j]);\n }\n printf(\"n\");\n }\n *\/\n memset(v, 0, sizeof v);\n long long ans = 0;\n for (int i = 0; i < n * n; i++) {\n v[b[i].second.first][b[i].second.second] = true;\n for (int k = 0; k < 4; k++) {\n int nx = b[i].second.first + dx[k];\n int ny = b[i].second.second + dy[k];\n if (in(nx, ny) && v[nx][ny]) {\n U(b[i].second.first * n + b[i].second.second, nx * n + ny);\n }\n }\n int ff = F(b[i].second.first * n + b[i].second.second);\n if (d[ff] <= i) {\n\/\/ cout << i << ' ' << c[ff] << ' ' << b[i].second.first << ' ' << b[i].second.second << endl;\n ans += c[ff];\n }\n }\n cout << ans << endl;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[4],"class_list":["post-166","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-usaco"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/166","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=166"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/166\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=166"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=166"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=166"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}