4285 字
21 分钟
11.10 比赛全套题解 (CodeForces A ~ M)
2026-10-10算法竞赛算法竞赛CodeForces题解模拟赛

目录与题目汇总#

题号题目名称核心考点与算法CodeForces 原题链接
AWater Buying贪心、数学CF 1118A
BEdge Deletion图论、Dijkstra 最短路树CF 1076D
CBasketball Exercise线性 DPCF 1195C
DTree Painting换根 DPCF 1187E
ELCM数论（因数分解）CF 1068B
FEasy Problem状态机线性 DPCF 1096D
GCatch Overflow!栈模拟循环CF 1175B
HMagic Ship二分答案 + 曼哈顿距离CF 1117C
IMaximal Continuous Rest环形数组断环成链CF 1141B
JCow and Snacks图论生成树、并查集CF 1209D
KArray and Segments (Hard version)线段树扫描线CF 1108E2
LVasya and Triangle数论与几何构造CF 1030D
MTwo Arrays and Sum of Functions贡献法 + 排序不等式CF 1165E

A. Water Buying (CodeForces 1118A)#

  • 标签：贪心、数学

题目大意#

需要购买 nn 升水。1 升装售价 aa，2 升装售价 bb。求最少需要花费多少钱。

算法思路#

比较两种购买方式的单价性价比：

  • 买两瓶 1 升装需要花费 2a2a。
  • 若 2a≤b2a \le b，说明 1 升装更划算或价格相同，全部购买 1 升装即可，花费为 n×an \times a。
  • 若 2a>b2a > b，说明 2 升装更划算。应尽可能多买 2 升装，即购买 ⌊n/2⌋\lfloor n / 2 \rfloor 瓶 2 升装；若 nn 为奇数，剩下的 1 升补买 1 瓶 1 升装，总花费为： ⌊n/2⌋×b+(n mod 2)×a\lfloor n / 2 \rfloor \times b + (n \bmod 2) \times a

综合两式，直接取最小值即可： min⁡(n×a,  ⌊n/2⌋×b+(n mod 2)×a)\min\Big(n \times a,\; \lfloor n / 2 \rfloor \times b + (n \bmod 2) \times a\Big)

复杂度分析#

  • 时间复杂度：O(1)O(1)。
  • 空间复杂度：O(1)O(1)。

参考代码#

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


void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int x = n * a;
    int y = (n % 2) * a + (n / 2) * b;
    cout << min(x, y) << "\n";
}


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

B. Edge Deletion (CodeForces 1076D)#

  • 标签：图论、Dijkstra、最短路树 (SPT)、贪心

题目大意#

给定包含 nn 个点、mm 条边的带正权连通无向图。现在需要保留至多 kk 条边。 定义“好点”：如果某个节点在保留边构成的新图中的最短路（以 1 为源点）与原图完全相等，则称该点为好点。 要求最大化好点的数量，输出保留的边数及保留边的编号。

算法思路#

  1. 从源点 1 出发的所有单源最短路径构成一棵最短路树（Shortest Path Tree, SPT），最多包含 n−1n-1 条边。
  2. 观察性质：只要一个点 vv 到根节点 1 的路径上的所有树边都被保留，vv 在新图中的最短距离就一定与原图一致，因此 vv 成为好点。
  3. 任何一条保留的边最多只能将 1 个新的好点连接到以 1 为根的连通分量中。因此保留 kk 条边最多产生 1+min⁡(k,n−1)1 + \min(k, n-1) 个好点。
  4. 我们在运行 Dijkstra 算法时，当一个点 uu 被从优先队列中取出（距离确定）时，记录将其松弛的树边 parent_edge[u]。
  5. 按照节点被确定的先后顺序（即距离递增的拓扑/BFS顺序），依次选取前 min⁡(k,n−1)\min(k, n-1) 条树边。因为边权为正，后确定的节点的祖先必已确定，这样保证了被选取的边始终构成包含根节点 1 的一棵连通子树。

