03-10 00:42 已编辑浙江中医药大学 Java 发布于浙江

关注

题解 | 2025年浙江中医药大学程序设计竞赛（同步赛）

2025年浙江中医药大学程序设计竞赛（同步赛）

难度排序

Easy：K、L、C、D、E

Mid：G、H、J、I

Hard：F、B、A

AK：M

K 签到1

出题人：你安好便天晴

人数统计题。

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

#include<bits/stdc++.h>
using namespace std;
int a[1010];
void solve() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int ans = 0, k = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            k++;
            ans += k;
        } else {
            k = 0;
        }
    }
    printf("%d", ans);
}
int main() {
    solve();
    return 0;
}

L 签到2

出题人：你安好便天晴

第一次出现的人名需要注意一下，别的就是语法的问题。

使用 std::map 实现时间复杂度为 $O(T\log T\sum |s_i|)$ .

#include<bits/stdc++.h>
using namespace std;
map<string, int> q, ci;
map<string, int> ans;
int main() {
    int t;
    cin >> t;
    int idx = 1;
    while (t--) {
        int x;
        cin >> x;
        if (x == 1) {
            string str;
            cin >> str;
            if (q[str] + 1 == idx) {
                q[str] = idx;
                ci[str]++;
                ans[str] += ci[str];
                continue;
            }
            if (q[str] != idx && q[str] + 1 != idx) {
                q[str] = idx;
                ans[str] += 1;
                ci[str] = 1;
                continue;
            }
        }
        if (x == 2) {
            string str;
            cin >> str;
            cout << ans[str] << endl;
            continue;
        }
        if (x == 3) {
            idx++;
        }
    }
    return 0;
}

C 天际线的能量平衡

出题人：你安好便天晴

只需要第一个不变，然后每当遇到后一个不合法，便把他变合法，这样的代价和最小。

这样的贪心容易被证明是正确的，具体实现看代码。

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> q(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> q[i];
    }
    for (int i = 2; i <= n; ++i) {
        if (i % 2 == 0) {
            if (q[i] <= q[i - 1]) {
                ans += q[i - 1] + 1 - q[i];
                q[i] = q[i - 1] + 1;
            }
        } else {
            if (q[i] >= q[i - 1]) {
                ans += q[i] - q[i - 1] + 1;
                q[i] = q[i - 1] - 1;
            }
        }
    }
    cout << ans;
    return 0;
}

D 赚米

出题人：你安好便天晴

典型二分答案，二分答案后 $O(n)$ 验证，但是验证的时候每一步都要判一下有没有满足，因为数量增长过快，会导致爆 long long。只要不是单调不增的序列，都会有不大于 $10^{18}$ 的解。

时间复杂度 $O(n\log V)$ .

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
typedef pair<pair<int, int>, int>PIII;
typedef pair<long long, long long>PLL;
long long p[1000010];
void solve() {
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    long long mx = 0, f = 1e10;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &p[i]);
    }
    for (int i = 1; i < n; i++) {
        if (p[i + 1] > p[i]) {
            mx = 1;
            f = min(f, (m + p[i + 1] - p[i] - 1) / (p[i + 1] - p[i]) * p[i]);
        }
    }
    if (mx == 0) {
        printf("-1");
        return;
    }
    long long l = 1, r = f;
    while (l < r) {
        long long x = (l + r) / 2;
        long long y = x;
        for (int i = 1; i < n; i++) {
            if (p[i + 1] > p[i]) {
                y = (y / p[i]) * p[i + 1] + y % p[i];
            }
        }
        if (y - x >= m) {
            r = x;
        } else {
            l = x + 1;
        }
    }
    printf("%lld", l);
}
int main() {
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

E 传送门

出题人：你安好便天晴

简单 bfs，每次都把能到的点塞进队列即可。

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

#include<bits/stdc++.h>
using namespace std;
struct node {
    int idx, step;
};
vector<int> x[100005];
queue<node> q;
int n;
int a[1000005], vis[1000005], dist[1000005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        x[a[i]].push_back(i);
    }
    dist[1] = 0;
    q.push({1, 0});
    while (q.size() != 0) {
        node h = q.front();
        q.pop();
        int idd = h.idx;
        int stp = h.step;
        if (vis[idd] == 1) {
            continue;
        }
        vis[idd] = 1;
        dist[idd] = stp;
        if (idd == n) {
            cout << dist[n] << endl;
            break;
        }
        if (idd + 1 <= n && vis[idd + 1] == 0) {
            q.push({idd + 1, stp + 1});
        }
        if (idd - 1 >= 1 && vis[idd - 1] == 0) {
            q.push({idd - 1, stp + 1});
        }
        for (int i = 0; i < x[a[idd]].size(); i++) {
            if (vis[x[a[idd]][i]] == 0) {
                q.push({x[a[idd]][i], stp + 1});
            }
        }
    }
    return 0;
}

