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;
}