20230721题解

发表于 2023-07-21 阅读次数：

感觉这一套题提高难度左右的做得还行，普及难度打的没脸看。。。

T1 game

思路分析

概率 DP 。

设 \(f_{i,j,k(k \in \{0,1\})}\) 表示 Alice 还剩 \(i\) 分，Bob 还剩 \(j\) 分时 Alice 获胜的概率。\(k=1\) 时 Alice 先手，\(k=0\) 时 Bob 先手。

由定义，可以得到如下方程组：

\[ \left \{ \begin{aligned} f_{i,j,0}&=\frac{1}{2}(f_{i,j,1}+f_{i,j-1,1}) \\ f_{i,j,1}&=\min_{p}{\frac{1}{2^p}f_{i - 2^{p-1},j,0}+(1- \frac{1}{2^p})f_{i,j,0} } \end{aligned} \right. \]

可以发现出现了递归定义，无法转移。

考虑将 \(f_{i,j,0}\) 代换掉。同时代换掉 \(f_{i - 2^{p-1},j,0}\) ，这样就无需计算 Bob 先手的情况了：

\[ f_{i,j,1}=\min_{p}{ \frac{1}{2}(\frac{1}{2^p}(f_{i - 2^{p-1},j,1}+f_{i - 2^{p-1},j-1,1})+(1- \frac{1}{2^p})(f_{i,j,1}+f_{i,j-1,1})) } \]

\(k\) 的取值已经无关紧要，我们删去不看。

移项变形，解出 \(f_{i,j}\)：

\[ f_{i,j}=\min_{p}{ \frac{\frac{1}{2^p}(f_{i - 2^{p-1},j}+f_{i - 2^{p-1},j-1})+(1- \frac{1}{2^p})f_{i,j-1}}{1+\frac{1}{2^p}} } \]

边界条件显然是 \(f_{0,i}=1,f_{i,0}=0\)。这样就可以转移了。

最后考虑 \(p\) 的取值范围。可以想象，Alice 为了尽快结束战斗，可能会选一个得分高于需要的任务。所以 \(2^{p-1}\) 应该枚举到比 \(i\) 略大为止。

话说这其实是我写出来的第一道概率 DP。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 5e2 + 5;

int n;
long double dp[maxn][maxn], p[maxn], q[maxn], ans;

int main() {
    //freopen("game.in", "r", stdin);
    //freopen("game.out", "w", stdout);
    read(n);
    p[0] = 1.0;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0.0;
        dp[0][i] = 1.0;
        p[i] = p[i - 1] / 2;
        q[i] = (1 - p[i]) / 2;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= 40; k++) {
                int ii = i - (1 << (k - 1));
                if (ii < 0) ii = 0;
                dp[i][j] = max(dp[i][j], ((dp[ii][j - 1] + dp[ii][j]) * p[k] + dp[i][j - 1] * (1-p[k])) / (1 + p[k]));
            }
        }
    }
    printf("%.6lf\n", double(dp[n][n]));
    return 0;
}

T2 cipher

思路分析

首先考虑如何判断能否压缩：使用字符串 Hash，比较相邻子串的 Hash 值。

发现字符串长度只有 100，意味着一共只有 10000 个子串。所以可以求出每一个子串压缩后的结果，用类似区间 DP 的方式合并即可。

代码实现使用了记忆化搜索。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 1e2 + 5;

int n;
char s[maxn];
unsigned long long h[maxn], p[maxn];
int mi[maxn][maxn], ml[maxn][maxn], mt[maxn][maxn], res[maxn][maxn];

