A – 找位置

首先发现\(k\)非常的小，且\(n\)也较小，所以考虑直接暴力，枚举经过每一个超市的顺序，然后顺起来就行了（提前处理\(k\)次最短路即可）。

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

using namespace std;

const int MAX_N = 1e4 + 200, MAX_E = 2e5 + 200, MAX_K = 6;

int head[MAX_N], current, n, m, k, *dist, distances[MAX_K][MAX_N], k_set[MAX_K], dist_id[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_E << 1];

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

void shortest_path(int st)
{
    memset(dist, 0x3f, sizeof(distances[0]));
    memset(vis, false, sizeof(vis));
    priority_queue<pr> pq;
    dist[st] = 0, pq.push(make_pair(0, st));
    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%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
        scanf("%d", &k_set[i]), dist_id[k_set[i]] = i;
    for (int i = 1, u, v, w; i <= m; i++)
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
    for (int i = 1; i <= k; i++)
        dist = distances[i], shortest_path(k_set[i]);
    int gans = 0x3f3f3f3f;
    do
    {
        // insert it;
        int pans = 0;
        for (int i = 1; i < k; i++)
            pans += distances[dist_id[k_set[i]]][k_set[i + 1]];
        for (int i = 1; i <= n; i++)
            if (!dist_id[i])
                gans = min(gans, pans + distances[dist_id[k_set[1]]][i] + distances[dist_id[k_set[k]]][i]);
    } while (next_permutation(k_set + 1, k_set + 1 + k));
    printf("%d", gans);
    return 0;
}

B – 砍树枝

这道题挺傻逼的。

每次砍掉一条边都会产生一个新的连通块，且这个连通块一定是一个子树和之外的点集。所以判断是否在同一个子树即可，直接用 DFS 序乱搞就行。

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

using namespace std;

const int MAX_N = 200100, MAX_L = 23;

int head[MAX_N], current, n, q, dep[MAX_N], dfn[MAX_N], antidfn[MAX_N], ptot, edpt[MAX_N];

struct edge
{
    int from, to, nxt;
} edges[MAX_N << 1], org[MAX_N];

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

void dfs(int u, int fat)
{
    dep[u] = dep[fat] + 1, dfn[u] = ++ptot, antidfn[dfn[u]] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            dfs(edges[i].to, u);
    edpt[u] = ptot;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u), org[i] = (edge){u, v, 0};
    dfs(1, 0), scanf("%d", &q);
    while (q--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        int up, low;
        up = org[z].from, low = org[z].to;
        if (dep[up] > dep[low])
            swap(up, low);
        bool xInLow = (dfn[low] <= dfn[x] && dfn[x] <= edpt[low]);
        bool yInLow = (dfn[low] <= dfn[y] && dfn[y] <= edpt[low]);
        if (xInLow ^ yInLow)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

C – 搬砖

直接暴力，记录下每个点往右走的最近的砖块就行了。

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

using namespace std;

const int MAX_N = 1e5 + 200, INF = 0x3f3f3f3f;

struct block
{
    int l, r;
    bool operator<(const block &target) const { return l < target.l || (l == target.l && r < target.r); }
} bs[MAX_N];

int n, q, len, ci[MAX_N], suffix[MAX_N], pos[MAX_N];

int main()
{
    scanf("%d%d%d", &n, &q, &len);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &bs[i].l, &bs[i].r);
    sort(bs + 1, bs + 1 + n);
    for (int i = 1; i <= len + 1; i++)
        ci[i] = len + 1;
    for (int i = 1; i <= n; i++)
    {
        if (i > 1 && bs[i].l == bs[i - 1].l)
            continue;
        ci[bs[i].l] = bs[i].r;
    }
    suffix[len] = ci[len], pos[len] = len;
    for (int i = len - 1; i >= 1; i--)
    {
        suffix[i] = min(suffix[i + 1], ci[i]);
        pos[i] = suffix[i + 1] < ci[i] ? pos[i + 1] : i;
    }
    pos[len + 1] = len + 1;
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int z = pos[x], res = 0;
        while (ci[z] <= y)
            res++, z = pos[ci[z] + 1];
        printf("%d\n", res);
    }
    return 0;
}