G 最大区间和

出题人：你安好便天晴

$p_i=\sum_{j=1}^i a_j$

$\sum_{i=l}^r a_i=p_r-p_{l-1}$

$(\sum_{i=l}^ra_i)\times (r-l+1)=(p_r-p_{l-1})*(r-(l-1))$

而 $|p[i]|\le5000$ ，因此考虑从 $p_i$ 的值域入手，我们发现，如果 $p_r-p_{l-1}$ 的值一样，那么肯定是区间越长越好，所以我们记录每一种前缀和最早出现的位置 $l_i$ 和最晚出现的位置 $r_i$ , 那么枚举值域,答案就是 $(j-i)(r_j-l_i)$ ，取最大即可。

时间复杂度 $O([\max(p_i)]^2)$ .

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int n;
int a[N];
int s[N];
int idx1[N], idx2[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    memset(idx1, -1, sizeof idx1);
    memset(idx2, -1, sizeof idx2);
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if (a[i] == -1) ++ cnt;
    }
    if (cnt == n) {
        cout << -1 << '\n';
        return 0;
    }
    s[0] = 5000;
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    for (int i = 0; i <= n; i ++ ) idx2[s[i]] = i;
    for (int i = n; i >= 0; i -- ) idx1[s[i]] = i;
    LL res = -1e17;
    for (int i = 0; i <= 10000; i ++ ) {
        for (int j = 0; j <= 10000; j ++ ) {
            if (idx1[i] == -1 || idx2[j] == -1) continue;
            if (idx1[i] > idx2[j]) continue;
            res = max(res, (LL)(j - i) * (idx2[j] - idx1[i]));
        }
    }
    cout << res << '\n';
    return 0;
}

H elo

出题人：你安好便天晴

定义 $dp[r][i]$ 表示选手 $i$ 晋级到第 $r$ 轮的概率。初始状态 $dp[0][i] = 1$ （所有选手默认晋级第 $0$ 轮）。

对于第 $r$ 轮比赛：

分组结构：将选手划分为大小为 $2^r$ 的组，每组分为左半区（前 $2^{r-1}$ 人）和右半区（后 $2^{r-1}$ 人）。
对手来源：左半区选手的对手来自右半区，反之亦然。
转移方程：

dp[r][i] = dp[r-1][i] \times \sum_{\text{对手}j} \left( \frac{A[i]}{A[i] + A[j]} \times dp[r-1][j] \right).

直接暴力转移的复杂度是 $O(n2^{2n})$ ，无法通过本题，考虑值域优化。

1. 分组合并统计

对每个半区统计各实力值的总概率，避免逐个枚举对手。
例如：左半区中实力为 $s$ 的选手总概率为：

sum\_left[s] = \sum_{\substack{i \in \text{左半区} \\ A[i] = s}} dp[r-1][i]

2. 公式变形

将转移方程改写为：

dp[r][i] = dp[r-1][i] \times \sum_{s=1}^{100} \left( \frac{A[i]}{A[i]+s} \times sum\_opponent[s] \right)

其中 $sum\_opponent[s]$ 是对手半区中实力值为 $s$ 的选手的总概率。

