雪碧只喝可乐

编辑于 2024-12-02 14:18 广东

+ 关注

官方题解

“华为杯”2024 年广东工业大学 ACM 新生程序设计竞赛题解

PDF 题面，题解，和标程下载：点击下载

题目难度分布：

签到题: A、N
Easy: I、E、C、F
Medium: J、D、K、G
Hard: B、H、M
Very-Hard: L

A. 演奏春日影

简明题意

给定 $n$ 个字符串，原样输出的前提下判断是否为目标字符串，如果是则额外插入输出一个字符串。

题解

签到题，按题意模拟即可。

具体的说，按行读入字符串，并原样输出。同时判断读到的字符串是否是“Tomori”，如果是就额外输出一行“Haruhikage”。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using i64 = long long;
void work() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::string str;
        std::cin >> str;
        std::cout << str << "\n";
        if (str == "Tomori") {
            std::cout << "Haruhikage\n";
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

N. 哥伦比亚大选

简明题意

给定 $n$ 个字符串和数值，输出所有数值中最大者对应的字符串。

题解

签到题，按题意模拟即可。

设置初始的最大票数为 $0$ ，枚举所有的候选人，如果当前候选人的票数大于之前的票数，那么将答案更新为当前候选人的名字，并更新最大票数，最后输出答案即可。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

void solve() {
    int n;
    std::cin >> n;
    std::string name;
    int ans = 0;
    while (n--) {
        static std::string s;
        int cnt = 0;
        std::cin >> s >> cnt;
        if (cnt > ans) {
            ans = cnt;
            name = s;
        }
    }
    std::cout << name << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    // std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

I. 小 P 爱折跃

简明题意

给一个排列，问最少需要交换多少次元素才能使得整个排列形成一个大的环。

题解

可以先通过 DFS 或者并查集求出所有的联通块，答案即是联通块个数减一。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        --a[i];
    }

    std::vector<int> vis(n);

    int ans = -1;
    auto dfs = [&](auto&& self, int u) -> bool {
        if (vis[u]) {
            ans++;
            return true;
        }
        vis[u] = 1;
        return self(self, a[u]);
    };

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            dfs(dfs, i);
        }
    }

    std::cout << ans << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

E. 黑塔的奇物

简明题意

用 $1$ 到 $n$ 的数字各 $n$ 个，构造一个 $n\times n$ 的矩阵，使得矩阵每一行和每一列的异或值的最大值最小。

给出最小值和构造方案。

题解

可以通过打表或手算发现，对于正奇数 $n$ ，有： $n \oplus (n-1) = 1$ 。因此归纳可得：

1\oplus 2\oplus\cdots\oplus n= \left\{ \begin{array} {l} 0,\ \ \ \ \ \ n\mod 4=3\\ 1,\ \ \ \ \ \ n\mod 4=1\\ \end{array} \right\}

容易看出， $n\mod 4=3$ 时，让每一列每一行都有 $1$ 到 $n$ 的每个数即可获得 $m=0$ 的最小阈值。

而 $n\mod 4=1$ 时，由于 $1$ 到 $n$ ，的数中二进制下最低位是 $1$ 的数的数量是奇数，也就是无论如何摆放这 $n^2$ 个数，都至少有一行或一列异或后二进制下最低位是 $1$ 。因此最小阈值 $m=1$ ，具体方案同上。

时间复杂度 $O(n^2)$ 。

代码

