A – Photo of The Sky

比较显然，我们需要选两个点集，最后贡献就是两个点集的极差积。排个序，并且把每个长度为 \(n\) 的区间都给做一遍即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ai[MAX_N << 1];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= (n << 1); i++)
        scanf("%d", &ai[i]);
    sort(ai + 1, ai + 1 + (n << 1));
    long long ans = 1e18;
    for (int i = 1; i <= n; i++)
        ans = min(ans, 1LL * (ai[i + n - 1] - ai[i]) * (ai[n << 1] - (i == 1 ? ai[n + 1] : ai[1])));
    printf("%lld\n", ans);
    return 0;
}

B – Chemical table

妈的想了半天最后发现用二分图来做，气死我了。

考虑行号连至列号，画出一个二分图。思考两条边组成的三元组的意义，比如说两个左部点 \(u, v\)、一个右部点 \(w\)，发现右部点可以将 \(u, v\) 所连接的右部点做到一个「共享」的功能，因为对于一行的点 \(u, v\) 来说，\(u, v\) 的列信息（相当于一个 bitset）是可以并起来的，所以一个二分图连通块可以使得整个连通块 work。

答案就是连通块个数减去一个 \(1\)。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

typedef pair<int, int> pii;

int n, m, q, sumx[MAX_N], sumy[MAX_N], color[MAX_N];
pii pts[MAX_N];
vector<int> G[MAX_N];

void dfs(int u, int org)
{
    color[u] = org;
    for (auto v : G[u])
        if (color[v] == 0)
            dfs(v, org);
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1, u, v; i <= q; i++)
        scanf("%d%d", &u, &v), G[u].push_back(v + n), G[v + n].push_back(u);
    int ans = 0;
    for (int i = 1; i <= n + m; i++)
        if (color[i] == 0)
            dfs(i, ++ans);
    printf("%d\n", ans - 1);
    return 0;
}

C – Hills

一个 SB DP，比上一题难（汗）。

考虑设计状态，发现可以直接 \(\Theta(n^2)\) 艹过去。发现三个状态就够了：放置、未放置、已下降。随便转移即可。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050;

int n, ai[MAX_N], dp[MAX_N][MAX_N][3];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0][0] = 0;
        for (int j = 1; j <= (i + 1) >> 1; j++)
        {
            if (ai[i] > ai[i - 1])
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0]);
            if (i != 1)
            {
                if (ai[i] > ai[i - 2] - 1)
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][2]);
                else
                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][2] + ai[i - 2] - 1 - ai[i] + 1);
            }
            if (ai[i] <= ai[i - 1])
                dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + ai[i - 1] - ai[i] + 1);
            // choose;
            dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][2], dp[i - 1][j][0]));
            if (ai[i] < ai[i - 1])
                dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1]);
            if (ai[i] >= ai[i - 1])
                dp[i][j][2] = min(dp[i][j][2], min(dp[i - 1][j][1], dp[i - 1][j][0]) + ai[i] - ai[i - 1] + 1);
        }
    }
    for (int i = 1; i <= (n + 1) >> 1; i++)
        printf("%d ", min(dp[n][i][0], min(dp[n][i][1], dp[n][i][2])));
    puts("");
    return 0;
}

D – AB-Strings

首先，连续的字符是可以压缩的，可以用链表。用完链表之后，发现如果头部不同，那么就换奇数个单元；如果相同的话，选奇数、偶数个即可。

但是，这样不一定是全局最优的。如果想要当前进行减少的话，这样显然是最优的；但是，全局最优要求我们每一次操作能尽量使这两个串大小相等，这样下一步才会较优。

代码没过，也很难写，就不挂了。