A – 走格子

其实就是靠墙走，然后乱七八糟的东西全部用 Djisktra 来搞就行了。

// A.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>

using namespace std;

const int MAX_N = 550, INF = 0x3f3f3f3f;

int n, m, dist[MAX_N * MAX_N], name[MAX_N][MAX_N], cx, cy, px, py;
int upper[MAX_N][MAX_N], lower[MAX_N][MAX_N], lft[MAX_N][MAX_N], rig[MAX_N][MAX_N];
int head[MAX_N * MAX_N], current;
char mp[MAX_N][MAX_N];
bool vis[MAX_N * MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[MAX_N * MAX_N * 10];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

void djisktra()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pr> pq;
    dist[name[cx][cy]] = 0;
    pq.push(make_pair(0, name[cx][cy]));
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] > dist[u] + edges[i].weight)
                dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            name[i][j] = (i - 1) * m + j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 'C')
                cx = i, cy = j;
            if (mp[i][j] == 'F')
                px = i, py = j;
            if (mp[i - 1][j] != '#')
                upper[i][j] = upper[i - 1][j];
            else
                upper[i][j] = i;
            if (mp[i][j - 1] != '#')
                lft[i][j] = lft[i][j - 1];
            else
                lft[i][j] = j;
        }

    for (int i = n; i >= 1; i--)
        for (int j = m; j >= 1; j--)
        {
            if (mp[i + 1][j] != '#')
                lower[i][j] = lower[i + 1][j];
            else
                lower[i][j] = i;
            if (mp[i][j + 1] != '#')
                rig[i][j] = rig[i][j + 1];
            else
                rig[i][j] = j;
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] != '#')
            {
                addpath(name[i][j], name[i - 1][j], 1);
                addpath(name[i][j], name[i + 1][j], 1);
                addpath(name[i][j], name[i][j + 1], 1);
                addpath(name[i][j], name[i][j - 1], 1);

                int dist = min(i - upper[i][j], min(lower[i][j] - i, min(j - lft[i][j], rig[i][j] - j))) + 1;

                addpath(name[i][j], name[i][lft[i][j]], dist);
                addpath(name[i][j], name[i][rig[i][j]], dist);
                addpath(name[i][j], name[upper[i][j]][j], dist);
                addpath(name[i][j], name[lower[i][j]][j], dist);
            }

    djisktra();
    if (dist[name[px][py]] == INF)
        puts("no");
    else
        printf("%d", dist[name[px][py]]);
    return 0;
}

B – 扭动的树

真他妈傻逼。

考虑先进行排序，以维护二叉排序树的性质。然后就是区间 DP，设\(dp[i][j][0/1]\)为\([i, j]\)做\(i – 1\)的左子树还是\(j + 1\)的右子树。DP 时其实就是枚举一个子树根。

值得一提的是，这道题正常递推会出问题。因为 GCD 的限制，很多状态不会被访问到。记忆化搜索就会快很多。

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

using namespace std;

const int MAX_N = 330;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

ll dp[MAX_N][MAX_N][2], n, prefix[MAX_N];
bool conn[MAX_N][MAX_N];
struct node
{
    ll key, val;
    bool operator<(const node &nd) const { return key < nd.key; }
} nodes[MAX_N];

ll dfs(int l, int r, int opt)
{
    if (l > r)
        return 0;
    if (dp[l][r][opt] != 0)
        return dp[l][r][opt];
    ll ans = 0;
    int root = (opt == 1) ? r + 1 : l - 1;
    bool flag = false;
    if (root > n)
        return dp[l][r][opt] = -1;
    for (int i = l; i <= r; i++)
    {
        if (conn[i][root] == false)
            continue;
        ll lft = dfs(l, i - 1, 1), rig = dfs(i + 1, r, 0);
        if (lft == -1 || rig == -1)
            continue;
        ans = max(ans, lft + rig);
        flag = true;
    }
    if (flag)
        return dp[l][r][opt] = ans + prefix[r] - prefix[l - 1];
    else
        return dp[l][r][opt] = -1;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &nodes[i].key, &nodes[i].val);
    sort(nodes + 1, nodes + 1 + n);
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i - 1] + nodes[i].val;
    for (int i = 1; i <= n; i++)
    {
        conn[i][0] = conn[0][i] = true;
        for (int j = i + 1; j <= n; j++)
            if (gcd(nodes[i].key, nodes[j].key) != 1)
                conn[i][j] = conn[j][i] = true;
    }
    printf("%lld", dfs(1, n, 0));
    return 0;
}

C – 旋转字段

考虑每一个点形成的区间\([min(i, arr[i]), max(i, arr[i])]\)的中间点信息\(min(i, arr[i]) + max(i, arr[i])\)是\(O(n)\)级别的，所以我们预处理好每一个中间点的区间，然后从小的区间向外更新答案。

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

using namespace std;

const int MAX_N = 1e5 + 2000;

int seq[MAX_N], n, prefix[MAX_N];
vector<int> vecs[MAX_N << 1];
int ans = 0;

bool compare(int a, int b) { return a > b; }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]), prefix[i] = prefix[i - 1] + (seq[i] == i), vecs[seq[i] + i].push_back(min(seq[i], i));
    for (int i = 1; i <= 2 * n; i++)
        if (!vecs[i].empty())
        {
            sort(vecs[i].begin(), vecs[i].end(), compare);
            int tmp = 0;
            for (vector<int>::iterator it = vecs[i].begin(); it != vecs[i].end(); it++)
            {
                int rig = i - *it;
                tmp++, ans = max(ans, prefix[*it - 1] + prefix[n] - prefix[rig] + tmp);
            }
        }
    printf("%d", ans);
    return 0;
}