复杂度分析#

  • 时间复杂度：O(mlog⁡n)O(m \log n)。
  • 空间复杂度：O(n+m)O(n + m)。

参考代码#

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


struct Edge {
    int to;
    long long w;
    int id;
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;


    vector<vector<Edge>> adj(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w, i});
        adj[v].push_back({u, w, i});
    }


    const long long INF = 1e18;
    vector<long long> dist(n + 1, INF);
    vector<int> parent_edge(n + 1, 0);
    vector<bool> vis(n + 1, false);


    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});


    vector<int> ans;


    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();


        if (vis[u]) continue;
        vis[u] = true;


        if (u != 1 && (int)ans.size() < k) {
            ans.push_back(parent_edge[u]);
        }


        for (const auto& edge : adj[u]) {
            int v = edge.to;
            if (d + edge.w < dist[v]) {
                dist[v] = d + edge.w;
                parent_edge[v] = edge.id;
                pq.push({dist[v], v});
            }
        }
    }


    cout << ans.size() << "\n";
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i] << (i + 1 == (int)ans.size() ? "" : " ");
    }
    cout << "\n";


    return 0;
}

C. Basketball Exercise (CodeForces 1195C)#

  • 标签：动态规划、线性 DP

题目大意#

两排学生，每排各 nn 人。第 1 排学生身高为 h1,ih_{1,i}，第 2 排学生身高为 h2,ih_{2,i}。 要求挑选若干学生组成篮球队，选出的学生列号必须严格单调递增，且队伍所在的行必须严格交替。求选出学生的身高总和最大值。

算法思路#

定义状态：

  • f[i][0]f[i][0]：在前 ii 列中选人，且第 ii 列选第 1 排的最大身高总和；
  • f[i][1]f[i][1]：在前 ii 列中选人，且第 ii 列选第 2 排的最大身高总和。

转移方程： f[i][0]=max⁡(f[i−1][1],f[i−2][1])+h1,if[i][0] = \max(f[i-1][1], f[i-2][1]) + h_{1, i} f[i][1]=max⁡(f[i−1][0],f[i−2][0])+h2,if[i][1] = \max(f[i-1][0], f[i-2][0]) + h_{2, i}

最终答案为 max⁡(f[n][0],f[n][1],f[n−1][0],f[n−1][1])\max(f[n][0], f[n][1], f[n-1][0], f[n-1][1])。

复杂度分析#

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


int f[100005][2], a[100005][2];


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    if (!(cin >> n)) return 0;


    for (int i = 1; i <= n; i++) cin >> a[i][0];
    for (int i = 1; i <= n; i++) cin >> a[i][1];


    f[1][0] = a[1][0];
    f[1][1] = a[1][1];


    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 1; j++) {
            f[i][j] = max(f[i - 1][1 - j], f[i - 2][1 - j]) + a[i][j];
        }
    }


    cout << max({f[n - 1][0], f[n - 1][1], f[n][0], f[n][1]}) << "\n";
    return 0;
}

D. Tree Painting (CodeForces 1187E)#

  • 标签：树形 DP、换根 DP

题目大意#

给定包含 nn 个节点的无向树，初始所有点均为白色。

  • 第 1 步：任选一个白点染黑，得分加上该点所在的白色连通块大小（初始为 nn）。
  • 第 ii 步（2≤i≤n2 \le i \le n）：选取一个与已有黑点相邻的白点染黑，得分加上该点染色前所在白色连通块的大小。 求将全部节点染黑所能获得的最大总得分。

算法思路#

  1. 当以 rr 为初始根节点时，总得分为所有节点以 rr 为根时的子树大小之和： dp[r]=∑u=1nsizer(u)dp[r] = \sum_{u=1}^n \text{size}_r(u)
  2. 换根 DP 转移：
    • 第一次 DFS：选 1 为根，统计子树大小 sz[u]sz[u] 以及 dp[1]=∑sz[u]dp[1] = \sum sz[u]。
    • 第二次 DFS：根由 uu 移动到子节点 vv： dp[v]=dp[u]−sz[v]+(n−sz[v])=dp[u]+n−2⋅sz[v]dp[v] = dp[u] - sz[v] + (n - sz[v]) = dp[u] + n - 2 \cdot sz[v]
  3. 遍历所有节点求 max⁡dp[u]\max dp[u]。