unsigned long long get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int solve(int l, int r) {
    if (r - l + 1 <= 4) return r - l + 1;
    if (res[l][r]) return res[l][r];
    res[l][r] = r - l + 1;
    for (int i = l; i <= r; i++) {
        for (int len = 1; i + len * 2 - 1 <= r; len++) {
            unsigned long long h1 = get(i, i + len - 1);
            for (int t = 2; i + len * t - 1 <= r; t++) {
                unsigned long long h2 = get(i + len * (t - 1), i + len * t - 1);
                if (h2 != h1) break;
                int tmp1 = solve(i + len * t, r);
                int tmp2 = solve(i, i + len - 1);
                int tmp3 = len < 10 ? 3 : (len < 100 ? 4 : 5);
                int tmp4 = i - l;
                if (tmp1 + tmp2 + tmp3 + tmp4 < res[l][r]) {
                    mi[l][r] = i, ml[l][r] = len, mt[l][r] = t, res[l][r] = tmp1 + tmp2 + tmp3 + tmp4;
                }
            }
        }
    }
    return res[l][r];
}

void print(int l, int r) {
    if (mi[l][r] == 0) {
        for (int i = l; i <= r; i++) putchar(s[i]);
        return;
    }
    for (int i = l; i < mi[l][r]; i++) putchar(s[i]);
    printf("%d", mt[l][r]);
    putchar('(');
    print(mi[l][r], mi[l][r] + ml[l][r] - 1);
    putchar(')');
    print(mi[l][r] + ml[l][r] * mt[l][r], r);
}

int main() {
    // freopen("cipher.in", "r", stdin);
    // freopen("cipher.out", "w", stdout);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * 131 + s[i];
        p[i] = p[i - 1] * 131;
    }
    solve(1, n);
    print(1, n);

    return 0;
}

T3 acrobat

思路分析

由于题目说一只奶牛的受力不包括自己，这会导致所有奶牛的比较标准不同。所以可以做一个修改，让奶牛的受力和它的力量都加上自己的重力，即 \(s_i + w_i \to s_i\)。再比较新的力量和受力。

最优的序列有什么特点呢？它一定是从上往下力量递增的。运用反证法：假设最优序列中存在 \(i < j\)，使得 \(s_i > s_j\)，则交换 \(i,j\) 后，因为 \(j\) 的新位置受力更少，所以 \(j\) 的压扁指数会变小；而 \(i\) 比 \(j\) 力量更大，所以 \(i\) 的新压扁指数会比 \(j\) 原来的压扁指数更小。总压扁指数不会变大，则交换后获得了更优解，与假设矛盾。说明最优序列里没有逆序对。

则按照更新后的 \(s_i\) 排序即可。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 5e4 + 5;
int n;
vector<pair<long long, long long> > vec;

int main() {
    // freopen("acrobat.in", "r", stdin);
    // freopen("acrobat.out", "w", stdout);
    read(n);
    long long ans = 0xcfcfcfcfcfcfcfcf, sm = 0;
    for (int i = 1; i <= n; i++) {
        long long w, s; read(w); read(s);
        sm += w;
        vec.emplace_back(- w - s, -w);
    }
    sort(vec.begin(), vec.end());
    for (auto x : vec) {
        ans = max(ans, sm + x.first);
        sm += x.second;
    }
    write(ans);
    return 0;
}

T4 cost

双倍经验：Luogu。

思路分析

容易发现，卡车经过的路线只会在图的最小生成树上。

证明也容易。以 kruskal 为例，一条边 \((u,v)\) 没有被加入最小生成树必然是因为已经有权值更小的几条边把 \(u\) 所在集合与 \(v\) 所在集合连在了一起，则从 \(u\) 走到 \(v\) 必然有不经过这条边的更有解。

所以可以建出最小生成树之后跑树上两点间取 \(\max\)。使用倍增，时间复杂度 \(O(n \log n)\)。

但是这样码量比较大。观察 kruskal 算法，可以想到：当一条边 \((u,v)\) 被加入最小生成树时，\(u\) 所在集合与 \(v\) 所在集合之间联通的代价就是 \((u,v)\) 的长度。我们可以对于每一个集合，维护有多少个询问跟它有关。在合并的时候，如果询问 \(q\) 既和 \(u\) 所在集合有关，又和 \(v\) 所在集合有关，那么 \(q\) 的答案就是 \((u,v)\) 的边权。