时间复杂度 $O(Vn2^n)$ .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ull unsigned long long
using PII = pair<int, int>;
using ld = long double;
using lll = __int128;
const int N = 1e5 + 5, M = 998244353;
ll ksm(ll a, ll b = M - 2) {
    ll res = 1;
    while (b) {
        if (b & 1)res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
ll a[N][101], inv[202];
void solve() {
    int n;
    cin >> n;
    int m = 1 << n;
    ll a0;
    cin >> a0;
    for (int i = 1; i < m; i++) {
        int x;
        cin >> x;
        a[i][x] = 1;
    }
    ll ans = 1;
    for (int i = 1; i <= 200; i++)inv[i] = ksm(i);
    while (m > 1) {
        ll res = 0;
        for (int i = 1; i <= 100; i++) {
            res = (res + a0 * inv[a0 + i] % M * a[1][i]) % M;
        }
        ans = ans * res % M;
        for (int i = 2; i < m; i += 2) {
            for (int j = 1; j <= 100; j++)a[i / 2][j] = 0;
            for (int j = 1; j <= 100; j++) {
                if (!a[i][j])continue;
                for (int k = 1; k <= 100; k++) {
                    ll tmp = inv[j + k] * a[i][j] % M * a[i + 1][k] % M;
                    a[i / 2][j] = (a[i / 2][j] + j * tmp) % M;
                    a[i / 2][k] = (a[i / 2][k] + k * tmp) % M;
                }
            }
        }
        m >>= 1;
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int tt = 1;
    while (tt--)solve();
    return 0;
}

J 并查集

出题人：ygy0

赛前预测一下，应该会有很多人使用线段树合并，至少验题的时候是这样的。

实际上我们只需要维护每个点 $i$ 能否走到 $i+1$ 。

在启发式合并的时候，如果小集合里面的点 $i$ 左边就是大集合，那么 $i-1$ 连向 $i$ ，右边同理。

查询的时候找找 $l$ 的老大是否越过 $r$ 即可。

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

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
vector<int>v[maxn];
int fa[maxn], nxt[maxn];
int find(int x) {
    return nxt[x] == x ? x : nxt[x] = find(nxt[x]);
}
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) v[i].push_back(i), fa[i] = nxt[i] = i;
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            int f1 = fa[l], f2 = fa[r];
            if (f1 == f2) continue;
            if (v[f1].size() < v[f2].size()) swap(f1, f2);
            for (auto x : v[f2]) {
                if (fa[x - 1] == f1) nxt[x - 1] = x;
                if (fa[x + 1] == f1) nxt[x] = x + 1;
                v[f1].push_back(x);
                fa[x] = f1;
            }
        } else {
            if (find(l) >= r) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

I 队列重组

出题人：你安好便天晴

第 $n$ 个位置只能 $t_i=n$ 的人去，第 $n-1$ 个位置只能 $t_i\ge n-1$ 的人去， $\cdots$ ，想明白这一点就很简单了，从后面的位置开始往前填，假设当前要填第 $k$ 个位置，那么从 $t_i\ge k$ 的人中选择初始位置最靠右的过去，使用 std::<set> 记录所有 $t_i\ge k$ 的人初始位置，每次删去最大的即可。

最终可以得到每个人要去的位置，类比计算冒泡排序的交换次数，使用树状数组计算逆序对个数即可得到答案。

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
#define __cs() int T; cin >> T; while (T--)
int n, x, p[maxn];
vector<int>v[maxn];
set<int>s;
struct BIT {
    int n, res, c[maxn];
    void init(int n) {
        this->n = n;
        for (int i = 1; i <= n; ++i) c[i] = 0;
    }
    void add(int x, int k = 1) {
        for (; x <= n; x += x & -x) c[x] += k;
    }
    int sum(int x) {
        for (res = 0; x; x ^= x & -x) res += c[x];
        return res;
    }
} bit;
void solve() {
    cin >> n;
    bit.init(n);
    s.clear();
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        p[x] = i;
        v[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        v[x].push_back(p[i]);
    }
    ll ans = 0;
    for (int i = n; i >= 1; --i) {
        for (auto it : v[i]) s.insert(it);
        if (s.empty()) {
            cout << -1 << '\n';
            return;
        }
        x = *--s.end();
        s.erase(x);
        ans += bit.sum(x);
        bit.add(x);
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    __cs()solve();
    return 0;
}

F 数星星

出题人：ygy0

本题由广州大学校赛改编而来，沿用了原题的名字。

首先对于一颗子树，最小值、最大值、节点个数是容易维护的，然后我们就会有一个期望的公差。

于是，不难想到还需要维护最大公约数。

做完了吗？我们来看下面这个例子： $[2,4,6,10,10]$

此时我们期望的公差是 $2$ ，最大公约数也是 $2$ ，但显然这不是一个等差数列。

不难发现我们唯一需要做的就是判断子树内有没有重复元素（全都一样除外）。

这部分的处理可以 $O(n)$ 完成。

在 dfs 的过程中，我们同时维护以下三个值：

$dfn_u$ ：节点 $u$ 的 dfs 序编号。

$last_c$ ：上一个颜色为 $c$ 的节点的 dfn。

$Max$ ：所有 $last_c$ 最大值。

注意，这里的更新顺序为 $dfn_u,Max,last_c$ 。

在遍历完一棵以 $u$ 为根的子树之后，如果 $Max \geq dfn_u$ ，说明子树内存在重复元素。

本题也可以把树拍成序列再离线处理，处理方法一致。

需要注意的是，离线需要预处理区间 $\gcd$ ，而 ST 表预处理区间 $\gcd$ 的时间复杂度为 $O(n\log n+n\log w)$ ，可以通过本题。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
vector<int>e[maxn];
int c[maxn];
int dfn[maxn], cnt;
int g[maxn], mx[maxn], mi[maxn];
int last[maxn];
int Max, ans;
void dfs(int u) {
    dfn[u] = ++cnt;
    mx[u] = mi[u] = c[u];
    Max = max(Max, last[c[u]]);
    last[c[u]] = cnt;
    for (auto v : e[u]) {
        dfs(v);
        mx[u] = max(mx[u], mx[v]);
        mi[u] = min(mi[u], mi[v]);
        g[u] = __gcd(g[u], abs(c[u] - c[v]));
        g[u] = __gcd(g[u], g[v]);
    }
    if (mi[u] == mx[u]) {
        ans++;
        return;
    }
    if (Max < dfn[u]) {
        if (dfn[u] == cnt) {
            ans++;
            return;
        }
        if ((mx[u] - mi[u]) % (cnt - dfn[u])) return;
        int gap = (mx[u] - mi[u]) / (cnt - dfn[u]);
        if (gap == g[u]) ans++;
    }
}
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) e[i].clear(), g[i] = last[i] = 0;
    cnt = Max = ans = 0;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        e[f].push_back(i);
    }
    dfs(1);
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

B 染色之旅

出题人：ygy0

首先这是一个 基环内向森林。

我们考虑去倒着染色，每个点就至多被染一次，遇到染过的直接用并查集跳过就好了。

按照基环树的常规解法，我们先去找环，再将环上的点和其它点分开处理。

这样写代码量较大，比较考验实现的细节，一不小心可能罚时爆炸。

实际上我们可以使用带权并查集，也就是对每个点再维护一个到老大的距离。

这样在遍历的时候剩余步数 $k$ 是很好控制的。

在对每一个未染色的点染色时，将该点 $i$ 连向 $f_i$ ，同时更新到老大的距离就可以了。

这样我们就完全不需要管这张图的结构，代码也会比较简单。

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

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
struct DSU {
    vector<int>fa, dis;
    DSU(int n) {
        fa.assign(n, 0);
        dis.assign(n, 0);
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int u) {
        if (fa[u] == u) return u;
        int f = find(fa[u]);
        dis[u] += dis[fa[u]];
        return fa[u] = f;
    }
    void merge(int u, int v) {
        int f = find(u);
        dis[v] = dis[u] + 1;
        fa[v] = f;
    }
    int dist(int u) {
        find(u);
        return dis[u];
    }
};
struct {
    int u, k, c;
} q[maxn];
int nxt[maxn], col[maxn];
void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) col[i] = 0;
    for (int i = 1; i <= n; i++) cin >> nxt[i];
    for (int i = 1; i <= m; i++) {
        int u, k, c;
        cin >> u >> k >> c;
        q[i] = {u, k, c};
    }
    DSU dsu(n + 1);
    for (int i = m; i >= 1; i--) {
        auto [u, k, c] = q[i];
        k -= dsu.dist(u);
        u = dsu.find(u);
        while (k >= 0 && col[u] == 0) {
            col[u] = c;
            dsu.merge(nxt[u], u);
            k -= dsu.dist(u);
            u = dsu.find(u);
        }
    }
    for (int i = 1; i <= n; i++) cout << col[i] << " ";
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

