IO竞赛2025年题目解析：中级难度（6-7）

安全风信子

发布于 2025-11-13 13:21:51

740

文章被收录于专栏：AI SPPECHAI SPPECH

引言

中级难度的IO竞赛题目是竞赛中的核心部分，也是选手们拉开差距的关键。2025年的中级难度（难度系数6-7）题目综合考察了选手的算法设计、数据结构应用、数学建模和问题分析能力。本文将深入解析2025年中级难度的IO竞赛题目，帮助选手们突破瓶颈，提升解题能力。

难度进阶路径: 入门(1-3) → 基础(4-5) → 中级(6-7) → 高级(8-10)

难度系数	考察重点	核心知识点	学习目标
6-7	高级算法、数据结构综合应用	高级动态规划、图论、数论、几何	掌握复杂算法的设计和实现，具备解决综合问题的能力

第一章：2025年IO竞赛中级难度题目概述

根据2025年NOI修订版大纲，中级难度（CSP-S提高）的知识点难度系数为6-7，这一阶段的题目开始考察更高级的算法和数据结构的综合应用。

中级难度题目类型分布:
高级动态规划 → 25%
图论算法 → 20%
数论 → 15%
计算几何 → 15%
数据结构综合应用 → 15%
其他 → 10%

中级难度题目的特点：

算法复杂度分析成为解题的关键
问题建模难度增加，需要将实际问题转化为算法模型
数据结构的选择和实现更加复杂
代码量增加，对代码的正确性和效率要求更高
往往需要结合多种算法和数据结构来解决问题

第二章：难度系数6题目解析

难度系数6的题目是中级难度的基础，开始涉及更复杂的算法设计和数据结构应用。以下是8道典型的难度系数6题目解析。

2.1 题目1：区间动态规划

题目描述：给定一个长度为n的数组，每次可以合并相邻的两个数，合并后的数为这两个数的和，合并的代价为这两个数的和。要求将整个数组合并成一个数，求最小的合并代价。

解题思路：这是一个典型的区间动态规划问题。设dp[i][j]表示合并区间[i,j]的最小代价。状态转移方程为：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])，其中k从i到j-1。

C++代码实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int min_merge_cost(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<int> prefix_sum(n + 1, 0);
    
    // 计算前缀和
    for (int i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + nums[i];
    }
    
    // 区间长度从2开始
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            int sum = prefix_sum[j + 1] - prefix_sum[i];
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum);
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << min_merge_cost(nums) << endl;
    return 0;
}

2.2 题目2：最小生成树（Prim算法）

题目描述：给定一个无向图，使用Prim算法找到其最小生成树。

解题思路：Prim算法的基本思想是从一个起始顶点开始，每次选择一条与当前生成树相连的最小权值的边，将边的另一端顶点加入生成树，直到所有顶点都加入生成树。

C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // (权值, 顶点)

int prim(int n, vector<vector<pii>>& graph) {
    vector<bool> visited(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int total_weight = 0;
    int count = 0;
    
    // 从顶点0开始
    pq.push({0, 0});
    
    while (!pq.empty() && count < n) {
        int u = pq.top().second;
        int weight = pq.top().first;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        total_weight += weight;
        count++;
        
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            if (!visited[v]) {
                pq.push({w, v});
            }
        }
    }
    return total_weight;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back({v, weight});
        graph[v].push_back({u, weight});
    }
    int min_weight = prim(n, graph);
    cout << "最小生成树的总权值：" << min_weight << endl;
    return 0;
}

2.3 题目3：二分图匹配（匈牙利算法）

题目描述：给定一个二分图，求其最大匹配数。

解题思路：使用匈牙利算法来求解二分图的最大匹配问题。该算法的核心思想是寻找增广路径。

C++代码实现：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& match) {
    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            if (match[v] == -1 || dfs(match[v], graph, visited, match)) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungarian_algorithm(int n, int m, vector<vector<int>>& graph) {
    vector<int> match(m, -1);
    int result = 0;
    for (int u = 0; u < n; u++) {
        vector<bool> visited(m, false);
        if (dfs(u, graph, visited, match)) {
            result++;
        }
    }
    return result;
}

int main() {
    int n, m, e;
    cin >> n >> m >> e;
    vector<vector<int>> graph(n);
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    cout << hungarian_algorithm(n, m, graph) << endl;
    return 0;
}

2.4 题目4：树状数组（Fenwick Tree）

题目描述：实现树状数组，支持单点更新和区间查询。

解题思路：树状数组是一种支持单点更新和区间查询的数据结构。它的核心操作是lowbit运算，即取一个数的二进制表示中最低位的1所对应的值。

C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) {
        tree.resize(size + 1, 0);
    }
    
    // 计算lowbit
    int lowbit(int x) {
        return x & (-x);
    }
    
    // 单点更新
    void update(int index, int delta) {
        while (index < tree.size()) {
            tree[index] += delta;
            index += lowbit(index);
        }
    }
    
    // 区间查询[1, index]
    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowbit(index);
        }
        return sum;
    }
    
    // 区间查询[l, r]
    int range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    FenwickTree fenwick(n);
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        fenwick.update(i, val);
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) { // 单点更新
            int index, delta;
            cin >> index >> delta;
            fenwick.update(index, delta);
        } else if (op == 2) { // 区间查询
            int l, r;
            cin >> l >> r;
            cout << fenwick.range_query(l, r) << endl;
        }
    }
    return 0;
}