#include <bits/stdc++.h>
using i64 = long long;
using f80 = long double;
void work() {
    int n;
    std::cin >> n;
    std::cout << ((n / 2) % 2 == 0) << "\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << (i + j) % n + 1 << " \n"[j == n - 1];
        }
    }
    return;
}
int main() {
    init();
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

C. 交通要塞

简明题意

给定 $n$ 个二维平面的水平可行区间，区间每单位时刻向负方向整体移动一个单位。

初始时在 $(0, 0)$ ，每个单位时刻可以选择停留或前进。

问需要至少多少单位时刻才能穿过 $n$ 个区间而不接触非法区间，或者报告不可能。

题解

考虑贪心。我们尽可能的向前走，走不了再停住，等到能走后立刻前进。这样显然做一定是最优的。

考虑如何计算最短的路径。首先简化模型，考虑固定所有的车，让车不动，人动。那么每单位时间的操作将转化为 $(x,y) \to (x,y+1)$ 或者 $(x, y) \to (x+1,y+1)$ 。

进一步简化模型，我们可以先将所有的 $l_i$ 和 $r_i$ 都减去 $i$ ，得到了一个等价的变换。这样我们的前进就变成了直线的前进，即每单位时间的操作转化为 $(x, y) \to (x,y+1)$ 或者 $(x,y) \to (x+1,y)$ 。

最后我们直接模拟移动，从原点出发扫过去即可。可以从 $1$ 到 $n$ 枚举，枚举到 $x$ 时，对 $y$ 进行维护，其中 $y$ 代表上一步移动到的 $y$ 坐标。如果 $l_x > r_{x-1}$ 或者 $r_x < y$ ，则无法到达终点；如果 $l_x \le r_{x-1}$ 且 $l_x > y$ ，则需要多等待 $l_x - y$ 个单位的时间。最后前进一步，消耗一个单位的时间。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

void solve() {
    int n;
    std::cin >> n;
    i64 ans = n + 1, cur = 0, limit = 1e18;
    for (int i = 0; i < n; i++) {
        i64 l, r;
        std::cin >> l >> r;
        l -= i + 1, r -= i + 1;
        if (r < cur || l > limit) {
            ans = -1;
            break;
        }
        if (cur < l) {
            ans += l - cur;
            cur = l;
        }
        limit = r;
    }
    std::cout << ans << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    // std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

F. 字符串缩写太多了！

简明题意

给定 $n$ 个字符串，问对于所有可能的英文短语缩写可能含有的不同含义的个数的总和是多少。

题解

简单计数题。观察本题所求答案的本质，发现本题完全不需要在乎字符串的缩写是什么，亦不用在乎字符串的内容是什么，其本质是不同长度的所有字符串的排列方案数之和，即答案为：

\sum_{i=1}^{n}{{}^{n}P_{i}} = \sum_{i=1}^{n}{\frac{n!}{(n-i)!}}

一种简便的计算方法是，初始时答案为 $0$ ，从 $1$ 枚举到 $n$ ，枚举到 $i$ 时将答案先自增然后乘上 $i$ 。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
#include <string>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

const int MOD = 1e9 + 7;

void solve() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        static std::string s;
        std::cin >> s;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = 1LL * (ans + 1) * i % MOD;
    }
    std::cout << ans << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    // std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

J. 好得不能再好了！泰拉投资大师课

简明题意

进行若干次独立的实验，每次成功的概率是 $p$ ，问在失败次数超过 $n-1$ 次前成功 $n$ 次的概率是多少。

题解

直接暴力枚举实验输了的次数，用组合数计算二项分布的概率即可。答案即为：

p\times\sum_{i=0}^{n-1}{\binom{n-1+i}{n-1}\times p^{n-1}\times(1-p)^i} = p^n\times\sum_{i=0}^{n-1}{\binom{n-1+i}{i}\times(1-p)^i}

预处理阶乘及其逆元即可在算答案时 $O(1)$ 求解组合数何概率的幂次。

时间复杂度 $O(n + \log m)$ 。

代码

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

const int MOD = 1e9 + 7;

i64 pw(i64 a, i64 b) {
    i64 res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

i64 inv(i64 a) {
    return pw(a, MOD - 2);
}

const int MAXN = 2e5 + 5;
std::vector<int> fac, invfac;

void init() {
    fac.resize(MAXN), invfac.resize(MAXN);
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fac[i] = 1LL * fac[i - 1] * i % MOD;
    }
    invfac[MAXN - 1] = inv(fac[MAXN - 1]);
    for (int i = MAXN - 2; i >= 0; i--) {
        invfac[i] = 1LL * invfac[i + 1] * (i + 1) % MOD;
    }
}

i64 binom(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return 1LL * fac[n] * invfac[k] % MOD * invfac[n - k] % MOD;
}

void solve() {
    int n, a, b;
    std::cin >> n >> a >> b;
    i64 p = a * inv(b) % MOD, q = (1 - p + MOD) % MOD;
    i64 ans = 0, pp = pw(p, n), qq = 1;
    for (int i = 0; i < n; i++, qq = qq * q % MOD) {
        ans = (ans + binom(n - 1 + i, n - 1) * pp % MOD * qq % MOD) % MOD;
    }
    std::cout << ans << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    skadi::init();
    int t = 1;
    std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

D. 魔法少女素世世

简明题意

给定一个有向无环图，初始时从入度为 $0$ 的点进入，初始魔力值为 $x$ 。

与每个途径节点上的敌人战斗，第 $i$ 号节点的敌人魔力值为 $a_i$ 。每场战斗后 $x$ 的值会发生如下变化：

x=\left\{ \begin{aligned} &x + a_i, &\text{if } x \geq a_i, \\ &x - (a_i - x), &\text{otherwise}. \end{aligned} \right\}

若此时 $x \le 0$ ，战斗失败。

问最小的初始魔力值 $x$ ，使得最终可以战胜 $n$ 号节点的敌人。

题解

观察到答案具有单调性，考虑通过二分答案求最小的 $x$ 。

由于题目所给图为有向无环图，且初始从入度为 $0$ 的点进入，可以通过拓扑序遍历 $+$ 动态规划的方式判断某个 $x$ 是否可行。

若我们设 $f_i$ 表示到达 $i$ 号节点，且尚未与该节点敌人进行战斗时的最大可能魔力值，则对于图中的每条边 $u \rightarrow v$ ，有：

f_v = \max\left(f_v, \left\{ \begin{aligned} &f_u + a_u, &\text{if } f_u \geq a_u, \\ &f_u - (a_u - f_u), &\text{otherwise}. \end{aligned} \right\}\right)

若在按拓扑序遍历结束后， $f_n$ 的值足以打败 $n$ 号节点的敌人，则当前判断的 $x$ 合法。

时间复杂度 $O(m\log a)$ 。

代码

#include <bits/stdc++.h>
using i64 = long long;
void work() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1), f(n + 1);
    std::vector<std::vector<int>> to(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        ++f[v];
        to[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i]) {
            continue;
        }
        ++f[i];
        to[0].push_back(i);
    }
    std::vector<i64> dp(n + 1);
    auto check = [&](int k) {
        auto d = f;
        dp.assign(n + 1, 0);
        dp[0] = k;
        std::vector<int> que{0};
        int now = 0;
        while (now < int(que.size())) {
            int x = que[now];
            ++now;
            for (auto y : to[x]) {
                if (dp[x] >= a[y]) {
                    dp[y] = std::max(dp[y], dp[x] + a[y]);
                } else {
                    dp[y] = std::max(dp[y], dp[x] * 2 - a[y]);
                }
                --d[y];
                if (!d[y]) {
                    que.push_back(y);
                }
            }
        }
        return dp[n];
    };
    int l = 1, r = 1e9, mid;
    while (r - l > 1) {
        mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (check(l)) {
        std::cout << l << "\n";
    } else {
        std::cout << r << "\n";
    }
    return;
}