复杂度分析#

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    if (!(cin >> n)) return 0;


    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    vector<long long> sz(n + 1, 0);
    vector<long long> dp(n + 1, 0);


    auto dfs1 = [&](auto& self, int u, int p) -> void {
        sz[u] = 1;
        for (int v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
            sz[u] += sz[v];
        }
        dp[1] += sz[u];
    };


    dfs1(dfs1, 1, 0);


    long long max_ans = dp[1];


    auto dfs2 = [&](auto& self, int u, int p) -> void {
        for (int v : adj[u]) {
            if (v == p) continue;
            dp[v] = dp[u] - sz[v] + (n - sz[v]);
            max_ans = max(max_ans, dp[v]);
            self(self, v, u);
        }
    };


    dfs2(dfs2, 1, 0);


    cout << max_ans << "\n";
    return 0;
}

E. LCM (CodeForces 1068B)#

  • 标签：数论、因数分解

题目大意#

给定正整数 bb（b≤1010b \le 10^{10}），对于所有正整数 aa，求 LCM(a,b)a\frac{\text{LCM}(a, b)}{a} 的不同取值个数。

算法思路#

由公式： LCM(a,b)a=bgcd⁡(a,b)\frac{\text{LCM}(a, b)}{a} = \frac{b}{\gcd(a, b)} 由于 gcd⁡(a,b)\gcd(a, b) 可以取遍 bb 的每一个正因数，因此不同取值的个数严格等于 bb 的因数个数 d(b)d(b)。在 O(b)O(\sqrt{b}) 内枚举因数即可。

复杂度分析#

  • 时间复杂度：O(b)O(\sqrt{b})。
  • 空间复杂度：O(1)O(1)。

参考代码#

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


signed main() {
    int b;
    if (cin >> b) {
        int ans = 0;
        for (int i = 1; i * i <= b; ++i) {
            if (b % i == 0) {
                ans += (i * i == b ? 1 : 2);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

F. Easy Problem (CodeForces 1096D)#

  • 标签：动态规划、字符串

题目大意#

给定长度为 nn 的字符串 ss。删除第 ii 个字符的花费为 aia_i。求最小的花费，使得剩余的字符串中不包含子序列 "hard"。

算法思路#

维护前缀串消除各个前缀子序列的代价：

  • dp[0]dp[0]：无子序列 "h"；
  • dp[1]dp[1]：无子序列 "ha"；
  • dp[2]dp[2]：无子序列 "har"；
  • dp[3]dp[3]：无子序列 "hard"。

转移：

  • s[i]==’h’s[i] == \text{'h'}：dp[0]←dp[0]+aidp[0] \gets dp[0] + a_i；
  • s[i]==’a’s[i] == \text{'a'}：dp[1]←min⁡(dp[1]+ai,dp[0])dp[1] \gets \min(dp[1] + a_i, dp[0])；
  • s[i]==’r’s[i] == \text{'r'}：dp[2]←min⁡(dp[2]+ai,dp[1])dp[2] \gets \min(dp[2] + a_i, dp[1])；
  • s[i]==’d’s[i] == \text{'d'}：dp[3]←min⁡(dp[3]+ai,dp[2])dp[3] \gets \min(dp[3] + a_i, dp[2])。

答案为 dp[3]dp[3]。

复杂度分析#

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)。

参考代码#

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    if (!(cin >> n)) return 0;


    string s;
    cin >> s;


    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];


    vector<long long> dp(4, 0);


    for (int i = 0; i < n; i++) {
        if (s[i] == 'h') {
            dp[0] += a[i];
        } else if (s[i] == 'a') {
            dp[1] = min(dp[1] + a[i], dp[0]);
        } else if (s[i] == 'r') {
            dp[2] = min(dp[2] + a[i], dp[1]);
        } else if (s[i] == 'd') {
            dp[3] = min(dp[3] + a[i], dp[2]);
        }
    }


    cout << dp[3] << "\n";
    return 0;
}

G. Catch Overflow! (CodeForces 1175B)#

  • 标签：栈模拟、大数防溢出

题目大意#

初始 x=0x = 0。程序包含 for n、end、add。add 会累加外层循环的连乘倍数。若 x≥232x \ge 2^{32} 输出 OVERFLOW!!!，否则输出最终的 xx。

算法思路#

使用栈维护循环倍数的前缀积。遇到乘积超过 2322^{32} 时截断为 2322^{32} 防止越界。执行 add 时累加，若 ≥232\ge 2^{32} 立即输出 OVERFLOW!!!。

复杂度分析#

  • 时间复杂度：O(l)O(l)。
  • 空间复杂度：O(l)O(l)。

参考代码#

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


const int max_ = 1LL << 32;


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int l;
    if (!(cin >> l)) return 0;


    vector<int> stk;
    stk.reserve(l + 1);
    stk.push_back(1);


    int ans = 0;
    for (int i = 0; i < l; i++) {
        string s;
        cin >> s;
        if (s == "for") {
            int n;
            cin >> n;
            stk.push_back(min(max_, stk.back() * n));
        } else if (s == "end") {
            stk.pop_back();
        } else if (s == "add") {
            ans += stk.back();
            if (ans >= max_) {
                cout << "OVERFLOW!!!\n";
                return 0;
            }
        }
    }


    cout << ans << "\n";
    return 0;
}