给一个本人验题时给出的一个码量很小的递归做法：

依然是倒着暴力修改， $nxt_i$ 表示下一次修改到点 $i$ 时直接跳到点 $nxt_i$ ， $cnt_i$ 记录从 $i$ 到 $nxt_i$ 跳了几步，利用 dfs 的特性在本次修改完成回溯时修改 $nxt_i$ 和 $cnt_i$ ，返回 -1 表示环上的点已经全部修改完成直接退出，需要注意实现的细节。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int t, n, q, nxt[maxn], cnt[maxn], col[maxn], y, u[maxn], k[maxn], c[maxn];
pair<int, int> dfs(int s, int p, int stp, int now, int c, bool fg) {
    if ((p == s && fg) || nxt[p] == -1) return { -1, -1 };
    if (now > stp) return { p, now };
    if (!col[p]) col[p] = c;
    pair<int, int> ans = dfs(s, nxt[p], stp, now + cnt[p], c, 1);
    return { nxt[p] = ans.first, (cnt[p] = ans.second - now) + now };
}
//s表示起点，p表示当前修改的点，stp表示要跳的总步数，now表示现在已经跳了多少步
//c表示修改的颜色，fg表示是否再一次回到了起点（用于判环）
void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &y), nxt[i] = y, cnt[i] = 1, col[i] = 0;
    for (int i = 1; i <= q; ++i) scanf("%d%d%d", &u[i], &k[i], &c[i]);
    for (int i = q; i >= 1; --i) dfs(u[i], u[i], k[i], 0, c[i], 0);
    for (int i = 1; i <= n; ++i) printf("%d%c", col[i], " \n"[i == n]);
}
int main() {
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

A 元素使者的试炼

出题人：ygy0

非负的肯定全选上。

如果选择 $(i,j)$ ，那么第 $i$ 行和第 $j$ 列就可以不选了。

如果某行或某列全是负的，那我们需要在这些行列上选至少一个负的。

怎么选这些负的呢？

考虑反悔贪心。

如果对于行列分别来看，那我们一定是选第 $i$ 行 / 第 $j$ 列上的最大值。

不妨先选上。

如果第 $i$ 行和第 $j$ 列上都需要选一个呢？

这时候选 $(i,j)$ 的价值 $val_{i,j}=c_{i,j} \ -$ 第 $i$ 行最大值 $-$ 第 $j$ 列最大值。

又因为每一行 / 每一列的最大值只能被干掉一次，所以选了 $(i,j)$ 就不能再选 $(i,j_2),(i_2,j)$ 。

这是一个经典的二分图最大权匹配。

左部点 $i$ 和右部点 $j$ 的边权就是 $val_{i,j}$ 。

答案就是非负的 + 行列最大值 + 二分图最大权。

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

#include<bits/stdc++.h>
using namespace std;
struct Hungarian {
    int org_n, org_m, n, inf, ans;
    vector<vector<int>>g;
    vector<int>matchx, matchy, pre;
    vector<bool>visx, visy;
    vector<int>lx, ly;
    vector<int>slack;
    queue<int>q;
    Hungarian(int _n, int _m) {
        org_n = _n, org_m = _m, n = max(_n, _m), inf = 1e9, ans = 0;
        g.assign(n, vector<int>(n, 0));
        matchx.assign(n, -1);
        matchy.assign(n, -1);
        pre.assign(n, 0);
        visx.assign(n, 0);
        visy.assign(n, 0);
        lx.assign(n, 0);
        ly.assign(n, 0);
        slack.assign(n, 0);
    }
    void addedge(int u, int v, int w) {
        g[u][v] = max(0, w);
    }
    bool check(int v) {
        visy[v] = 1;
        if (matchy[v] != -1) {
            q.push(matchy[v]);
            visx[matchy[v]] = 1;
            return 0;
        }
        while (v != -1) {
            matchy[v] = pre[v];
            swap(v, matchx[pre[v]]);
        }
        return 1;
    }
    void bfs(int i) {
        while (q.size()) q.pop();
        q.push(i);
        visx[i] = 1;
        while (1) {
            while (q.size()) {
                int u = q.front();
                q.pop();
                for (int v = 0; v < n; v++) {
                    if (visy[v] == 0) {
                        int delta = lx[u] + ly[v] - g[u][v];
                        if (slack[v] >= delta) {
                            pre[v] = u;
                            if (delta) slack[v] = delta;
                            else if (check(v)) return;
                        }
                    }
                }
            }
            int a = inf;
            for (int j = 0; j < n; j++) {
                if (visy[j] == 0) a = min(a, slack[j]);
            }
            for (int j = 0; j < n; j++) {
                if (visx[j]) lx[j] -= a;
                if (visy[j]) ly[j] += a;
                else slack[j] -= a;
            }
            for (int j = 0; j < n; j++) {
                if (visy[j] == 0 && slack[j] == 0 && check(j)) return;
            }
        }
    }
    int solve() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                lx[i] = max(lx[i], g[i][j]);
            }
        }
        for (int i = 0; i < n; i++) {
            fill(slack.begin(), slack.end(), inf);
            fill(visx.begin(), visx.end(), 0);
            fill(visy.begin(), visy.end(), 0);
            bfs(i);
        }
        for (int i = 0; i < n; i++) {
            if (g[i][matchx[i]]) ans += g[i][matchx[i]];
            else matchx[i] = -1;
        }
        return ans;
    }
};
int c[305][305];
int h[305], l[305];
int main() {
    int n, m;
    cin >> n >> m;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
            if (c[i][j] >= 0) {
                ans += c[i][j];
                h[i] = 1, l[j] = 1;
            }
        }
    }
    vector<int>hmx(n, -1e9);
    vector<int>row;
    for (int i = 0; i < n; i++) {
        if (h[i] == 0) {
            for (int j = 0; j < m; j++) hmx[i] = max(hmx[i], c[i][j]);
            row.push_back(i);
            ans += hmx[i];
        }
    }
    vector<int>lmx(m, -1e9);
    vector<int>col;
    for (int j = 0; j < m; j++) {
        if (l[j] == 0) {
            for (int i = 0; i < n; i++) lmx[j] = max(lmx[j], c[i][j]);
            col.push_back(j);
            ans += lmx[j];
        }
    }
    int N = row.size(), M = col.size();
    Hungarian km(N, M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int w = max(0, c[row[i]][col[j]] - hmx[row[i]] - lmx[col[j]]);
            km.addedge(i, j, w);
        }
    }
    ans += km.solve();
    cout << ans << '\n';
    return 0;
}