具体实现上，我们对于每个集合维护一个 std::set，合并的时候使用启发式合并，总时间复杂度 \(O(n \log^2 n)\)。实际由于询问解决后就可以删除，复杂度根本跑不满。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 1e4 + 5, maxm = 1e5 + 5;

int n, m, q;

struct node {
    int u, v, w;
} e[maxm];

bool compare(node a, node b) {
    return a.w < b.w;
}

set<int> st[maxn];
int ans[maxn];

int f[maxn];
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

void merge(int u, int v, int w) {
    u = find(u); v = find(v);
    if (u == v) return;
    if (st[u].size() < st[v].size()) swap(u, v); //启发式合并
    f[v] = u;
    for (int x : st[v]) {
        if (st[u].count(x)) {
            ans[x] = w;
            st[u].erase(x);
        }
        else st[u].insert(x);
    }
    st[v].clear();
}

int main() {
    // freopen("cost.in", "r", stdin);
    // freopen("cost.out", "w", stdout);
    read(n); read(m);
    for (int i = 1; i <= m; i++) {
        read(e[i].u); read(e[i].v); read(e[i].w);
    }
    sort(e + 1, e + m + 1, compare);
    read(q);
    for (int i = 1; i <= q; i++) {
        int u, v; read(u); read(v);
        st[u].insert(i);
        st[v].insert(i);
    }
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= m; i++) merge(e[i].u, e[i].v, e[i].w);
    for (int i = 1; i <= q; i++) write(ans[i]);
    return 0;
}

T5 work

原题：Luogu。

思路分析

由于一份工作可以在一条边上来回传递，所以只要 \(L\) 大于 1 到 \(a\) 的最短路，我们一定可以通过在一条边反复的方法最终到达 \(1\) 。但是在一条边上反复是无法改变 \(L\) 的奇偶性的，所以我们要分别求出从 1 出发的奇最短路和偶最短路。

最好理解的方法应该是建分层图跑最短路。对于点 \(u\)，我们拆成两个点 \(u,u+n\)。连边 \((u,v)\) 时，我们把 \(u,v+n\) 与 \(v,u+n\) 连在一起。这样跑完最短路之后，到达 \(u+n\) 点必然过了奇数条边，而到达 \(u\) 点则正好是偶数条。

我实在是太菜了，在 wbx 说出来之前，我甚至没学过分层图的 trick。

AC 代码

code

#include <bits/stdc++.h>
using namespace std;

// #define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 2e5 + 5;

int n, m, qq;
vector<int> graph[maxn];
int dis[maxn];

int main() {
    read(n); read(m); read(qq);
    for (int i = 1; i <= m; i++) {
        int u, v; read(u); read(v);
        graph[u].emplace_back(v + n);
        graph[v].emplace_back(u + n);
        graph[u + n].emplace_back(v);
        graph[v + n].emplace_back(u);
    }
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    queue<int> q;
    q.emplace(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            if (dis[v] == 0x3f3f3f3f) {
                dis[v] = dis[u] + 1;
                q.emplace(v);
            }
        }
    }
    while (qq--) {
        int a, l;read(a); read(l);
        if (l & 1) {
            if (dis[a + n] <= l) printf("Yes\n");
            else printf("No\n");
        }
        else {
            if (dis[a] <= l) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

T6 cowpol

思路分析

考场上想了个 sb 根号分治，感觉要是真敢写绝对会写死。

其实就是有多棵重叠起来的树，让我们分别求直径。

虽然说求一次直径就要两次 dfs，但是 dfs 的意义只是求出到某一点最远的点。而这一点，我们用枚举 + lca 就可以做到。而由于所有树重叠起来也就是一棵树，所以 lca 可以一次性用倍增预处理。

总结一下：倍增预处理 lca，然后对于每一个政党，随便选一个点，枚举找出离这个点最远的点之后再枚举找到最远点的最远点，得到直径。

代码还没写，咕一会儿~