int main() {
    init();
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

K. 说重话！！！

简明题意

有一个初始时全 $0$ 的长度为 $n$ 的数组，然后将首项为 $1$ 公差为 $1$ 等差数列或者完全平方数数列累加到数组的 $m$ 个位置上，输出最后形成的数组。

题解

先考虑如果我们想生成一个第一类的数组怎么做。我们可以通过在起始位置放置一个 $1$ ，然后进行两次前缀和得到一个目标数组。

接下来，我们考虑如果想要放置若干个第一类数组怎么做。我们发现，按照刚才的步骤分开进行求解，最后再加和到一起，与一开始就共用一个差分数组，然后进行两次前缀和是等效的。

这是因为上述操作具有可加性，求解的过程可以合并在一起，并不会相互干扰。

接下来考虑第二个数列的累加怎么做。考察第二个数组第 $k$ 项和第 $k+1$ 项的关系：

(k+1)^2 = k^2 + 2\cdot k + 1

我们发现，可以通过拆解平方项，将第二个数组相邻两项的线性关系表示出来。

因此，同样根据可加性，我们可以通过递推和前缀和将每一个第二类数组在某个位置的项的和算出。

考虑使用与第一个数组相同的办法处理得到 $2\cdot k$ , $1$ 也可以通过使用差分进行一次前缀和处理得到。

于是，我们就能通过这个转移式求出每个第二类数组在某位置的 $k^2$ 的和了。

时间复杂度 $O(n)$ 。

另一种可行解法：

直接加的复杂度是 $O(n\cdot m)$ 的，考虑优化。对于一个 $a_1$ 处为 $1$ ，其它为 $0$ 的差分数组，有：

做一次前缀和，有 $\dot{a}_i=1$ 。
做两次前缀和，有 $\ddot{a}_i=i$ 。
做三次前缀和，有 $\hat{a}_i=\frac{i^2+i}{2}$ 。

其中第一类操操作可以通过 $\ddot{a}_i$ 得到；第二类操作可以通过 $2\cdot \hat{a}_i-\ddot{a}_i$ 得到。

具体一点，有 $a,b,c,d$ 四个数组：

对数组 $a$ 做前缀和得到数组 $b$ 。
对数组 $b$ 做前缀和得到数组 $c$ 。
对数组 $c$ 做前缀和得到数组 $d$ 。

数组 $d$ 即为最终数组。

按照以上分析，对于第一类操作，将 $b_x$ 的数 $+1$ 即可；

而对于第二类操作，将 $a_x$ 的数 $+2$ ，再将 $b_x$ 的数 $-1$ 即可。

最后再按照顺序依次进行操作和前缀和就可以得到答案。

时间复杂度 $O(n)$ 。

代码

第一种解法：

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

const int MOD = 1e9 + 7;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n), b(n), c(n);
    for (int i = 0; i < m; i++) {
        int op, x;
        std::cin >> op >> x, x--;
        if (op == 1) {
            a[x] += 1;
        } else {
            b[x] += 1;
            c[x] += 1;
        }
    }
    for (int i = 1; i < n; i++) {
        a[i] = (a[i] + a[i - 1]) % MOD;
        b[i] = (b[i] + b[i - 1]) % MOD;
        c[i] = (c[i] + c[i - 1]) % MOD;
    }
    for (int i = 1; i < n; i++) {
        a[i] = (a[i] + a[i - 1]) % MOD;
        b[i] = (b[i] + b[i - 1]) % MOD;
        c[i] = (c[i] + c[i - 1] + 2LL * b[i - 1]) % MOD;
    }
    for (int i = 0; i < n; i++) {
        std::cout << (a[i] + c[i]) % MOD << " \n"[i == n - 1];
    }
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
#endif
    int t = 1;
    std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

