A – 调整 Tweak

这道题我在考场上打了一个错解，还骗到了 30 分。

正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。

我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。

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

using namespace std;

const int MAX_N = 1100;

int n, m, c, dist[MAX_N * MAX_N], current, head[MAX_N * MAX_N];
bool vis[MAX_N * MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[1010 + MAX_N * MAX_N];

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> q;
    q.push(make_pair(0, 1));
    dist[1] = 0;
    while (!q.empty())
    {
        int u = q.top().second;
        q.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, q.push(make_pair(-dist[edges[i].to], edges[i].to));
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        for (int layer = 0; layer < n; layer++)
            addpath(layer * n + u, layer * n + v, w);
        for (int layer = 0; layer < n - 1; layer++)
            addpath(layer * n + u, (layer + 1) * n + v, 0);
    }
    djisktra();
    for (int layer = 0; layer < n; layer++)
        if (dist[layer * n + n] <= c)
        {
            printf("%d", layer);
            return 0;
        }
    return 0;
}

B – 树 A

sb 题，树链剖分板子题，不讲。

// B.cpp
#include <bits/stdc++.h>
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

using namespace std;

const int MAX_N = 31000;

int head[MAX_N], current, pt_weight[MAX_N], dfn[MAX_N], antidfn[MAX_N], m;
int top[MAX_N], son[MAX_N], siz[MAX_N], dep[MAX_N], fa[MAX_N], dfntot, n, opt;

int tree[MAX_N << 2];

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

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

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(tree[p] = pt_weight[antidfn[l]]);
    build(l, mid, lson), build(mid + 1, r, rson);
    tree[p] = tree[lson] + tree[rson];
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r && qx == l)
        return (void)(tree[p] = val);
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    tree[p] = tree[lson] + tree[rson];
}

int query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return tree[p];
    int ans = 0;
    if (ql <= mid)
        ans += query(ql, qr, l, mid, lson);
    if (mid < qr)
        ans += query(ql, qr, mid + 1, r, rson);
    return ans;
}

int query(int x, int y)
{
    if (dep[top[x]] > dep[top[y]])
        swap(x, y);
    int ans = 0;
    while (top[x] != top[y])
    {
        ans += query(dfn[top[y]], dfn[y], 1, n, 1);
        y = fa[top[y]];
        if (dep[top[x]] > dep[top[y]])
            swap(x, y);
    }
    if (dep[x] > dep[y])
        swap(x, y);
    ans += query(dfn[x], dfn[y], 1, n, 1);
    return ans;
}

void dfs1(int u)
{
    siz[u] = 1, dep[u] = dep[fa[u]] + 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[u])
        {
            fa[edges[i].to] = u, dfs1(edges[i].to);
            siz[u] += siz[edges[i].to];
            if (siz[edges[i].to] > siz[son[u]])
                son[u] = edges[i].to;
        }
}

void dfs2(int u, int org)
{
    dfn[u] = ++dfntot, antidfn[dfntot] = u, top[u] = org;
    if (son[u] == 0)
        return;
    dfs2(son[u], org);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[u] && edges[i].to != son[u])
            dfs2(edges[i].to, edges[i].to);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs1(1), dfs2(1, 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &pt_weight[i]);
    build(1, n, 1);
    while (m--)
    {
        int A, B;
        scanf("%d%d%d", &opt, &A, &B);
        if (opt == 1)
            update(dfn[A], 1, n, 1, B);
        else 
            printf("%d\n", query(A, B));
    }
    return 0;
}

C – 树 B

也是一道 SB 题，要不是我边的数组开小了，我考场上就能多 A 一题，那至于只有 50 分。

这道题很显然是一道树形 DP，考虑对要隔离的点进行标记，然后树形 DP 方程如下：

\[ \begin{cases} dp[u][0] = \sum_{v \in son(u)} min\{ dp[v][0], dp[v][1] \}[tag[v] = false] + dp[v][1][tag[v] = true] \\ dp[u][1] = e(e, fa[u]).weight \end{cases} \]

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

using namespace std;

const int MAX_N = 1e6 + 200;