2.5 题目5：线段树

题目描述：实现线段树，支持区间更新和区间查询。

解题思路：线段树是一种支持区间查询和区间更新的数据结构。它通过将区间划分为多个子区间，每个节点代表一个子区间，从而实现高效的区间操作。

C++代码实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    vector<int> lazy;
    vector<int> nums;
    int n;
    
    void push_down(int node, int start, int end) {
        if (lazy[node] != 0 && start != end) {
            int mid = (start + end) / 2;
            tree[2 * node + 1] += lazy[node] * (mid - start + 1);
            tree[2 * node + 2] += lazy[node] * (end - mid);
            lazy[2 * node + 1] += lazy[node];
            lazy[2 * node + 2] += lazy[node];
            lazy[node] = 0;
        }
    }
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
    
    void update_range(int node, int start, int end, int l, int r, int delta) {
        push_down(node, start, end);
        if (start > r || end < l) {
            return;
        }
        if (l <= start && end <= r) {
            tree[node] += delta * (end - start + 1);
            if (start != end) {
                lazy[2 * node + 1] += delta;
                lazy[2 * node + 2] += delta;
            }
            return;
        }
        int mid = (start + end) / 2;
        update_range(2 * node + 1, start, mid, l, r, delta);
        update_range(2 * node + 2, mid + 1, end, l, r, delta);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
    
    int query_range(int node, int start, int end, int l, int r) {
        if (start > r || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        push_down(node, start, end);
        int mid = (start + end) / 2;
        int left_sum = query_range(2 * node + 1, start, mid, l, r);
        int right_sum = query_range(2 * node + 2, mid + 1, end, l, r);
        return left_sum + right_sum;
    }
public:
    SegmentTree(vector<int>& arr) {
        nums = arr;
        n = arr.size();
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
        build(0, 0, n - 1);
    }
    
    void update(int l, int r, int delta) {
        update_range(0, 0, n - 1, l, r, delta);
    }
    
    int query(int l, int r) {
        return query_range(0, 0, n - 1, l, r);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    SegmentTree seg_tree(arr);
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) { // 区间更新
            int l, r, delta;
            cin >> l >> r >> delta;
            seg_tree.update(l, r, delta);
        } else if (op == 2) { // 区间查询
            int l, r;
            cin >> l >> r;
            cout << seg_tree.query(l, r) << endl;
        }
    }
    return 0;
}

2.6 题目6：数论基础（欧拉函数）

题目描述：计算欧拉函数φ(n)，即小于等于n且与n互质的数的个数。

解题思路：欧拉函数的计算公式为φ(n) = n * (1-1/p1) * (1-1/p2) * … * (1-1/pk)，其中p1,p2,…,pk是n的所有质因数。

C++代码实现：

#include <iostream>
using namespace std;

int euler_phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    cout << euler_phi(n) << endl;
    return 0;
}

2.7 题目7：二维前缀和

题目描述：给定一个二维数组，多次查询子矩阵的和。

解题思路：使用二维前缀和来快速计算子矩阵的和。二维前缀和数组pre[i][j]表示从左上角(0,0)到(i,j)的子矩阵的和。

C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> matrix(n, vector<int>(m));
    vector<vector<long long>> pre(n + 1, vector<long long>(m + 1, 0));
    
    // 输入矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    
    // 计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }
    
    // 处理查询
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long sum = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
        cout << sum << endl;
    }
    return 0;
}

2.8 题目8：贪心算法应用（活动选择问题）

题目描述：给定n个活动，每个活动有一个开始时间和结束时间，问最多可以参加多少个活动（活动之间不能重叠）。

解题思路：使用贪心算法，按照活动的结束时间排序，每次选择结束时间最早的活动。

C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, end;
    bool operator<(const Activity& other) const {
        return end < other.end;
    }
};