第二种解法：

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 mod = 1e9 + 7;
void work() {
    int n, m;
    std::cin >> n >> m;
    std::vector<i64> a(n), b(n), c(n), d(n);
    for (int i = 0; i < m; ++i) {
        int op, x;
        std::cin >> op >> x;
        --x;
        if (op == 1) {
            b[x] += 1;
        } else {
            a[x] += 2;
            b[x] -= 1;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i) {
            a[i] += a[i - 1];
        }
        b[i] += a[i];
    }
    for (int i = 0; i < n; ++i) {
        if (i) {
            b[i] += b[i - 1];
        }
        c[i] += b[i];
    }
    for (int i = 0; i < n; ++i) {
        if (i) {
            c[i] += c[i - 1];
        }
        d[i] += c[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cout << d[i] % mod << " \n"[i == n - 1];
    }


    return;
}

int main() {
    init();
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

G. 可乐喝雪碧

简明题意

给定 $n$ 个整数，在整数之间填充加号或者乘号，问能否使得表达式的值为 $0$ 。

题解

首先特判两个简单的情况：

$a_i$ 中有 $0$ 时可以构造。
$a_i$ 中没有 $-1$ 时无法构造。

接下来，我们先考虑所有数都是 $-1$ 。

$-1$ 的数量大于等于 $3$ 且为奇数时，总是有解的。因为我们可以将偶数个 $-1$ 合并成一个 $1$ ，最后再与剩下的 $-1$ 相加得到 $0$ 。
$-1$ 的数量大于等于 $6$ 且为偶数时，总是有解的。因为我们可以将偶数个 $-1$ 拆分成个数均不小于 $3$ 且都为奇数个 $-1$ 两个的部分。故这种情况也能构造出 $0$ 。

因为所有的 $1$ 都可以通过乘上其周围的数来直接消去，故它的数量对上述解没有影响。

接下来考虑 $4$ 个 $-1$ 的情况，可以发现，只有 $4$ 个 $-1$ 是无法构造的，但一旦在任意位置插入一个 $1$ ，就可以进行构造。因此 $4$ 个 $-1$ 的情况通过上述方式特判即可。

对于只有 $1$ 个和 $2$ 个 $-1$ 的情况，可以发现必须有至少同样数量的 $1$ 才能构造。

综上所述，记 $a$ 为 $-1$ 的数量， $b$ 为 $1$ 的数量， $c$ 为 $0$ 的数量，满足以下任意一个条件即可构造：

$c > 0$
$b \ge a$
$a = 3$ 或 $a > 4$
$a = 4$ 且 $b > 0$

如果以上条件均不满足，则无法构造出 $0$ 。

时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
void work() {
    int n, m = 0, tag = 0;
    std::cin >> n;
    std::cin >> m;
    std::vector<int> a(n);
    int cnt = 0, cnt1 = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] == -1) {
            ++cnt;
        } else if (a[i] == 0) {
            tag = 1;
        } else {
            ++cnt1;
        }
    }
    if ((cnt && cnt1 >= cnt) || cnt > 4 || cnt == 3 || (cnt == 4 && cnt1)) {
        tag = 1;
    }
    while (m--) {
        int q;
        std::cin >> q;
        if (tag) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

B. 超平坦棋盘

简明题意

在无尽大的棋盘上，不吃子的前提下问将一个指定位置的马移动到目标空格的最少步数是多少。

题解

首先，我们可以把空格和马反转，把空格视作马，马视作空格。因此空格可以直接按照马的形式进行移动。要想让目标马进行第一步移动，我们至少要先把空格移动到目标马的八个马脚处。

因此，我们先进行一次 BFS，求解将空格移动到目标马脚的最短路是多少。

接下来，考虑图论建模。我们将每个格子可以拆成八个点，分别代表了当前空格位于目标马的相对方向的状态。

通过手动构造，可以发现目标马向不同方向移动的代价。

向当前空格的方向移动的代价是 $1$ ；
向当前空格的正对面移动的代价是 $5$ ；
向其他任何方向移动的代价都是 $3$ ；

于是我们可以进行连边，构造出一个图论模型。

我们可以通过反向连边，然后求终点的单源点最短路来减少求解次数，最后枚举目标马起点周围的八个格子，合并答案取最小值即可。

实现上，可以不用存边来减少常数，拓展点的时候直接现场枚举所有边即可。

注意需要将棋盘扩大大约 $5$ 格左右，因为有些边界也是可以去到的。但是不用补太多，启发性的思考马并不会偏离到达终点的直线路径太多。

时间复杂度 $O(nm\log nm)$ 。

代码

#include <bits/stdc++.h>

const int base = 2;
const int inf = 0x3f3f3f3f;
const int dx[8] = {1, -1, 1, -1, 2, -2, 2, -2};
const int dy[8] = {2, -2, -2, 2, 1, -1, -1, 1};
const int cost[8] = {1, 5, 3, 3, 3, 3, 3, 3};

void solve() {
    int n, m;
    std::cin >> n >> m;
    int sx = base, sy = base, ex = n + base, ey = m + base;
    n += base * 2, m += base * 2;

    auto valid = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    };

    std::vector<int> dis1(n * m, -1), dis2(n * m * 8, -1);

    std::queue<std::pair<int, int>> q;
    q.emplace(ex, ey);
    dis1[ex * m + ey] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (valid(nx, ny) && dis1[nx * m + ny] == -1) {
                dis1[nx * m + ny] = dis1[x * m + y] + 1;
                q.emplace(nx, ny);
            }
        }
    }

    std::priority_queue<std::pair<int, int>> pq;
    for (int i = 0; i < 8; i++) {
        int id = (ex * m + ey) * 8 + i;
        dis2[id] = 0;
        pq.emplace(0, id);
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (dis2[u] != -d) {
            continue;
        }
        int x = u / 8 / m, y = u / 8 % m, i = u % 8;
        int fx = x + dx[i], fy = y + dy[i];
        for (int j = 0; j < 8; j++) {
            int id = (fx * m + fy) * 8 + j;
            int val = cost[i ^ j ^ 1];
            if (valid(fx, fy) && (dis2[id] == -1 || dis2[id] > dis2[u] + val)) {
                dis2[id] = dis2[u] + val;
                pq.emplace(-dis2[id], id);
            }
        }
    }

    int ans = inf;
    for (int i = 0; i < 8; i++) {
        int tx = sx + dx[i], ty = sy + dy[i];
        int id = tx * m + ty;
        int tid = id * 8 + (i ^ 1);
        if (valid(tx, ty) && dis1[id] != -1 && dis2[tid] != -1) {
            ans = std::min(ans, dis1[id] + dis2[tid]);
        }
    }

    std::cout << ans + 1 << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