H. Magic Ship (CodeForces 1117C)#

  • 标签：二分答案、前缀和、曼哈顿距离

题目大意#

起点 (x1,y1)(x_1, y_1)，终点 (x2,y2)(x_2, y_2)。风力周期为 nn。每天风力推船 1 步，船自主可走 1 步或不动。求最少到达天数；无法到达输出 -1。

算法思路#

二分天数 midmid。计算前 midmid 天风力位移 (wx,wy)(wx, wy)，风力吹到点为 (curx,cury)=(x1+wx,y1+wy)(cur_x, cur_y) = (x_1 + wx, y_1 + wy)。 可行充要条件： ∣x2−curx∣+∣y2−cury∣≤mid|x_2 - cur_x| + |y_2 - cur_y| \le mid 二分上界取 101510^{15}。

复杂度分析#

  • 时间复杂度：O(n+log⁡(max_ans))O(n + \log(\text{max\_ans}))。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int x1, y1, x2, y2;
    if (!(cin >> x1 >> y1 >> x2 >> y2)) return 0;


    int n;
    string s;
    cin >> n >> s;


    if (x1 == x2 && y1 == y2) {
        cout << 0 << "\n";
        return 0;
    }


    vector<int> px(n + 1, 0), py(n + 1, 0);
    for (int i = 0; i < n; i++) {
        px[i + 1] = px[i];
        py[i + 1] = py[i];
        if (s[i] == 'U') py[i + 1]++;
        else if (s[i] == 'D') py[i + 1]--;
        else if (s[i] == 'L') px[i + 1]--;
        else if (s[i] == 'R') px[i + 1]++;
    }


    int l = 1, r = 1e15;
    int ans = -1;


    auto check = [&](int mid) -> bool {
        int cnt = mid / n, rem = mid % n;
        int wx = cnt * px[n] + px[rem], wy = cnt * py[n] + py[rem];
        int cur_x = x1 + wx, cur_y = y1 + wy;
        return mid >= llabs(x2 - cur_x) + llabs(y2 - cur_y);
    };


    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }


    cout << ans << "\n";
    return 0;
}

I. Maximal Continuous Rest (CodeForces 1141B)#

  • 标签：环形数组、断环成链

题目大意#

给定循环 0/1 数组，求最长连续 1 的长度。

算法思路#

