A – 魏传之长坂逆袭

一道水的不得了的题目，两边线性的深搜合并距离即可。

// A.cpp
// Complexity: O(n)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 500200;
int head[MAX_N], current, n, tmpx, tmpy, paths[MAX_N];
ll tmpz, goal = 0, answer;
struct edge
{
    int to, nxt;
    ll weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, ll weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void dfs_1(int u, int fa, ll dis)
{
    ll ans = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs_1(edges[i].to, u, dis + edges[i].weight), ans = max(paths[edges[i].to] + edges[i].weight, ans);
    goal = max(goal, dis), paths[u] = ans;
}
void tune(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            tune(edges[i].to, u), answer += paths[u] - paths[edges[i].to] - edges[i].weight;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d%d%lld", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    dfs_1(1, 0, 0), tune(1, 0);
    printf("%lld", answer);
    return 0;
}

B – 蜀传之单刀赴会

这道题有点失误，写了一个暴力忘记判断不能超过\(t\)这个限制然后就送掉了 30 分，暴力状压 DFS 可拿到 60 分。正解其实就是最短路缩图 + 状压 DP，方程非常好想，设\(f[stat][i]\)为要经过\(stat\)集合中的点且最后一次经过了点\(i\)的最短路径，显然可以得出：

\[ f[stat \cup j][j] = min\{ f[stat][i] + map[i][j] \}, i \in stat, j \not\in stat \]

// B.cpp
// Complexity: O(n log m + 2^(k+1)*k^2) = O(2^(k+1)*k^2)
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, int>
using namespace std;
const int MAX_N = 10010, MAX_M = 50010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, t, head[MAX_N], current, tmpx, tmpy, tmpz, mp[20];
ll dist[20][MAX_N], neomap[20][20], f[(1 << 17)][20];
bool vis[MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[MAX_M << 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++;
}
int getOnBit(int num)
{
    int ans = 0;
    while (num)
        if (num & 1)
            ans++, num >>= 1;
        else
            num >>= 1;
    return ans;
}
void djisktra(int u)
{
    memset(vis, false, sizeof(vis));
    priority_queue<pr> q;
    int org = mp[u];
    q.push(make_pair(0, org)), dist[u][org] = 0;
    while (!q.empty())
    {
        int curt = q.top().second;
        q.pop();
        if (vis[curt])
            continue;
        vis[curt] = true;
        for (int i = head[curt]; i != -1; i = edges[i].nxt)
        {
            int to = edges[i].to;
            if (dist[u][to] > dist[u][curt] + edges[i].weight)
                dist[u][to] = dist[u][curt] + edges[i].weight, q.push(make_pair(-dist[u][to], to));
        }
    }
}
int main()
{
    memset(dist, 0x3f, sizeof(dist)), memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &k, &t);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    for (int i = 0; i < k; i++)
        scanf("%d", &tmpx), mp[i] = tmpx;
    mp[k] = n, mp[k + 1] = 1;
    for (int i = 0; i <= k + 1; i++)
        djisktra(i);
    for (int i = 0; i <= k + 1; i++)
        for (int j = 0; j <= k + 1; j++)
            neomap[i][j] = dist[i][mp[j]];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= k; j++)
            f[(1 << i)][j] = neomap[k + 1][i];
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= k; j++)
                if ((((stat >> i) & 1) == 1) && (((stat >> j) & 1) == 0))
                    f[stat | (1 << j)][j] = min(f[stat | (1 << j)][j], f[stat][i] + neomap[i][j]);
    ll ans1 = 0, ans2 = INF;
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
    {
        if (getOnBit(stat) < ans1 || ((stat >> k) & 1) == 0)
            continue;
        ll tmp = INF;
        for (int i = 0; i <= k; i++)
            if (((stat >> i) & 1) == 1)
                tmp = min(tmp, f[stat][i] + neomap[i][k + 1]);
        if (tmp != INF && tmp <= t)
            ans2 = (ans1 < getOnBit(stat)) ? tmp : min(ans2, tmp), ans1 = getOnBit(stat);
    }
    printf("%lld %lld", ans1 - 1, ans2);
    return 0;
}

最后一直卡在 80 分，发现忘了判断\(t\)的限制，凉飞了。

C – 吴传之火烧连营

心态崩了，这道题本身 trie 树空间开对了，最后标记的空间忘了开大就凉了，亏我还特意计算了要有多少各节点。

这道题就是一道傻* Trie 树摸板题，贪心沿着树走即可。

// C.cpp
// Complexity: O(32n + 32m)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 100;
int trie[MAX_N * 64][2], mark[MAX_N * 64], tot = 1, tmp;
void insert(int num, int mk)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if (trie[p][bit] == 0)
            trie[p][bit] = ++tot;
        p = trie[p][bit];
    }
    mark[p] = mk;
}
int query(int num)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1, desire = bit ^ 1;
        if (trie[p][desire] != 0)
            p = trie[p][desire];
        else
            p = trie[p][bit];
    }
    return mark[p];
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tmp), insert(tmp, i);
    for (int i = 1; i <= m; i++)
        scanf("%d", &tmp), printf("%d\n", query(tmp));
    return 0;
}