M.数论测试

出题人：pvzelyyds

记 $f(k)$ 表示 $\operatorname{lcm}(x,y)=k,[\gcd(x,y)]^3|xy$ 的方案数，设 $k$ 的质因数分解为 $p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$ ， $x$ 的质因数分解为 $p_1^{x_1}p_2^{x_2}\cdots p_m^{x_m}$ ， $y$ 的质因数分解为 $p_1^{y_1}p_2^{y_2}\cdots p_m^{y_m}$ ，于是对每一个质数 $p_i$ 其指数都应该满足 $\max(x_i,y_i)=c_i,3\min(x_i,y_i)\le x_i+y_i$ ，方案数为 $f(p_i^{c_i})$ ，那么总方案数为 $f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_m^{c_m})$ ，即 $f(p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m})=f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_m^{c_m})$ ，因此 $f(x)$ 为积性函数。

$f(p_i^{c_i})=2\sum_\limits{0\le e\le c_i,3e\le e+c_i}=2(\lfloor\frac{c_i}{2}\rfloor+1)$ .

考虑使用 PN 筛求出 $f(x)$ 的前缀和，构造 $g(x)=\sigma(x)$ 及 $h(x)$ 满足 $f(x)=(g*h)(x)$ ，其中 $\sigma(x)$ 表示 $x$ 的因数个数， $*$ 表示狄利克雷卷积。则满足质数处 $f(p)=g(p)=2$ 。