数组倍长为 2n2n，统计最大连续 1 计数，与 nn 取 min⁡\min。

复杂度分析#

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    if (!(cin >> n)) return 0;


    vector<int> a(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }


    int ans = 0, cur = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (a[i] == 1) {
            cur++;
            ans = max(ans, cur);
        } else {
            cur = 0;
        }
    }


    ans = min(ans, n);
    cout << ans << "\n";
    return 0;
}

J. Cow and Snacks (CodeForces 1209D)#

  • 标签：图论、连通分量、并查集

题目大意#

nn 种零食，kk 位客人。每人喜好两种零食，若都已被拿走则伤心。求最少伤心人数。

算法思路#

大小为 VV 的连通块最多满足 V−1V-1 人。使用并查集合并，每次成功合并说明增加 1 位满意客人。答案为 k−成功合并次数k - \text{成功合并次数}。

复杂度分析#

  • 时间复杂度：O(k⋅α(n))O(k \cdot \alpha(n))。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
            return true;
        }
        return false;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, k;
    if (!(cin >> n >> k)) return 0;


    DSU dsu(n);
    int happy = 0;


    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        if (dsu.unite(x, y)) {
            happy++;
        }
    }


    int sad = k - happy;
    cout << sad << "\n";
    return 0;
}

K. Array and Segments (Hard version) (CodeForces 1108E2)#

  • 标签：线段树、扫描线、贪心

题目大意#

选择区间子集执行 −1-1，最大化 max⁡(a′)−min⁡(a′)\max(a') - \min(a')。

算法思路#

若最小值在 pp 取得，最优策略是选择全部覆盖 pp 的区间。扫描线遍历 p∈[1,n]p \in [1, n]，在 ljl_j 时线段树区间 −1-1，在 rjr_j 之后区间 +1+1，全局维护 max⁡−min⁡\max - \min。

复杂度分析#

  • 时间复杂度：O(n+mlog⁡n)O(n + m \log n)。
  • 空间复杂度：O(n+m)O(n + m)。

参考代码#

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


struct Node {
    int mn, mx, lazy;
};


const int INF = 1e9;
vector<Node> tree;
vector<int> a;


void push_up(int u) {
    tree[u].mn = min(tree[u << 1].mn, tree[u << 1 | 1].mn);
    tree[u].mx = max(tree[u << 1].mx, tree[u << 1 | 1].mx);
}


void apply(int u, int val) {
    tree[u].mn += val;
    tree[u].mx += val;
    tree[u].lazy += val;
}


void push_down(int u) {
    if (tree[u].lazy != 0) {
        apply(u << 1, tree[u].lazy);
        apply(u << 1 | 1, tree[u].lazy);
        tree[u].lazy = 0;
    }
}


void build(int u, int l, int r) {
    tree[u].lazy = 0;
    if (l == r) {
        tree[u].mn = a[l];
        tree[u].mx = a[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}


void update(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        apply(u, val);
        return;
    }
    push_down(u);
    int mid = l + (r - l) / 2;
    if (ql <= mid) update(u << 1, l, mid, ql, qr, val);
    if (qr > mid) update(u << 1 | 1, mid + 1, r, ql, qr, val);
    push_up(u);
}


struct Segment {
    int l, r, id;
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m;
    if (!(cin >> n >> m)) return 0;


    a.resize(n + 1);
    int orig_min = INF, orig_max = -INF;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        orig_min = min(orig_min, a[i]);
        orig_max = max(orig_max, a[i]);
    }


    vector<Segment> segs(m);
    vector<vector<int>> start_at(n + 2), end_at(n + 2);
    for (int i = 0; i < m; i++) {
        cin >> segs[i].l >> segs[i].r;
        segs[i].id = i + 1;
        start_at[segs[i].l].push_back(i);
        end_at[segs[i].r].push_back(i);
    }


    tree.resize(4 * (n + 1));
    build(1, 1, n);


    int best_diff = orig_max - orig_min;
    int best_p = 0;


    for (int p = 1; p <= n; p++) {
        for (int idx : start_at[p]) {
            update(1, 1, n, segs[idx].l, segs[idx].r, -1);
        }


        int cur_diff = tree[1].mx - tree[1].mn;
        if (cur_diff > best_diff) {
            best_diff = cur_diff;
            best_p = p;
        }


        for (int idx : end_at[p]) {
            update(1, 1, n, segs[idx].l, segs[idx].r, 1);
        }
    }


    vector<int> chosen;
    if (best_p > 0) {
        for (int i = 0; i < m; i++) {
            if (segs[i].l <= best_p && best_p <= segs[i].r) {
                chosen.push_back(segs[i].id);
            }
        }
    }


    cout << best_diff << "\n";
    cout << chosen.size() << "\n";
    for (int i = 0; i < (int)chosen.size(); i++) {
        cout << chosen[i] << (i + 1 == (int)chosen.size() ? "" : " ");
    }
    cout << "\n";


    return 0;
}