int max_activities(vector<Activity>& activities) {
    int n = activities.size();
    if (n == 0) return 0;
    
    sort(activities.begin(), activities.end());
    int count = 1;
    int last_end = activities[0].end;
    
    for (int i = 1; i < n; i++) {
        if (activities[i].start >= last_end) {
            count++;
            last_end = activities[i].end;
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    vector<Activity> activities(n);
    for (int i = 0; i < n; i++) {
        cin >> activities[i].start >> activities[i].end;
    }
    cout << max_activities(activities) << endl;
    return 0;
}

第三章：难度系数7题目解析

难度系数7的题目是中级难度的难题，也是竞赛中的核心题目。以下是8道典型的难度系数7题目解析。

3.1 题目1：高级动态规划（最长公共子序列）

题目描述：给定两个字符串，求它们的最长公共子序列的长度。

解题思路：这是一个经典的动态规划问题。设dp[i][j]表示字符串s的前i个字符和字符串t的前j个字符的最长公共子序列的长度。状态转移方程为：如果s[i-1] == t[j-1]，则dp[i][j] = dp[i-1][j-1] + 1；否则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

C++代码实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longest_common_subsequence(string s, string t) {
    int n = s.size();
    int m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

int main() {
    string s, t;
    cin >> s >> t;
    cout << longest_common_subsequence(s, t) << endl;
    return 0;
}

3.2 题目2：最短路算法（Floyd-Warshall算法）

题目描述：给定一个带权有向图，使用Floyd-Warshall算法找出所有顶点对之间的最短路径。

解题思路：Floyd-Warshall算法是一种动态规划算法，用于求解任意两点间的最短路径。状态转移方程为：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])，其中dp[k][i][j]表示经过前k个顶点的i到j的最短路径长度。可以优化空间复杂度为O(n^2)。

C++代码实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX / 2; // 避免溢出

void floyd_warshall(int n, vector<vector<int>>& graph) {
    vector<vector<int>> dist = graph;
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << "INF" << " ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>(n, INF));
    
    // 初始化图
    for (int i = 0; i < n; i++) {
        graph[i][i] = 0;
    }
    
    // 输入边
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u][v] = weight;
    }
    
    floyd_warshall(n, graph);
    return 0;
}

3.3 题目3：最大流算法（Dinic算法）

题目描述：给定一个网络流图，求从源点到汇点的最大流。

解题思路：Dinic算法是一种高效的最大流算法，它通过分层图和阻塞流来快速计算最大流。

C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to, rev, capacity;
    Edge(int to, int rev, int capacity) : to(to), rev(rev), capacity(capacity) {}
};

class Dinic {
private:
    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> iter;
    
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const Edge& e : graph[u]) {
                if (e.capacity > 0 && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
    }
    
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int& i = iter[u]; i < graph[u].size(); i++) {
            Edge& e = graph[u][i];
            if (e.capacity > 0 && level[u] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.capacity));
                if (d > 0) {
                    e.capacity -= d;
                    graph[e.to][e.rev].capacity += d;
                    return d;
                }
            }
        }
        return 0;
    }
public:
    Dinic(int n) {
        graph.resize(n);
        level.resize(n);
        iter.resize(n);
    }
    
    void add_edge(int from, int to, int capacity) {
        graph[from].emplace_back(to, graph[to].size(), capacity);
        graph[to].emplace_back(from, graph[from].size() - 1, 0);
    }
    
    int max_flow(int s, int t) {
        int flow = 0;
        while (true) {
            bfs(s);
            if (level[t] == -1) return flow;
            fill(iter.begin(), iter.end(), 0);
            int f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }
    }
};

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    Dinic dinic(n);
    for (int i = 0; i < m; i++) {
        int from, to, capacity;
        cin >> from >> to >> capacity;
        dinic.add_edge(from, to, capacity);
    }
    cout << dinic.max_flow(s, t) << endl;
    return 0;
}

3.4 题目4：强连通分量（Tarjan算法）

题目描述：给定一个有向图，使用Tarjan算法找出所有强连通分量。

解题思路：Tarjan算法通过深度优先搜索来找出所有强连通分量。它维护两个数组：dfn表示节点的发现时间，low表示节点能够回溯到的最早的节点的发现时间。如果一个节点的dfn等于low，则它是一个强连通分量的根。