H. 雪碧喝可乐

简明题意

给定 $n$ 个整数，在整数之间填充加号或者乘号，一共 $q$ 个询问，问能否使得表达式的值为 $x$ 。

$x$ 为 $1$ 到 $10^9$ 的整数。

题解

设最大能达到的快乐值为 $m$ ，则可以发现， $m$ 一定是由若干连续整数相乘得到的 $1$ 、 $0$ 、 $-1$ 相加得来。因此，只需将其中任意的 $1$ 由加改为乘入相邻的数，就可以得到 $m-1$ 。

并以此类推可以得出：如果表达式的最大值能达到 $m$ ，则可以使表达式的值为 $1$ 到 $m$ 的任何数。

接下来考虑如何求表达式最大值 $m$ 。

考虑 dp，定义 $f_0 = 0$ ， $f_i$ 表示以 $i$ 结尾的表达式的最大值，通过枚举最后一段连续乘的长度进行转移，即：

f_i=\max_{0\le j<i}(f_j+\textstyle\prod_{k=j+1}^{i}a_k)

但是这样的复杂度是 $O(n^2)$ 的，考虑优化。

若 $a_i=1$ ，则加上一定比乘上更优。因此这种情况下 $f_i$ 从 $f_{i-1}$ 转移即可。
若 $a_i=-1$ ，则要尽量找前一个 $-1$ 与之相乘为 $1$ ，或者找前一个 $0$ 与之相乘为 $0$ 。对于第一种情况可以发现，只有在与前一个 $-1$ 之间有 $0$ 到 $2$ 个 $1$ 时，乘起来更优。对于第二种情况，只有 $a_{i-1}$ 为 $0$ 时与之相乘更优。因此这种情况下 $f_i$ 从 $f_{i-j}(1\le j \le 4)$ 转移即可。
若 $a_i=0$ ，则要么直接加上，要么与前一个 $-1$ 与之相乘为 $0$ ，而只有前一个 $-1$ 是 $a_{i-1}$ 更优。因此这种情况下 $f_i$ 从 $f_{i-1}$ 和 $f_{i-2}$ 转移即可。