L. Vasya and Triangle (CodeForces 1030D)#

  • 标签：数论、构造、几何

题目大意#

在 n×mn \times m 区域构造三角形使面积为 nmk\frac{nm}{k}。

算法思路#

必要条件 k∣2nmk \mid 2nm。构造直角边 xy=2nmkxy = \frac{2nm}{k}。

  • 若 kk 为偶数：x=ngcd⁡(n,k/2)x = \frac{n}{\gcd(n, k/2)}，y=m(k/2)/gcd⁡(n,k/2)y = \frac{m}{(k/2)/\gcd(n, k/2)}；
  • 若 kk 为奇数：求出基础值后将因子 2 乘给不超过边界的一维。

复杂度分析#

  • 时间复杂度：O(log⁡(min⁡(n,k)))O(\log(\min(n, k)))。
  • 空间复杂度：O(1)O(1)。

参考代码#

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


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;


    if ((2 * n * m) % k != 0) {
        cout << "NO\n";
        return 0;
    }


    cout << "YES\n";
    int x, y;
    if (k % 2 == 0) {
        int kp = k / 2;
        int g = gcd(n, kp);
        x = n / g;
        y = m / (kp / g);
    } else {
        int g = gcd(n, k);
        x = n / g;
        y = m / (k / g);
        if (2 * x <= n) {
            x *= 2;
        } else {
            y *= 2;
        }
    }


    cout << "0 0\n";
    cout << x << " 0\n";
    cout << "0 " << y << "\n";


    return 0;
}

M. Two Arrays and Sum of Functions (CodeForces 1165E)#

  • 标签：贡献法、排序不等式

题目大意#

重排数组 bb，求 ∑1≤l≤r≤n∑i=lraibi\sum_{1 \le l \le r \le n} \sum_{i=l}^r a_i b_i 模 998244353 的最大值。

算法思路#

计算贡献 wi=ai⋅i⋅(n−i+1)w_i = a_i \cdot i \cdot (n - i + 1)。 排序不等式：将 ww 和 bb 均升序排序后对应相乘。注意排序前切勿取模。

复杂度分析#

  • 时间复杂度：O(nlog⁡n)O(n \log n)。
  • 空间复杂度：O(n)O(n)。

参考代码#

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


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n;
    if (!(cin >> n)) return 0;


    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];


    vector<long long> w(n);
    for (int i = 0; i < n; i++) {
        w[i] = a[i] * (i + 1LL) * (n - i);
    }


    sort(w.begin(), w.end());
    sort(b.begin(), b.end());


    const long long MOD = 998244353;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long term = (w[i] % MOD) * (b[i] % MOD) % MOD;
        ans = (ans + term) % MOD;
    }


    cout << ans << "\n";
    return 0;
}
11.10 比赛全套题解 (CodeForces A ~ M)
https://zxhyczx.github.io/blog/posts/contest-11-10-solutions/
作者
ZXHYCZX
发布于
2026-10-10
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接，与更多人分享本文。

继续阅读

换条路线

从其他文章中稳定抽取

异或在算法竞赛中的应用