int n, m, head[MAX_N], current, fa[MAX_N], upward[MAX_N];
int dp[MAX_N][2];
bool tag[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 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 preprocess(int u)
{
    dp[u][1] = edges[upward[u]].weight;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[u])
        {
            fa[edges[i].to] = u, upward[edges[i].to] = i;
            preprocess(edges[i].to);
            if (tag[edges[i].to])
                dp[u][0] += dp[edges[i].to][1];
            else 
                dp[u][0] += min(dp[edges[i].to][0], dp[edges[i].to][1]);
        }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, c; i <= n - 1; i++)
        scanf("%d%d%d", &u, &v, &c), addpath(u, v, c), addpath(v, u, c);
    for (int i = 1, tmp; i <= m; i++)
        scanf("%d", &tmp), tag[tmp] = true;
    preprocess(1);
    printf("%d", dp[1][0]);
    return 0;
}

D – 跨时代

这道题真的毒瘤。

最开始的做法：考虑状态压缩，所有的木棍拼接成的长度的情况都存在桶中，然后枚举两边长度，枚举当前长度下的木棍状态，然后 AND 判断，也就是这样：

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

using namespace std;

const int MAX_N = 20;

int n, li[MAX_N], mxlen, S = -0x3f3f3f3f, sizes[20 * 15];
int bucket[20 * 15][20 * 150];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &li[i]), mxlen += li[i];
    for (int i = 0; i < (1 << n); i++)
    {
        int len = 0;
        for (int j = 1; j <= n; j++)
            if (i & (1 << (j - 1)))
                len += li[j];
        bucket[len][sizes[len]++] = i;
    }
    for (int lenA = mxlen; lenA >= 1; lenA--)
    {
        int sizA = sizes[lenA];
        if (sizA == 0)
            continue;
        if (lenA * mxlen <= S)
            break;
        for (int lenB = mxlen; lenB >= 1; lenB--)
        {
            int sizB = sizes[lenB];
            if (sizB  == 0)
                continue;
            if (lenA * lenB <= S)
                break;
            for (int x = 0; x < sizA; x++)
            {
                int statX = bucket[lenA][x];
                for (int y = 0; y < sizA; y++)
                {
                    int statY = bucket[lenA][y];
                    if ((statX & statY) != 0)
                        continue;
                    for (int z = 0; z < sizB; z++)
                    {
                        int statZ = bucket[lenB][z];
                        if((statX & statZ) != 0 || (statY & statZ) != 0)
                            continue;
                        for (int w = 0; w < sizB; w++)
                        {
                            int statW = bucket[lenB][w];
                            if ((statW & statX) != 0 || (statW & statY) != 0 || (statW & statZ) != 0)
                                continue;
                            S = max(S, lenA * lenB);
                        }
                    }
                }
            }
        }
    }
    if (S < 0)
        printf("No Solution");
    else
        printf("%d", S);
    return 0;
}

然后，嗯，TLE 了。

最后我看别人的做法是这样的：考虑状态压缩一套边，也就是一对长或者是一对宽，状压的时候进行背包 DP 判断这一套边是否能被拆成两部分，如果能的话打一个标记。然后，进行搜索：DFS 的时候，时间复杂度是\(O(3^n)\)的，因为每一条边都有选或者是不选的状态，然后考虑分配长和宽就行了。

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

const int MAX_N = 17;

using namespace std;

int n, ai[MAX_N], dp[MAX_N * 20], ans = -1;
bool flag[(1 << MAX_N)];

void dfs(int dep, int statA, int lenA, int statB, int lenB)
{
    if (dep == n)
    {
        if (flag[statA] && flag[statB])
            ans = max(ans, (lenA * lenB) / 4);
        return;
    }
    dfs(dep + 1, statA, lenA, statB, lenB);
    dfs(dep + 1, statA | (1 << dep), lenA + ai[dep + 1], statB, lenB);
    dfs(dep + 1, statA, lenA, statB | (1 << dep), lenB + ai[dep + 1]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int stat = 1; stat < (1 << n); stat++)
    {
        int sum = 0;
        for (int i = 1; i <= n; i++)
            if ((stat >> (i - 1)) & 1)
                sum += ai[i];
        if (sum & 1)
            continue;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            if ((stat >> (i - 1)) & 1)
                for (int k = sum; k >= ai[i]; k--)
                    dp[k] |= dp[k - ai[i]];
        if (dp[sum >> 1])
            flag[stat] = true;
    }
    dfs(0, 0, 0, 0, 0);
    if (ans > 0)
        printf("%d", ans);
    else
        puts("No Solution");
    return 0;
}