Bronze
B1
#include <bits/stdc++.h>
using namespace std;
char s[20][20];
int d[20][20];
queue<int> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool in(int x, int y) {
return 0 <= x && x < 10 && 0 <= y && y < 10;
}
int main() {
freopen("buckets.in", "r", stdin);
freopen("buckets.out", "w", stdout);
for (int i = 0; i < 10; i++) {
scanf("%s", s[i]);
}
memset(d, -1, sizeof d);
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (s[i][j] == 'L') {
d[i][j] = 0;
q.push(i);
q.push(j);
}
}
}
while (q.size()) {
int x = q.front();
q.pop();
int y = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (in(nx, ny) && d[nx][ny] == -1 &&s[nx][ny] != 'R') {
d[nx][ny] = d[x][y] + 1;
q.push(nx);
q.push(ny);
}
}
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (s[i][j] == 'B') {
printf("%d\n", d[i][j] - 1);
}
}
}
return 0;
}
B2
#include <bits/stdc++.h>
using namespace std;
bool v[100020];
int n, x, y;
int main() {
freopen("factory.in", "r", stdin);
freopen("factory.out", "w", stdout);
cin >> n;
for (int i = 1; i < n; i++) {
cin >> x >> y;
v[x] = true;
}
int cnt = 0, choose;
for (int i = 1; i <= n; i++) {
if (!v[i]) {
cnt++;
choose = i;
}
}
if (cnt == 1) {
cout << choose << endl;
} else {
cout << -1 << endl;
}
}
B3
import sys
sys.stdin = open('evolution.in', 'r')
sys.stdout = open('evolution.out', 'w')
n = input()
g = {}
cnt = 0
a = []
for i in range(n):
b = raw_input().split()[1:]
for j in range(len(b)):
if b[j] not in g:
g[b[j]] = cnt
cnt += 1
b[j] = g[b[j]]
a.append(set(b))
e = [[] for i in range(cnt)]
d = [0 for i in range(cnt)]
for i in range(n):
for j in range(i):
f = a[i] & a[j]
g = a[i] ^ a[j]
for x in f:
for y in g:
e[x].append(y)
d[y] += 1
q = []
for i in range(cnt):
if d[i] == 0:
q.append(i)
while len(q):
u = q.pop()
for i in e[u]:
d[i] -= 1
if d[i] == 0:
q.append(i)
if sum(d) == 0:
print 'yes'
else:
print 'no'
Silver
S1
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1020][1020];
int b[1020][1020];
char c;
void row(int i) {
for (int j = 0; j < n; j++) {
a[i][j] ^= 1;
}
}
void column(int j) {
for (int i = 0; i < n; i++) {
a[i][j] ^= 1;
}
}
bool gao(int x, int y) {
// return true;
a[x][y] ^= 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int di = 1; di <= 2 && i + di < n; di++) {
for (int dj = 1; dj <= 2 && j + dj < n; dj++) {
if ((a[i][j] ^ a[i][j + dj] ^ a[i + di][j] ^ a[i + di][j + dj]) == 1) {
return false;
}
}
}
}
}
return true;
}
int main() {
freopen("leftout.in", "r", stdin);
freopen("leftout.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf(" %c", &c);
if (c == 'L') {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int di = 1; di <= 2 && i + di < n; di++) {
for (int dj = 1; dj <= 2 && j + dj < n; dj++) {
if ((a[i][j] ^ a[i][j + dj] ^ a[i + di][j] ^ a[i + di][j + dj]) == 0) {
b[i][j] = 0;
b[i][j + dj] = 0;
b[i + di][j] = 0;
b[i + di][j + dj] = 0;
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (b[i][j] == 1) {
if (gao(i, j)) {
printf("%d %d\n", i + 1, j + 1);
return 0;
} else {
printf("-1\n");
return 0;
}
}
}
}
printf("-1\n");
return 0;
}
S2
这份代码有巨大的错误,但是依然AC了。
#include <bits/stdc++.h>
using namespace std;
int n;
struct P{
int x, y;
P(int x = 0, int y = 0): x(x), y(y) {
}
void scan() {
scanf("%d%d", &x, &y);
}
};
bool operator<(const P&a, const P&b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
P operator-(const P&a, const P&b) {
return P(a.x - b.x, a.y - b.y);
}
struct L{
int id;
P a, b;
void scan() {
a.scan();
b.scan();
if (b < a) {
swap(a, b);
}
}
}a[1000020];
struct cmp
{
bool operator()(int u, int v)const{
return a[u].a.y < a[v].a.y || (a[u].a.y == a[v].a.y && a[u].id < a[v].id);
}
};
long long det(P a, P b) {
return (long long)a.x * b.y - (long long)b.x * a.y;
}
int sgn(long long x) {
if (x < 0) {
return -1;
}
if (x > 0) {
return 1;
}
return 0;
}
bool judge(const L &u, const L &v) {
int sgnva = sgn(det(v.a - u.a, u.b - u.a));
int sgnvb = sgn(det(v.b - u.a, u.b - u.a));
if (sgnva * sgnvb == 1) {
return false;
}
int sgnua = sgn(det(u.a - v.a, v.b - v.a));
int sgnub = sgn(det(u.b - v.a, v.b - v.a));
if (sgnua * sgnub == 1) {
return false;
}
return true;
}
set<int, cmp> s;
pair<int, int> e[200020];
int work() {
for (int i = 0; i < 2 * n; i++) {
if (e[i].second > 0) {
set<int>::iterator it = s.lower_bound(e[i].second);
if (judge(a[e[i].second], a[*it])) {
return e[i].second;
}
if (judge(a[e[i].second], a[*--it])) {
return e[i].second;
}
s.insert(e[i].second);
} else {
set<int>::iterator it = s.lower_bound(-e[i].second);
set<int>::iterator ti = it;
ti--;
if (judge(a[*ti], a[*it])) {
return *ti;
}
s.erase(-e[i].second);
}
}
return -1;
}
int main() {
freopen("cowjump.in", "r", stdin);
freopen("cowjump.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
a[i].id = i;
a[i].scan();
e[2 * i - 2] = make_pair(a[i].a.x, +i);
e[2 * i - 1] = make_pair(a[i].b.x, -i);
}
{
a[n + 1].id = n + 1;
a[n + 1].a = P(-1000000007, -1000000007);
a[n + 1].b = P(1000000007, -1000000007);
a[n + 2].id = n + 2;
a[n + 2].a = P(-1000000007, 1000000007);
a[n + 2].b = P(1000000007, 1000000007);
s.insert(n + 1);
s.insert(n + 2);
}
sort(e, e + 2 * n);
int res = work();
assert(res != -1);
vector<int> inter;
for (int i = 1; i <= n; i++) {
if (i != res && judge(a[i], a[res])) {
inter.push_back(i);
}
}
if (inter.size() == 1) {
printf("%d\n", min(inter[0], res));
} else {
printf("%d\n", res);
}
return 0;
}
S3
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[100020];
int xx[100020];
int yy[100020];
int v[100020];
int maxx, minx;
int maxy, miny;
int ans;
void dfs(int x) {
if (v[x]) {
return;
}
v[x] = true;
maxx = max(maxx, xx[x]);
minx = min(minx, xx[x]);
maxy = max(maxy, yy[x]);
miny = min(miny, yy[x]);
for (int i = 0; i < a[x].size(); i++) {
dfs(a[x][i]);
}
}
int main() {
freopen("fenceplan.in", "r", stdin);
freopen("fenceplan.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
}
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
ans = 1e9;
for (int i = 1; i <= n; i++) {
if (!v[i]) {
maxx = maxy = 0;
minx = miny = 1e9;
dfs(i);
ans = min(ans, (maxx - minx + maxy - miny) * 2);
}
}
printf("%d\n", ans);
return 0;
}
Gold
G1
对于a[l + 1], a[l + 2], …, a[r] 共r-l个
所需要的代价是
(mx[l + 1][r] * (r – l) – (s[r] – s[l]))
设f[i][j]表示只考虑前i个组蛇,用了j种大小的网
(注意可以改变k次网的大小,相当于可以用k+1种不同的网的大小。)
枚举最后一段的起点,假设最后一段是a[k+1], a[k+2], …, a[i]
那么转移是 f[i][j] = min(f[i][j], f[k][j – 1] + (mx[k + 1][i] * (i – k) – (s[i] – s[k])));
#include <bits/stdc++.h>
using namespace std;
long long f[420][420];
long long a[420];
long long mx[420][420];
long long s[420];
int n, m;
int main() {
freopen("snakes.in", "r", stdin);
freopen("snakes.out", "w", stdout);
cin >> n >> m;
m++;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
mx[i][i] = a[i];
for (int j = i + 1; j <= n; j++) {
mx[i][j] = max(mx[i][j - 1], a[j]);
}
}
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < i; k++) {
f[i][j] = min(f[i][j], f[k][j - 1] + (mx[k + 1][i] * (i - k) - (s[i] - s[k])));
}
}
}
cout << f[n][m] << endl;
return 0;
}
G2
这是一个n个点的完全图
用Prim算法求最小生成树,时间复杂度O(n^2)
记录最小生成树上所有边的边权
输出最小生成树的第m大的边即可
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<long long, pair<int, int> > >e;
int f[10000];
long long d[10000];
int p[10000];
bool v[10000];
long long get(long long x, long long y) {
if (x > y) {
swap(x, y);
}
return ((2019201913 * x + 2019201949 * y) % 2019201997);
}
int main() {
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
cin >> n >> m;
memset(d, 0x3f, sizeof d);
d[1] = 0;
for (int i = 1; i <= n; i++) {
long long mindis = 1e18;
int minidx = -1;
for (int j = 1; j <= n; j++) {
if (!v[j]) {
if (d[j] < mindis) {
mindis = d[j];
minidx = j;
}
}
}
v[minidx] = true;
if (minidx != 1) {
assert(p[minidx] != 0);
// cerr << minidx << ' ' << p[minidx] << ' ' << d[minidx] << endl;
e.push_back(make_pair(d[minidx], make_pair(minidx, p[minidx])));
// cerr << minidx << ' ' << p[minidx] << ' ' << d[minidx] << endl;
}
for (int j = 1; j <= n; j++) {
if (!v[j]) {
long long dd = get(minidx, j);
if (dd < d[j]) {
d[j] = dd;
p[j] = minidx;
}
}
}
}
sort(e.begin(), e.end());
assert(e.size() == n - 1);
for (int i = 0; i < n - 1; i++) {
// cerr << e[i].first << ' ' << e[i].second.first << ' ' << e[i].second.second << endl;
}
cout << e[n - m].first << endl;
return 0;
}
G3
假设前n个数字和后n个数字不交换
那么每次交换0和1可以让逆序对个数+1或者-1
那么只需要计算出前n个数字逆序对,和后n个数字逆序对的个数即可
答案即为2个的差
接下来要考虑两边0和1的交换
用左边的一些1换右边的一些0
或者是
用左边的一些0换右边的一些1
一定是左边最靠右的几个1,换右边最靠左的几个0
左边的1被改掉,会使得这个1和右边的0形成的逆序对消失
并且因为改成0,会使得这个0和左边1形成新的逆序对
右边的0被改掉,会使得这个0和左边的1形成的逆序对消失
并且因为改成1,会使得这个1和右边0形成新的逆序对
枚举改了几个即可。
一定是左边最靠右的几个0,换右边最靠左的几个1
左边的0改成1,会使得这个0和左边的1形成的逆序对消失,不会产生新的逆序对
右边的1改成0,会使得这个1和右边的0形成的逆序对消失,不会产生新的逆序对
#include <bits/stdc++.h>
using namespace std;
long long ans;
int a[200020];
int n;
void work1() {
long long ansl = 0, cntl0 = 0;
long long ansr = 0, cntr1 = 0;
vector<pair<int, int> > L;
vector<pair<int, int> > R;
for (int i = n - 1; i >= 0; i--) {
if (a[i] == 0) {
cntl0++;
} else {
L.push_back(make_pair(i, cntl0));
ansl += cntl0;
}
}
for (int i = n; i < 2 * n; i++) {
if (a[i] == 1) {
cntr1++;
} else {
R.push_back(make_pair(i, cntr1));
ansr += cntr1;
}
}
ans = min(ans, abs(ansl - ansr));
long long tmp = 0;
for (int i = 0; i < L.size() && i < R.size(); i++) {
tmp += (R[i].first - L[i].first);
ansl -= L[i].second;
ansl += L.size() - i + 1;
ansr -= R[i].second;
ansr += R.size() - i + 1;
// cerr << ansl << ' ' << ansr << ' ' << tmp << endl;
ans = min(ans, abs(ansl - ansr) + tmp);
}
return;
}
void work2() {
long long ansl = 0, cntl1 = 0;
long long ansr = 0, cntr0 = 0;
vector<pair<int, int> > L;
vector<pair<int, int> > R;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
L.push_back(make_pair(i, cntl1));
ansl += cntl1;
} else {
cntl1++;
}
}
for (int i = 2 * n - 1; i >= n; i--) {
if (a[i] == 1) {
R.push_back(make_pair(i, cntr0));
ansr += cntr0;
} else {
cntr0++;
}
}
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
ans = min(ans, abs(ansl - ansr));
// cerr << ansl << ' ' << ansr << endl;
long long tmp = 0;
for (int i = 0; i < L.size() && i < R.size(); i++) {
tmp += (R[i].first - L[i].first);
ansl -= L[i].second;
ansr -= R[i].second;
// cerr << ansl << ' ' << ansr << ' ' << tmp << endl;
ans = min(ans, abs(ansl - ansr) + tmp);
}
return;
}
int main() {
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < 2 * n; i++) {
scanf("%d", &a[i]);
}
ans = 1e18;
work1();
work2();
printf("%lldn", ans);
return 0;
}
Platinum
P1
把图画在平面上,LCA。
每个点左上角的区域表示自己这个子树
之所以2个矩形,是因为一个矩形只能覆盖 某个点到自己祖先的路径
任意2点之间的路径要用2个 矩形覆盖
(x到lca,y到lca,但是这样lca会被覆盖两次,需要处理一下)
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
/*
void addBox(int x1, int y1, int x2, int y2) {
printf("addBox %d %d %d %dn", x1, y1, x2, y2);
}
void setFarmLocation(int id, int x, int y) {
printf("setFarmLocation %d %d %dn", id, x, y);
}
*/
vector<int> a[100020];
int f[100020][20];
int d[100020];
int xx[100020], xc;
int yy[100020], yc;
void dfs(int x, int y) {
f[x][0] = y;
d[x] = d[y] + 1;
for (int i = 1; i < 20; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = 0; i < a[x].size(); i++) {
if (a[x][i] != y) {
dfs(a[x][i], x);
}
}
}
void dfs1(int x, int y) {
xx[x] = ++xc;
for (int i = 0; i < a[x].size(); i++) {
if (a[x][i] != y) {
dfs1(a[x][i], x);
}
}
}
void dfs2(int x, int y) {
yy[x] = ++yc;
setFarmLocation(x, xx[x], yy[x]);
for (int i = a[x].size() - 1; i >= 0; i--) {
if (a[x][i] != y) {
dfs2(a[x][i], x);
}
}
}
void addRoad(int x, int y) {
a[x].push_back(y);
a[y].push_back(x);
}
void buildFarms() {
dfs(0, -1);
dfs1(0, -1);
dfs2(0, -1);
}
void notifyFJ(int X, int Y) {
if (d[X] < d[Y]) {
swap(X, Y);
}
int x = X;
int y = Y;
int dd = d[x] - d[y];
for (int i = 0; i < 20; i++) {
if (dd >> i & 1) {
x = f[x][i];
}
}
if (x == y) {
addBox(xx[x], yy[y], xx[X], yy[X]);
return;
}
for (int i = 20 - 1; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
addBox(xx[f[x][0]], yy[f[x][0]], xx[X], yy[X]);
addBox(xx[y], yy[y], xx[Y], yy[Y]);
}
/*
int main() {
addRoad(1, 2);
addRoad(1, 3);
addRoad(2, 4);
addRoad(2, 5);
addRoad(3, 6);
addRoad(3, 7);
buildFarms();
notifyFJ(5, 6);
notifyFJ(1, 7);
}
*/
P2
逐格的插头DP
状态数有132个
状态就是把6个点分组,组不能相交
比如分成
1 2 1 2 3 3
是不行的,1和2相交了
但是
1 2 1 3 1 4
是可以的
然后
30000 * 6 * 132,还要再乘一个转移的复杂度4
大概就是枚举每个点是否和,左边,上边连起来
如果不和左边连边,需要注意左边是否是唯一一个(否则图就不连通了)
如果和左边上边都连边,需要注意不要出环
预处理出来132个状态,在每个(6个)位置,的所有(4个)转移可能,记下来
所有DP状态都需要记录最小代价和方案数
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, m;
int a[30020][9];
int b[30020][9];
typedef long long ll;
int c[8];
long long timecount = 0;
void decode(int x) {
for (int i = 0; i < m; i++) {
c[i] = x >> (3 * i) & 7;
timecount++;
}
}
int visited[20], stamp;
int mapped[20];
int encode() {
stamp++;
int cnt = 0;
int re = 0;
for (int i = 0; i < m; i++) {
if (visited[c[i]] != stamp) {
visited[c[i]] = stamp;
mapped[c[i]] = cnt++;
c[i] = mapped[c[i]];
} else {
c[i] = mapped[c[i]];
}
re |= c[i] << (3 * i);
}
return re;
}
pair<ll, int> add(pair<ll, int> a, pair<ll, int> b) {
if (a.first == b.first) {
return make_pair(a.first, (a.second + b.second) % mod);
}
if (a.first < b.first) {
return a;
}
if (a.first > b.first) {
return b;
}
assert(false);
}
int stateid[262145];
int stateis[262145];
int trans[132][6][4];
int cnt = 0;
namespace qiachangshu {
int a[10];
bool ok() {
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
for (int k = j + 1; k < m; k++) {
for (int l = k + 1; l < m; l++) {
if (a[i] == a[k] && a[j] == a[l] && a[i] != a[j]) {
return false;
}
}
}
}
}
return true;
}
void dfs(int x, int y, int z) {
if (x == m) {
if (ok()) {
stateid[z] = cnt;
stateis[cnt] = z;
cnt++;
}
} else {
for (int i = 0; i <= y; i++) {
a[x] = i;
dfs(x + 1, max(i + 1, y), z | (i << (3 * x)));
}
}
}
}
pair<ll, int> f[132], g[132];
void insert(int enc, pair<ll, int> d) {
assert(stateid[enc] != -1);
enc = stateid[enc];
g[enc] = add(g[enc], d);
}
int main() {
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
scanf("%d", &a[i][j]);
}
}
for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
scanf("%d", &b[i][j]);
}
}
memset(stateid, -1, sizeof stateid);
qiachangshu::dfs(0, 0, 0);
for (int j = 0; j < m; j++) {
for (int k = 0; k < cnt; k++) {
{// no up, no left
int cnt = 0;
for (int l = 0; l < m; l++) {
if ((stateis[k] >> (3 * l) & 7) == (stateis[k] >> (3 * j) & 7)) {
cnt++;
}
}
if (cnt > 1) {
decode(stateis[k]);
c[j] = 17;
trans[k][j][0] = encode();
} else {
trans[k][j][0] = -1;
}
}
{// no up, left
trans[k][j][1] = stateis[k];
}
{// up, no left
if (j > 0) {
decode(stateis[k]);
int cnt = 0;
for (int l = 0; l < m; l++) {
if (c[l] == c[j]) {
cnt++;
}
}
if (cnt > 1) {
c[j] = c[j - 1];
trans[k][j][2] = encode();
} else {
trans[k][j][2] = -1;
}
} else {
trans[k][j][2] = -1;
}
}
{// up, left
if (j > 0) {
decode(stateis[k]);
if (c[j] != c[j - 1]) {
int cj = c[j];
for (int l = 0; l < m; l++) {
if (c[l] == cj) {
c[l] = c[j - 1];
}
}
trans[k][j][3] = encode();
} else {
trans[k][j][3] = -1;
}
} else {
trans[k][j][3] = -1;
}
}
}
}
{
for (int k = 0; k < cnt; k++) {
f[k] = make_pair(1e18, 0);
}
f[0] = make_pair(0, 1);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) {
continue;
}
for (int k = 0; k < cnt; k++) {
g[k] = make_pair(1e18, 0);
}
for (int k = 0; k < cnt; k++) {
if (f[k].first == 1e18 || f[k].second == 0) {
continue;
}
{// no up, no left
if (trans[k][j][0] != -1) {
insert(trans[k][j][0], f[k]);
}
}
{// no up, left
if (i > 0) {
if (trans[k][j][1] != -1) {
insert(trans[k][j][1], make_pair(f[k].first + b[i][j], f[k].second));
}
}
}
{// up, no left
if (trans[k][j][2] != -1) {
insert(trans[k][j][2], make_pair(f[k].first + a[i][j], f[k].second));
}
}
{// up, left
if (i > 0) {
if (trans[k][j][3] != -1) {
insert(trans[k][j][3], make_pair(f[k].first + a[i][j] + b[i][j], f[k].second));
}
}
}
}
swap(f, g);
}
}
cout << f[0].second << endl;
// cerr << f[0].first << ' ' << f[0].second << endl;
// cerr << "TIME COUNT " << timecount << endl;
return 0;
}
P3
注意到高度没有相同的
从低到高依次加入,每次形成的连通区域,就是valley。
但是这样可能加出来的东西有洞,怎么办呢。
从高到低考虑所有依次加入,
感觉就像洞越来越大,然后某个时刻大到和边界连通,就不再是洞了。
那么在 导致他不再是洞的那一次 记录下这个洞的开始时间
这样在从低到高依次加入的时候,如果加入了这个点,我们就知道
这个点为我们带来了一个洞,需要等到 这个洞的开始时间 之后
(这个时候这个洞就被填成实心的了)
再统计这个valley的大小
但是这样有一个微小的bug,就是可能洞中有洞
一个补丁是
不仅要在
某个时刻大到和边界连通
记录下这个洞的开始时间
而且要在导致两个(或者3个,4个)小洞,连通起来的时候
记录下所有洞时间中第二大的
(边界之外的区域看做无限大)
#include <bits/stdc++.h>
using namespace std;
pair<int, pair<int, int> > b[1000020];
int n;
int a[751][751];
int f[1000020];
int c[1000020];
int d[1000020];
int w[751][751];
bool v[751][751];
int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
int F(int x) {
return f[x] != x ? f[x] = F(f[x]) : x;
}
bool U(int x, int y) {
x = F(x);
y = F(y);
if (x != y) {
f[y] = x;
c[x] += c[y];
d[x] = max(d[x], d[y]);
return true;
}
return true;
}
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n;
}
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d", v[i][j]);
}
printf("n");
}
}
int main() {
freopen("valleys.in", "r", stdin);
freopen("valleys.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
b[i * n + j] = make_pair(a[i][j], make_pair(i, j));
}
}
sort(b, b + n * n);
for (int i = 0; i <= n * n; i++) {
f[i] = i;
c[i] = 1;
d[i] = 0;
}
memset(v, 0, sizeof v);
for (int i = n * n - 1; i >= 0; i--) {
v[b[i].second.first][b[i].second.second] = true;
if (b[i].second.first == 0 || b[i].second.first == n - 1) {
U(n * n, b[i].second.first * n + b[i].second.second);
}
if (b[i].second.second == 0 || b[i].second.second == n - 1) {
U(n * n, b[i].second.first * n + b[i].second.second);
}
for (int k = 0; k < 8; k++) {
int nx = b[i].second.first + dx[k];
int ny = b[i].second.second + dy[k];
if (in(nx, ny) && v[nx][ny] && F(nx * n + ny) == F(n * n)) {
U(b[i].second.first * n + b[i].second.second, nx * n + ny);
}
}
int ff = F(b[i].second.first * n + b[i].second.second);
d[ff] = max(d[ff], i);
if (ff != F(n * n)) {
vector<int> pending;
for (int k = 0; k < 8; k++) {
int nx = b[i].second.first + dx[k];
int ny = b[i].second.second + dy[k];
if (in(nx, ny) && v[nx][ny]) {
if (F(b[i].second.first * n + b[i].second.second) != F(nx * n + ny)) {
pending.push_back(d[F(nx * n + ny)]);
}
U(b[i].second.first * n + b[i].second.second, nx * n + ny);
}
}
assert(pending.size() <= 4);
if (pending.size() >= 2) {
sort(pending.begin(), pending.end());
int &ref = w[b[i].second.first][b[i].second.second];
ref = max(ref, pending[pending.size() - 2]);
}
} else {
for (int k = 0; k < 8; k++) {
int nx = b[i].second.first + dx[k];
int ny = b[i].second.second + dy[k];
if (in(nx, ny) && v[nx][ny] && F(nx * n + ny) != F(n * n)) {
int &ref = w[b[i].second.first][b[i].second.second];
ref = max(ref, d[F(nx * n + ny)]);
U(b[i].second.first * n + b[i].second.second, nx * n + ny);
}
}
}
}
for (int i = 0; i < n * n; i++) {
f[i] = i;
c[i] = 1;
d[i] = w[i / n][i % n];
// printf("%d %d %dn", i / n, i % n, d[i]);
}
/*
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", w[i][j]);
}
printf("n");
}
*/
memset(v, 0, sizeof v);
long long ans = 0;
for (int i = 0; i < n * n; i++) {
v[b[i].second.first][b[i].second.second] = true;
for (int k = 0; k < 4; k++) {
int nx = b[i].second.first + dx[k];
int ny = b[i].second.second + dy[k];
if (in(nx, ny) && v[nx][ny]) {
U(b[i].second.first * n + b[i].second.second, nx * n + ny);
}
}
int ff = F(b[i].second.first * n + b[i].second.second);
if (d[ff] <= i) {
// cout << i << ' ' << c[ff] << ' ' << b[i].second.first << ' ' << b[i].second.second << endl;
ans += c[ff];
}
}
cout << ans << endl;
}