归纳易证 $h(1)=h(p^2)=1,h(p^k)=2\cdot(-1)^k(k>2)$ ，不想证明也可以直接暴力计算或者打表。

利用 $\sum\limits_{k=1}^n\sigma(k)=\sum_\limits{i=1}^n\lfloor\frac{n}{i}\rfloor$ 和整除分块可以在 $O(\sqrt n)$ 时间内计算 $\sigma$ 的前 $n$ 项和。

时间复杂度分析：设某一 Powerful Number 被表示为 $x^2y^3$ ，计算 $\sum\limits_{k=1}^{\lfloor\frac{n}{x^2y^3}\rfloor}\sigma(k)$ 的复杂度为 $O(\sqrt\frac{n}{x^2y^3})$ .

则 $T(n)=\iint\limits_{_{1\le x^2y^3\le n}}\sqrt\frac{n}{x^2y^3}dxdy=\sqrt n\int_1^{\sqrt n}\frac{dx}{x}\int_1^{\sqrt[3]{\frac{n}{x^2}}}y^{-\frac{3}{2}}dy=2\sqrt n\int_1^{\sqrt n}(\frac{1}{x}-\frac{x^{-\frac{2}{3}}}{n^\frac{1}{6}})dx=2\sqrt n(\ln\sqrt n-3+3n^{-\frac{1}{6}})=O(\sqrt n\log n)$ .