总结下来，只需要按照 $a_i$ 的值对 $f_i$ 进行转移即可。但由于最多转移不超过 $4$ 个数，转移方程可以直接写成：

f_i=\max_{\max(0,i-4)\le j <i}(f_j+ {\textstyle \prod_{k=j+1}^{i}}a_k)

这样表达式最大值 $m=f_n$ ，而对于 $q$ 个询问，只需判断 $x$ 是否大于 $m$ 即可。

时间复杂度 $O(n+q)$ 。

代码

#include <bits/stdc++.h>

void work() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n);
    std::vector<int> dp(n + 1, -1);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        int sum = 1;
        for (int j = 0; j <= std::min(i, 5); ++j) {
            sum *= a[i - j];
            dp[i + 1] = std::max(dp[i + 1], dp[i - j] + sum);
        }
    }
    while (m--) {
        int q;
        std::cin >> q;
        if (q <= dp[n]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

M. GLLF 砍木棍

简明题意

给定长度为 $n$ 的木棍，问有多少种切割方式使得切出的所有木棍可以拼成凸多边形，两种方案不同当且仅当切割的点位不同。

题解

先考虑什么情况下能构成凸多边形。与三角形类似，我们发现只要除最长边以外的所有边的长度和大于最长边，即可构成一个凸多边形。简要证明：考虑除了最长边以外所有的边的长度之和等于最长边的长度，此时任意边增加一点长度，即可产生一个凸起，形成凸多边形。

因此问题转化为，有多少种切割方案可以使得除了最长边外的所有边的长度和大于最长边。我们发现直接去求解这个问题并不好做。考虑转换思维，如果我们能求出有多少种不合法的方案，也是可以算出答案的。只需用总方案数减去不合法的方案数即可。

总方案由每个切割点是否切割得到，即 $2^{n-1}$ 。先去除显然不合法的 $n$ 个方案：

不进行切割，共 $1$ 个方案；
只切割一次，共 $n-1$ 个方案；

先考虑朴素的求解，我们可以暴力枚举最长边的长度 $k$ ，有 $(n-k+3)\times2^{n-k-2} -2$ 个方案：

最长边不在两端时的位置有 $n-k-1$ 个，可以随意选择是否切割的点位有 $n-k-2$ 个，总方案数为 $(n-k-1) \times 2^{n-k-2}$ 。
最长边在两端时至少切两次的方案数： $2\times 2^{n-k-1} - 2$

于是答案即为：

2^{n-1} - n -\sum_{i=\lfloor\frac{n+1}{2}\rfloor}^{n-2}{[(n-i+3)\times2^{n-i-2}-2]}

然而直接求解是 $O(n)$ 的，需要优化。可以使用错位相减法求出求和的通项公式，就能快速进行计算了。

记 $k = \lfloor\frac{n}{2}\rfloor$ 最终答案的公式为：

2^{n-1}-n-2^{k-1}\times(k+2) + 2\times (k-1) + 3

时间复杂度 $O(T\log n)$ 。

代码

#include <bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

const int MOD = 1e9 + 7;

i64 pw(i64 a, i64 b) {
    i64 res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    i64 n;
    std::cin >> n;
    i64 k = n / 2;
    i64 ans = pw(2, n - 1) - n - pw(2, k - 1) * (k + 2) + 2 * (k - 1) + 3;
    ans = (ans % MOD + MOD) % MOD;
    std::cout << ans << '\n';
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

L. 向日葵的坡道

简明题意

给定一个 $n$ 个点 $m$ 条边的有向二分图，其中所有的边都从同一个独立点集出发指向另一个独立点集，问最少需要加多少条边，才能使得原图强连通，并给出构造方案。

题解

本题的一般形式都可以化简为本题给出的图论模型，因此本题的解法也可以适用于一般模型。

首先我们定义一些概念：

入点：入度为 $0$ 的点。
出点：出度为 $0$ 的点。
孤立点：入读和出度均为 $0$ 的点。
菊花图：一颗大小至少为 $2$ 树，除树根外的所有点都是树根的叶子。树上所有的边都由叶子指向树根，或者所有的边都由树根指向叶子。
菊花图森林：由菊花图构成的森林。

考察答案的下界，因为每个入点都至少要被加一条入边，每个出点都至少要加一条出边，答案的下界为 $\max(\text{入点点数},\text{出点点数})$ 。

先考虑一个比较简单的模型，如果给定一个菊花图森林，能否构造出一种方案取到答案的下界。

答案是肯定的。一种朴素的构造方法是：

将每个菊花图取出一条边作为构造大环的边，将这些边上的点依次排开，然后前后相连，构造出一个大环。此时，所有的菊花图都在环上。在这一步中，每个入点匹配到了一个出点。
接下来可以将任意的入点和出点进行配对，因为无论如何连边，最后都可以进入大环，也就得到了强连通的性质。在这一步中，每个入点匹配到了一个出点。
容易发现，到了最后一步的时候，只剩下了入点或者出点，将他们随意的连上大环即可。

观察过程可以发现，前两步增加的边数是 $\min(\text{入点点数},\text{出点点数})$ ，而最后一步增加的边数是 $\max(\text{入点点数},\text{出点点数}) - \min(\text{入点点数},\text{出点点数})$ ，因此一共增加了的边数是 $\max(\text{入点点数},\text{出点点数})$ 。

所以通过这种构造方式，我们总是能取到答案的下界，也就是最优解。

既然菊花图森林有这么好的性质，那么我们能不能将原图转化为菊花图森林，然后就能进行进一步处理了呢？

幸运的是，我们确实有一种方法，总是能把原图转为菊花图森林。

对于孤立点，我们考察它的性质。因为孤立点同时满足入度为 $0$ 且出度为 $0$ ，因此它既是入点，也是出点，且与一条大小为 $2$ 的链是等价的。因此我们可以把每个孤立点当作大小为 $2$ 的链进行处理。

接下来，我们可以把二分图中的节点分为三种：叶子、根、未访问点。

如果存在度数为 $1$ 的节点，则将其设为叶子，并将其唯一相连的节点设为根。
否则随意选择一个节点，将其设为叶子，然后任意选择一个与其相连的节点，并设为根，再断开其它与其相连的边。

重复以上操作，直到没有未访问点为止。

关于正确性的证明：

可以发现，在以上操作中，每个节点都至少有一条边连向其它节点，而叶子只能连向根且只有一条边，根只能连向叶子。

这样，节点之间就组成了一个菊花图森林，并且没有新增入点、出点和孤立点。

综上，本题的解法就是先将原图转化成性质较好的菊花图森林，然后按照上述步骤连边即可。

由于读入数据量较大，如果使用 vector 存图，建议先统计度数，然后提前分配好内存后建边，这样做可以减少大量的常数。也可以直接使用链式前向星存图。

时间复杂度 $O(n + m)$ 。

代码

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n, m, RT = 1, LF = 2;
    std::cin >> n >> m;
    n *= 2;
    std::vector<std::vector<int>> adj(n), nadj(n);
    std::vector<std::array<int, 2>> loop, ans;
    std::vector<int> deg(n), tag(n), p[2];
    std::vector<std::pair<int, int>> edges(m);

    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        ++deg[--u], ++deg[--v];
        edges[i] = { u, v };
    }

    for (int i = 0; i < n ; i++) {
        adj[i].reserve(deg[i]);
    }

    for (int i = 0; i < m; i++) {
        auto [u, v] = edges[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::function<void(int)> dfs = [&](int u) {
        while (adj[u].size() && tag[adj[u].back()] == LF) {
            adj[u].pop_back();
        }
        int v = adj[u].back();
        tag[u] = LF, tag[v] = RT;
        nadj[v].push_back(u);
        while (adj[u].size()) {
            v = adj[u].back();
            if (!tag[v] && --deg[v] == 1) {
                dfs(v);
            }
            adj[u].pop_back();
        }
    };

    for (int i = 0; i < n; i++) {
        if (!deg[i]) {
            loop.push_back({i, i});
        } else if (!tag[i] && deg[i] == 1) {
            dfs(i);
        }
    }

    for (int i = 0; i < n; i++) {
        if (deg[i] && !tag[i]) {
            dfs(i);
        }
    }

    for (int i = 0; i < n; i++) {
        if (tag[i] != RT) {
            continue;
        }
        int u = i, v = nadj[i].back();
        if (u > v) {
            std::swap(u, v);
        }
        loop.push_back({u, v});
        nadj[i].pop_back();
        for (auto x : nadj[i]) {
            p[x >= i].push_back(x);
        }
    }

    n = loop.size();
    m = std::max(p[0].size(), p[1].size());

    ans.resize(n + m);
    for (int i = 0; i < n; i++) {
        ans[i] = {loop[i][1], loop[(i + 1) % n][0]};
    }

    p[0].resize(m, loop[0][0]);
    p[1].resize(m, loop[0][1]);
    for (int i = 0; i < m; i++) {
        ans[i + n] = {p[1][i], p[0][i]};
    }

    std::cout << n + m << '\n';
    for (auto [u, v] : ans) {
        std::cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(4) 回帖

加载中...

话题同步到我的动态回帖

官方题解

“华为杯”2024 年广东工业大学 ACM 新生程序设计竞赛题解

A. 演奏春日影

简明题意

题解

代码

N. 哥伦比亚大选

简明题意

题解

代码

I. 小 P 爱折跃

简明题意

题解

代码

E. 黑塔的奇物

简明题意

题解

代码

C. 交通要塞

简明题意

题解

代码

F. 字符串缩写太多了！

简明题意

题解

代码

J. 好得不能再好了！泰拉投资大师课

简明题意

题解

代码

D. 魔法少女素世世

简明题意

题解

代码

K. 说重话！！！

简明题意

题解

代码

G. 可乐喝雪碧

简明题意

题解

代码

B. 超平坦棋盘

简明题意

题解

代码

H. 雪碧喝可乐

简明题意

题解

代码

M. GLLF 砍木棍

简明题意

题解

代码

L. 向日葵的坡道

简明题意

题解

代码

已采纳

精彩回帖

全部评论

本文相关内容

等你来战

热门推荐