C++代码实现：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Tarjan {
private:
    vector<vector<int>> graph;
    vector<int> dfn, low;
    vector<bool> in_stack;
    stack<int> st;
    vector<vector<int>> sccs;
    int timestamp;
    
    void tarjan(int u) {
        dfn[u] = low[u] = ++timestamp;
        st.push(u);
        in_stack[u] = true;
        
        for (int v : graph[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        
        if (dfn[u] == low[u]) {
            vector<int> scc;
            while (true) {
                int v = st.top();
                st.pop();
                in_stack[v] = false;
                scc.push_back(v);
                if (v == u) break;
            }
            sccs.push_back(scc);
        }
    }
public:
    Tarjan(int n, vector<vector<int>>& g) {
        graph = g;
        dfn.resize(n, 0);
        low.resize(n, 0);
        in_stack.resize(n, false);
        timestamp = 0;
        
        for (int i = 0; i < n; i++) {
            if (!dfn[i]) {
                tarjan(i);
            }
        }
    }
    
    vector<vector<int>> get_sccs() {
        return sccs;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    
    Tarjan tarjan(n, graph);
    vector<vector<int>> sccs = tarjan.get_sccs();
    
    cout << "强连通分量的数量：" << sccs.size() << endl;
    for (int i = 0; i < sccs.size(); i++) {
        cout << "强连通分量 " << i + 1 << ":";
        for (int u : sccs[i]) {
            cout << " " << u;
        }
        cout << endl;
    }
    return 0;
}

3.5 题目5：计算几何基础（点与线段的关系）

题目描述：给定一个点P和一条线段AB，判断点P是否在线段AB上。

解题思路：要判断点P是否在线段AB上，需要满足两个条件：1）点P在直线AB上；2）点P在点A和点B之间。

C++代码实现：

#include <iostream>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

typedef Point Vector;

Vector operator+(Vector a, Vector b) {
    return Vector(a.x + b.x, a.y + b.y);
}

Vector operator-(Point a, Point b) {
    return Vector(a.x - b.x, a.y - b.y);
}

double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}

double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

bool on_segment(Point p, Point a, Point b) {
    return dcmp(cross(a - p, b - p)) == 0 && dcmp(dot(a - p, b - p)) <= 0;
}

int main() {
    Point p, a, b;
    cin >> p.x >> p.y >> a.x >> a.y >> b.x >> b.y;
    if (on_segment(p, a, b)) {
        cout << "Point is on segment" << endl;
    } else {
        cout << "Point is not on segment" << endl;
    }
    return 0;
}

3.6 题目6：矩阵快速幂

题目描述：给定一个n×n的矩阵A和一个正整数k，计算A的k次幂。

解题思路：使用快速幂的思想来计算矩阵的幂。矩阵快速幂可以用来优化某些递推式的计算，例如斐波那契数列。

C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<long long>> Matrix;

Matrix multiply(Matrix& a, Matrix& b, long long mod) {
    int n = a.size();
    Matrix res(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            if (a[i][k] == 0) continue;
            for (int j = 0; j < n; j++) {
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    return res;
}

Matrix matrix_pow(Matrix a, long long k, long long mod) {
    int n = a.size();
    Matrix res(n, vector<long long>(n, 0));
    // 初始化为单位矩阵
    for (int i = 0; i < n; i++) {
        res[i][i] = 1;
    }
    while (k > 0) {
        if (k % 2 == 1) {
            res = multiply(res, a, mod);
        }
        a = multiply(a, a, mod);
        k /= 2;
    }
    return res;
}

int main() {
    int n;
    long long k, mod;
    cin >> n >> k >> mod;
    Matrix a(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    Matrix res = matrix_pow(a, k, mod);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

3.7 题目7：数论（中国剩余定理）

题目描述：求解同余方程组。

解题思路：中国剩余定理（CRT）用于求解模数互质的同余方程组。如果模数不互质，可以使用扩展欧几里得算法来求解。

C++代码实现：

#include <iostream>
using namespace std;

typedef long long ll;

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll gcd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

ll crt(ll a[], ll m[], int n) {
    ll M = 1, ans = 0;
    for (int i = 0; i < n; i++) {
        M *= m[i];
    }
    for (int i = 0; i < n; i++) {
        ll Mi = M / m[i];
        ll x, y;
        ll gcd = exgcd(Mi, m[i], x, y);
        ans = (ans + a[i] * Mi * x) % M;
    }
    return (ans % M + M) % M;
}

int main() {
    int n;
    cin >> n;
    ll a[n], m[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> m[i];
    }
    cout << crt(a, m, n) << endl;
    return 0;
}

3.8 题目8：凸包算法（Graham扫描法）

题目描述：给定平面上的n个点，求这些点的凸包。

解题思路：Graham扫描法是一种常用的凸包算法。它的基本步骤是：1）找到最左下的点作为起始点；2）将其他点按照极角排序；3）依次扫描这些点，维护一个凸多边形。

C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

typedef Point Vector;

Vector operator-(Point a, Point b) {
    return Vector(a.x - b.x, a.y - b.y);
}

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}

double dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int compare_angle(Point p0, Point p1, Point p2) {
    Vector v1 = p1 - p0;
    Vector v2 = p2 - p0;
    int c = dcmp(cross(v1, v2));
    if (c > 0) return -1;
    else if (c < 0) return 1;
    else {
        return dcmp(dist(p0, p1) - dist(p0, p2));
    }
}

vector<Point> graham_scan(vector<Point>& points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // 找到最左下的点
    int min_index = 0;
    for (int i = 1; i < n; i++) {
        if (points[i] < points[min_index]) {
            min_index = i;
        }
    }
    swap(points[0], points[min_index]);
    
    // 按极角排序
    sort(points.begin() + 1, points.end(), [&](Point a, Point b) {
        return compare_angle(points[0], a, b) < 0;
    });
    
    // 维护凸包
    vector<Point> hull;
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    
    for (int i = 2; i < n; i++) {
        while (hull.size() >= 2) {
            Point p2 = hull.back();
            hull.pop_back();
            Point p1 = hull.back();
            if (dcmp(cross(p2 - p1, points[i] - p1)) > 0) {
                hull.push_back(p2);
                break;
            }
        }
        hull.push_back(points[i]);
    }
    return hull;
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }
    vector<Point> hull = graham_scan(points);
    cout << "凸包上的点：" << endl;
    for (Point p : hull) {
        cout << p.x << " " << p.y << endl;
    }
    return 0;
}

第四章：中级难度题目解题策略

通过对2025年IO竞赛中级难度题目的解析，我们可以总结出以下解题策略：

问题建模：将实际问题转化为算法模型是解决中级难度题目的关键。这需要对各种算法和数据结构有深入的理解。
算法选择：根据问题的特点选择合适的算法。例如，对于区间查询和更新问题，可以选择线段树或树状数组；对于图论问题，需要根据具体情况选择最短路算法、最小生成树算法等。
优化策略：在解决中级难度题目时，时间和空间复杂度的优化至关重要。可以通过剪枝、预处理、贪心选择等方法来优化算法。
代码实现：中级难度题目的代码量通常较大，需要良好的编程习惯和代码组织能力。可以使用模块化的方法来组织代码，提高代码的可读性和可维护性。
调试技巧：对于复杂的问题，调试是一个重要的环节。可以使用输出中间结果、断点调试等方法来定位问题。

解题策略: 问题分析 → 模型建立 → 算法选择 → 代码实现 → 测试优化

第五章：综合能力提升建议

对于想要在IO竞赛中取得好成绩的选手，以下是一些综合能力提升的建议：

系统学习：系统地学习各种算法和数据结构，建立完整的知识体系。
多做练习：通过大量的练习来巩固所学的知识，提高解题能力。可以从简单的题目开始，逐渐过渡到复杂的题目。
总结归纳：总结解题经验和技巧，归纳常见的问题类型和解决方法。
模拟比赛：定期参加模拟比赛，适应竞赛环境和节奏，提高在压力下的解题能力。
学习交流：与其他选手交流学习经验，分享解题思路，拓宽视野。
关注前沿：关注算法和数据结构的最新发展，学习新的解题方法和技巧。

能力提升路径: 基础巩固 → 专题突破 → 综合训练 → 模拟比赛 → 实战提升

结论

IO竞赛中级难度的题目是竞赛中的核心部分，也是选手们提升能力的关键阶段。通过系统地学习算法和数据结构，掌握各种解题技巧，选手们可以逐步提高解决复杂问题的能力，为在竞赛中取得好成绩奠定基础。希望本文的解析能够帮助读者在IO竞赛的道路上更进一步。

学习价值分布：

算法设计(30%) | 数据结构应用(25%) | 数学建模(20%) | 问题分析(15%) | 代码实现(10%)

互动讨论：

在解决中级难度题目的过程中，你遇到的最大挑战是什么？你是如何克服的？
对于不同类型的中级难度题目（如图论、动态规划、数论等），你有什么特别的解题技巧可以分享？
你认为在IO竞赛中，理论知识和实践经验哪个更重要？为什么？

参考资料

《算法竞赛进阶指南》- 李煜东
《算法导论》- Thomas H. Cormen等
《计算几何算法与应用》- Mark de Berg等
《数论概论》- Joseph H. Silverman
《具体数学》- Ronald L. Graham等
OI Wiki - https://oi-wiki.org/
Codeforces - https://codeforces.com/
2025年NOI竞赛大纲

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-22，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度