首页 › 题库 › C/C++编程考级 › C/C++编程七级

C/C++编程七级 题库

共 54 道题 ,第 3 / 3 页 · 按题型筛选,点「查看答案」核对解析
41 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

专属教室

题目描述

在一所学校中,有 N 个班级,每个班级都有一间专属的教室。第 i 个班级当前使用的教室编号为 Si,但学校计划将其调整到新的教室 Ti。

已知所有班级当前使用的教室编号互不相同,所有班级希望更换到的教室编号也互不相同。每个班级只能更换一次教室,且一次只能安排一个班级进行更换。在更换时,目标教室必须是空闲的。

学校希望找到一个合理的更换顺序,使得所有班级都能顺利迁入目标教室。请判断是否可能。

输入格式

第一行一个整数 N。

接下来 N 行,每行两个字符串 Si 和 Ti,表示第 i 个班级当前所在的教室编号和希望迁入的教室编号。

输出格式

如果存在一种顺序使得所有班级都能完成更换,输出 Yes,否则输出 No。

输入样例#1

2
b m
m d

输出样例#1

Yes

输入样例#2

3
a b
b c
c a

输出样例#2

No

说明提示

1≤N≤105

Si,Ti 为由小写英文字母组成的字符串,长度在 1 到 8 之间。

Si≠Ti

所有 Si 互不相同。

所有 Ti 互不相同。

限制

时间限制:1000ms

内存限制:256MiB


答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<string, vector<string>> adj;
map<string, int> state;

bool has_cycle(string v) {
  state[v] = 1;
  
  for (string next_v : adj[v]) {
    if (state[next_v] == 1) return true;
    if (state[next_v] == 0) {
      if (has_cycle(next_v)) return true;
    }
  }
  
  state[v] = 2;
  return false;
}

int main() {
  int N;
  cin >> N;
  
  vector<string> S(N), T(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i] >> T[i];
    adj[S[i]].push_back(T[i]);
  }
  
  for (auto const& [name, _] : adj) {
    if (state[name] == 0) {
      if (has_cycle(name)) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  
  cout << "Yes" << endl;
  return 0;
}
题目详情
42 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

简单路径

题目描述

给定一个简单无向图,包含 N 个顶点和 M 条边。顶点编号为 1 至 N。每个顶点的度数不超过 10。

定义一条简单路径为顶点序列 v1,v2,…,vk,满足 v1=1,相邻顶点有边相连,且所有顶点互不相同(长度为 0 的路径仅包含顶点 1 本身)。

设所有这样的简单路径的总数为 K。 如果 K>2200,则输出 X;否则输出 K。

输入格式

第一行,两个整数 N,M。

接下来 M 行,每行两个整数 ui,vi,表示一条边。

输出格式

输出一个整数或大写字母 X。

输入样例#1

4 2
1 2
2 3

输出样例#1

3

输入样例#2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例#2

16

输入样例#3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

输出样例#3

2023

说明提示

1≤N≤2×105

0≤M≤min(2×105, 2N(N−1))

1≤ui,vi≤N

图是简单图,每个顶点度数 ≤10

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;


const int LIMIT = 1 << 20;
const int MAXN = 200005;

vector<int> g[MAXN];
bool vis[MAXN];
int ans;

void dfs(int u)
{
    ans++;
    if (ans > LIMIT) return;
    for (int v : g[u])
    {
        if (!vis[v])
        {
            vis[v] = true;
            dfs(v);
            vis[v] = false;
            if (ans > LIMIT) return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(vis, 0, sizeof(vis));
    ans = 0;
    vis[1] = true;
    dfs(1);
    if (ans > LIMIT)
        cout << "X\n";
    else
        cout << ans << "\n";
    return 0;
}
题目详情
43 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

数字之和

题目描述

给定一个数字字符串 n,定义一次操作为:移除字符串中一个非空子串,并将剩余部分拼接形成新数字。

求所有可能操作方案生成的新数字之和,结果对 109+7取模。

输入格式

一行字符串 n

输出格式

一个整数,表示所有方案生成数字之和取模后的结果。


输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤105,| n |表示字符串长度。

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_LEN = 1e5 + 10;

long long pow10[MAX_LEN];
long long inv9, inv81;

long long mod_pow(long long base, long long exp, int mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

void precompute(int L) {
    pow10[0] = 1;
    for (int i = 1; i <= L; ++i) {
        pow10[i] = (pow10[i - 1] * 10) % MOD;
    }
    inv9 = mod_pow(9, MOD - 2, MOD);
    inv81 = mod_pow(81, MOD - 2, MOD);
}

int main() {
    string n;
    cin >> n;
    int L = n.size();
    precompute(L);
    
    long long ans = 0;
    for (int k = 0; k < L; ++k) {
        int d = n[k] - '0';
        if (d == 0) {
            continue; // 贡献为0,可直接跳过
        }
        
        // 计算左侧贡献
        long long left = 0;
        if (k > 0) {
            long long count = (1LL * k * (k + 1)) / 2 % MOD;
            int exponent = L - k - 1;
            long long pow_val = pow10[exponent];
            left = (count * pow_val) % MOD;
        }
        
        // 计算右侧贡献
        long long right = 0;
        int exponent = L - k - 1;
        if (exponent > 0) {
            long long part1 = (1LL * (L - k - 1) * pow10[exponent]) % MOD;
            long long term1 = (part1 * inv9) % MOD;
            
            long long part2 = (pow10[exponent] - 1 + MOD) % MOD;
            long long term2 = (part2 * inv81) % MOD;
            
            right = (term1 - term2 + MOD) % MOD;
        }
        
        long long total = (left + right) % MOD;
        ans = (ans + 1LL * d * total) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}
题目详情
44 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换!

最初,所有 N辆花车排成一行,花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中:

· 第 1 分钟:位置 a1 与 b1 的花车交换位置

· 第 2 分钟:位置 a2 与 b2 的花车交换位置

· ……

· 第 K 分钟:位置 aK 与 bK 的花车交换位置

· 第 K+1 分钟:重新从 (a1,b1) 开始交换(即位置 a1 与 b1 交换)

· 第 K+2 分钟:位置 a2 与 b2 交换

· 如此无限循环……

请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 N,K。

接下来 K 行每行包含 ai,bi(1≤ai<bi≤N)。

输出格式

输出 N行,第 i行为花车 i能到达的不同位置数量。

输入样例

5 4
1 3
1 2
2 3
2 4

输出样例

4
4
3
4
1

说明提示

样例解释

· 花车 1 可到达位置 {1,2,3,4}

· 花车 2 可到达位置 {1,2,3,4}

· 花车 3 可到达位置 {1,2,3}

· 花车 4 可到达位置 {1,2,3,4}

· 花车 5 始终在位置 5(未移动)

【数据范围】

1≤K≤2×105

2≤N≤105

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

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

    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> swaps(K);
    unordered_set<int> S;
    for (int i = 0; i < K; ++i) {
        int a, b;
        cin >> a >> b;
        swaps[i] = {a, b};
        S.insert(a);
        S.insert(b);
    }

    // 计算P = Q_K,即经过K步后的置换
    vector<int> Q(N + 1), R(N + 1); // 1-based
    for (int i = 1; i <= N; ++i) {
        Q[i] = i;
        R[i] = i;
    }
    for (auto [a, b] : swaps) {
        int x1 = R[a];
        int x2 = R[b];
        swap(R[a], R[b]);
        swap(Q[x1], Q[x2]);
    }
    vector<int> P = Q; // P是Q_K

    // 对P进行循环分解
    vector<bool> visited(N + 1, false);
    vector<vector<int>> cycles;
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            vector<int> cycle;
            int cur = i;
            while (!visited[cur]) {
                visited[cur] = true;
                cycle.push_back(cur);
                cur = P[cur];
            }
            cycles.push_back(cycle);
        }
    }

    // 为每个循环计算答案
    vector<int> ans(N + 1);
    for (auto& cycle : cycles) {
        // 检查循环是否与S有交集
        bool has_intersection = false;
        for (int x : cycle) {
            if (S.count(x)) {
                has_intersection = true;
                break;
            }
        }
        if (!has_intersection) {
            // 答案是循环大小
            int sz = cycle.size();
            for (int x : cycle) {
                ans[x] = sz;
            }
            continue;
        }

        // 模拟current_set的变化,计算Y的大小
        unordered_set<int> current_set(cycle.begin(), cycle.end());
        unordered_set<int> Y(current_set.begin(), current_set.end());

        for (int t = 0; t < K - 1; ++t) { // t处理0到K-2,对应步骤1到K-1
            auto [a, b] = swaps[t];
            bool has_a = current_set.count(a);
            bool has_b = current_set.count(b);

            if (has_a && has_b) {
                // 交换后集合不变
                continue;
            } else if (has_a) {
                current_set.erase(a);
                current_set.insert(b);
                Y.insert(b);
            } else if (has_b) {
                current_set.erase(b);
                current_set.insert(a);
                Y.insert(a);
            }
            // 否则集合不变
        }

        int res = Y.size();
        for (int x : cycle) {
            ans[x] = res;
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}
题目详情
45 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

公平

题目描述

有多干所精英学院和 N 名天才学员(编号 1 到 N)。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。

联盟定期进行学员调院操作(共 Q 次):第 j次操作将学员 Cj 调到学院 Dj。

联盟公平指数定义为:

对每所至少有一名学员的学院,取该学院最高能力值;再取这些最高能力值中的最小值。

请计算每次调院操作后的联盟公平指数。

输入格式

· 第一行:N Q

· 接下来 N 行:每行 Ai Bi,表示学员 ii 的能力值和初始学院

· 接下来 Q 行:每行 Cj Dj,表示将学员 Cj 调到学院 Dj

输出格式

· Q 行:每行一个整数,表示每次操作后的公平指数


输入样例#1

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

输出样例#1

6

2

6

输入样例#2

2 2

4208 1234

3056 5678

1 2020

2 2020

输出样例#2

3056

4208

说明提示

1≤N,Q≤2×105,1≤N,Q≤2×105

1≤Ai≤109,1≤Ai≤109

1≤Cj≤N,1≤Cj≤N

1≤Bi,Dj≤2×105,1≤Bi,Dj≤2×105

输入均为整数

每次转园操作会改变所属学院

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

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

    int N, Q;
    cin >> N >> Q;

    vector<int> ability(N + 1);
    vector<int> current_college(N + 1);
    unordered_map<int, multiset<int>> college_students;

    for (int i = 1; i <= N; ++i) {
        int A, B;
        cin >> A >> B;
        ability[i] = A;
        current_college[i] = B;
        college_students[B].insert(A);
    }

    multiset<int> global_max;
    for (const auto& pair : college_students) {
        const auto& s = pair.second;
        if (!s.empty()) {
            global_max.insert(*s.rbegin());
        }
    }

    while (Q--) {
        int Cj, Dj;
        cin >> Cj >> Dj;
        int c = Cj;
        int a = ability[c];
        int old_college = current_college[c];
        int new_college = Dj;

        // 处理旧学院
        auto& old_set = college_students[old_college];
        int x = *old_set.rbegin();
        auto it_old = old_set.find(a);
        old_set.erase(it_old);

        if (old_set.empty()) {
            auto it_global = global_max.find(x);
            if (it_global != global_max.end()) {
                global_max.erase(it_global);
            }
            college_students.erase(old_college);
        } else {
            int x_new = *old_set.rbegin();
            if (x_new != x) {
                auto it_global = global_max.find(x);
                if (it_global != global_max.end()) {
                    global_max.erase(it_global);
                }
                global_max.insert(x_new);
            }
        }

        // 处理新学院
        auto& new_set = college_students[new_college];
        bool was_empty = new_set.empty();
        int y = 0;
        if (!was_empty) {
            y = *new_set.rbegin();
        }
        new_set.insert(a);
        int y_new = *new_set.rbegin();

        if (was_empty) {
            global_max.insert(y_new);
        } else {
            if (y_new != y) {
                auto it_global = global_max.find(y);
                if (it_global != global_max.end()) {
                    global_max.erase(it_global);
                }
                global_max.insert(y_new);
            }
        }

        current_college[c] = new_college;
        cout << *global_max.begin() << '\n';
    }

    return 0;
}
题目详情
46 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

给定一棵包含 N个顶点的树。顶点编号为 1 至 N,第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。

对于树中任意两个顶点 u 和 v(满足 u<v),定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ,一个整数表示n

接下来的n−1行,每行两个整数ai,bi.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。


输入样例#1

3
1 2
2 3

输出样例#1

3

输入样例#2

5
1 2
1 3
1 4
1 5

输出样例#2

10

说明提示

【 数据范围 】

2≤N≤105

1≤ai,bi≤N

限制

时间限制:1000ms

内存限制:256MiB

答案与解析
参考答案

答案整理中……

题目详情
47 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

子序列

题目描述

给定两个整数序列,第一个序列长度为 n,第二个序列长度为 m。请问,这两个序列有多少种公共的子序列?输出数量模 998244353 的余数。

所谓子序列,是指从原序列中选择部分或全部元素组成新序列,这些元素在原序列中不必连续,但要保持在原序列中的顺序。只要下标不同,哪怕数字相同,也要算成不同的子序列。

输入格式

第一行:两个整数表示 n 与 m;

第二行: n 个数字 a1,a2,... ,an;

第三行:m 个数字 b1,b2,... ,bm;

输出格式

单个整数表示答案。

输入样例

4 3
3 4 6 2
3 3 2

输出样例

6

说明提示

1≤n,m≤2000

1≤ai,bj≤100,000

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 空子序列
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int j = 0; j <= m; ++j) dp[0][j] = 1;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
            } else {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
            }
            if (dp[i][j] < 0) dp[i][j] += MOD;
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}
题目详情
48 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

逻辑表达式

题目描述

给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^:

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值:0、1、?。

每个 ? 必须赋值成为 0 或 1 中的一种,请问有多少种不同的赋值方式,可以让整个逻辑表达式的值为 0?

由于答案可能很大,请输出方案数模1,000,000,007 的余数。

前缀表达式的定义如下:

0、1、? 都是前缀表达式;

如果 x,y 都是前缀表达式,则 &xy、|xy、^xy 都是前缀表达式;

不满足以上两条规则的表达式都不是前缀表达式。

输入格式

单个字符串表示输入的前缀表达式

输出格式

单个整数:表示答案模 1,000,000,007 的余数。


输入样例#1

&??

输出样例#1

3

输入样例#2

||??|||?^?|0|1&???|??

输出样例#2

4

输入样例#3

|?^?|0|&??||?^?|1??

输出样例#3

64

说明提示

设 ∣s∣表示输入字符串的长度

50%的数据,1≤∣s∣<1,000

100%的数据,1≤∣s∣<200,000

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
//C语言参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

typedef struct {
   long long zero;
   long long one;
} Node;

Node stack[200000];
int top = -1;

void push(Node node) {
   stack[++top] = node;
}

Node pop() {
   return stack[top--];
}

int main() {
   char s[200001];
   scanf("%s", s);
   int len = strlen(s);

   for (int i = len - 1; i >= 0; i--) {
       char c = s[i];
       if (c == '0') {
           push((Node){1, 0});
       } else if (c == '1') {
           push((Node){0, 1});
       } else if (c == '?') {
           push((Node){1, 1});
       } else {
           Node right = pop();
           Node left = pop();
           Node res = {0, 0};
           if (c == '&') {
               res.zero = (left.zero * right.zero % MOD + left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
               res.one = left.one * right.one % MOD;
           } else if (c == '|') {
               res.zero = left.zero * right.zero % MOD;
               res.one = (left.one * right.zero % MOD + left.zero * right.one % MOD + left.one * right.one % MOD) % MOD;
           } else if (c == '^') {
               res.zero = (left.zero * right.zero % MOD + left.one * right.one % MOD) % MOD;
               res.one = (left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;
           }
           push(res);
       }
   }

   Node result = pop();
   printf("%lld\n", result.zero);
   return 0;
}
//C++参考代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MOD = 1e9+7;

struct Node {
    long long zero, one;
    Node(long long z=0, long long o=0) : zero(z), one(o) {}
};

int main() {
    string s;
    cin >> s;
    stack<Node> st;
    
    for (int i = s.size()-1; i >= 0; --i) {
        char c = s[i];
        if (c == '0') {
            st.push(Node(1, 0));
        } else if (c == '1') {
            st.push(Node(0, 1));
        } else if (c == '?') {
            st.push(Node(1, 1));
        } else {
            Node right = st.top(); st.pop();
            Node left = st.top(); st.pop();
            Node res;
            
            if (c == '&') {
                res.zero = (right.zero * left.zero % MOD + 
                           right.zero * left.one % MOD + 
                           right.one * left.zero % MOD) % MOD;
                res.one = right.one * left.one % MOD;
            } else if (c == '|') {
                res.zero = right.zero * left.zero % MOD;
                res.one = (right.one * left.one % MOD + 
                          right.one * left.zero % MOD + 
                          right.zero * left.one % MOD) % MOD;
            } else if (c == '^') {
                res.zero = (right.zero * left.zero % MOD + 
                           right.one * left.one % MOD) % MOD;
                res.one = (right.zero * left.one % MOD + 
                          right.one * left.zero % MOD) % MOD;
            }
            st.push(res);
        }
    }
    
    cout << st.top().zero % MOD << endl;
    return 0;
}


题目详情
49 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

联盟

题目描述

在国际会议上,共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况,请计算存在多少种合法的联盟分配方案。

输入格式

第一行:单个整数 n 表示国家数量

第二行到第 n 行:在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n,其中

ci,j=0-表示 i 号国家与 j 号国家不接壤

ci,j=1 表示 i 号国家与 j 号国家接壤

输出格式

单个整数:表示合法的联盟分配方案总数。


输入样例#1

3
1 1
1

输出样例#1

6

输入样例#2

4
1 1 1
1 1
1

输出样例#2

0

说明提示

数据范围

对于 50% 的数据,1≤n≤12

对于 100% 的数据,1≤n≤20

样例1说明

三国两两接壤,形成三角形。三个联盟的排列方案为 3!=6种。

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> color;
int count = 0;

bool isValid(int country, int c) {
    for (int i = 0; i < country; ++i) {
        if (adj[i][country] && color[i] == c) {
            return false;
        }
    }
    return true;
}

void dfs(int country) {
    if (country == n) {
        count++;
        return;
    }
    
    for (int c = 1; c <= 3; ++c) {
        if (isValid(country, c)) {
            color[country] = c;
            dfs(country + 1);
            color[country] = 0;
        }
    }
}

int main() {
    cin >> n;
    adj.resize(n, vector<int>(n, 0));
    color.resize(n, 0);
    
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            cin >> adj[i][j];
            adj[j][i] = adj[i][j];
        }
    }
    
    dfs(0);
    cout << count << endl;
    return 0;
}
题目详情
50 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 4 图论基础

工作规划

题目描述

n 台机器人正在完成任务。其中,第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束,其中约束关系共有m条,每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。

请问,所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的,所有机器人一定在有限时间内完成工作。

输入格式

第一行:两个整数 n 和 m

第二行到第 n+1 行:每个机器人需要的时间 ti

接下来 m 行:每行有两个整数 a 和 b,表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。

输出格式

单个整数,表示所有机器人任务完成最少需要花多少时间。


输入样例

10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3

输出样例

161

说明提示

1≤n≤104

1≤m≤50,000

1≤ti≤105

1≤ai,bi≤n

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 10005
#define MAX_M 50005
#define INF 0x3f3f3f3f

typedef struct Node {
   int to;
   struct Node* next;
} Node;

Node* adj[MAX_N];  // 邻接表
int in_degree[MAX_N];  // 入度数组
int t[MAX_N];  // 每个机器人的工作时间
int earliest_start[MAX_N];  // 每个机器人的最早开始时间
int n, m;

// 添加边
void add_edge(int u, int v) {
   Node* new_node = (Node*)malloc(sizeof(Node));
   new_node->to = v;
   new_node->next = adj[u];
   adj[u] = new_node;
   in_degree[v]++;
}

// 拓扑排序计算最早完成时间
int topological_sort() {
   int queue[MAX_N];
   int front = 0, rear = 0;

   // 初始化队列,将入度为0的节点加入队列
   for (int i = 1; i <= n; i++) {
       if (in_degree[i] == 0) {
           queue[rear++] = i;
           earliest_start[i] = 0;  // 入度为0的节点最早开始时间为0
       }
   }

   // 处理队列中的节点
   while (front < rear) {
       int u = queue[front++];

       // 遍历所有后继节点
       Node* current = adj[u];
       while (current != NULL) {
           int v = current->to;
           // 更新后继节点的最早开始时间
           if (earliest_start[v] < earliest_start[u] + t[u]) {
               earliest_start[v] = earliest_start[u] + t[u];
           }
           // 减少后继节点的入度
           in_degree[v]--;
           if (in_degree[v] == 0) {
               queue[rear++] = v;
           }
           current = current->next;
       }
   }

   // 计算最大最早完成时间
   int max_time = 0;
   for (int i = 1; i <= n; i++) {
       int finish_time = earliest_start[i] + t[i];
       if (finish_time > max_time) {
           max_time = finish_time;
       }
   }

   return max_time;
}

int main() {
   // 初始化
   memset(adj, 0, sizeof(adj));
   memset(in_degree, 0, sizeof(in_degree));
   memset(earliest_start, 0, sizeof(earliest_start));

   // 读取输入
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= n; i++) {
       scanf("%d", &t[i]);
   }
   for (int i = 0; i < m; i++) {
       int a, b;
       scanf("%d %d", &a, &b);
       add_edge(a, b);
   }

   // 计算并输出结果
   int result = topological_sort();
   printf("%d\n", result);

   // 释放内存
   for (int i = 1; i <= n; i++) {
       Node* current = adj[i];
       while (current != NULL) {
           Node* temp = current;
           current = current->next;
           free(temp);
       }
   }

   return 0;
}
题目详情
51 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

树的同构

给定两棵树  T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

图一

图二

现给定两棵树,请你判断它们是否是同构的。

时间限制:1000

内存限制:65536

输入

输入给出2棵二叉树的信息。对于每棵树,首先在一行中给出一个非负整数 n(≤ 10),即该树的结点数(此时假设结点从 0 到 n -1 编号);随后 n 行,第 i 行对应编号第 i 个结点,给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出

如果两棵树是同构的,输出“Yes”,否则输出“No”。


样例输入

样例#1(对应图1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

样例#2(对应图2):

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

样例输出

样例#1:

Yes

样例#2:

No
答案与解析
参考答案

答案整理中……

题目详情
52 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

网红点打卡攻略

一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

时间限制:1000

内存限制:65536

输入

首先第一行给出两个正整数:网红点的个数 N(1 < N ≤ 200)和网红点之间通路的条数 M。随后 M 行,每行给出有通路的两个网红点、以及这条路上的旅行花费(为正整数),格式为“网红点1 网红点2 费用”,其中网红点从 1 到 N 编号;同时也给出你家到某些网红点的花费,格式相同,其中你家的编号固定为 0。 再下一行给出一个正整数 K,是待检验的攻略的数量。随后 K 行,每行给出一条待检攻略,格式为: n V1 V2 … Vn 其中 n (≤ 200) 是攻略中的网红点数,Vi 是路径上的网红点编号。这里假设你从家里出发,从 V1 开始打卡,最后从 Vn 回家。

输出

在第一行输出满足要求的攻略的个数。 在第二行中,首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号(从 1 开始),然后输出这个攻略的总路费,其间以一个空格分隔。如果这样的攻略不唯一,则输出序号最小的那个。 题目保证至少存在一个有效攻略,并且总路费不超过 109。


样例输入

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

样例输出

3
5 11

提示

样例说明: 第 2、3、4、6 条都不满足攻略的基本要求,即不能做到从家里出发,在每个网红点打卡仅一次,且能回到家里。所以满足条件的攻略有 3 条。 第 1 条攻略的总路费是:(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14; 第 5 条攻略的总路费同理可算得:1 + 1 + 1 + 2 + 3 + 1 + 2 = 11,是一条更省钱的攻略; 第 7 条攻略的总路费同理可算得:2 + 1 + 1 + 2 + 2 + 2 + 1 = 11,与第 5 条花费相同,但序号较大,所以不输出。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> matrix(201, vector<int>(201, -1));
	for (int i = 0; i < M; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		matrix[u][v] = c;
		matrix[v][u] = c;
	}
	int K;
	cin >> K;
	vector<pair<int, int>> valid_plans;
	for (int plan_idx = 1; plan_idx <= K; ++plan_idx) {
		int n;
		cin >> n;
		vector<int> Vi(n);
		for (int i = 0; i < n; ++i) {
			cin >> Vi[i];
		}
		if (n != N) {
			continue;
		}
		vector<bool> visited(N + 1, false);
		bool valid_vi = true;
		for (int v : Vi) {
			if (v < 1 || v > N || visited[v]) {
				valid_vi = false;
				break;
			}
			visited[v] = true;
		}
		for (int i = 1; i <= N && valid_vi; ++i) {
			if (!visited[i]) {
				valid_vi = false;
				break;
			}
		}
		if (!valid_vi) {
			continue;
		}
		int cost = 0;
		int current = 0;
		bool path_valid = true;
		if (matrix[current][Vi[0]] == -1) {
			path_valid = false;
		} else {
			cost += matrix[current][Vi[0]];
			current = Vi[0];
		}
		for (int i = 1; i < n && path_valid; ++i) {
			int next = Vi[i];
			if (matrix[current][next] == -1) {
				path_valid = false;
			} else {
				cost += matrix[current][next];
				current = next;
			}
		}
		if (path_valid) {
			if (matrix[current][0] == -1) {
				path_valid = false;
			} else {
				cost += matrix[current][0];
			}
		}
		if (path_valid) {
			valid_plans.emplace_back(plan_idx, cost);
		}
	}
	cout << valid_plans.size() << endl;
	if (!valid_plans.empty()) {
		auto min_plan = valid_plans[0];
		for (const auto &p : valid_plans) {
			if (p.second < min_plan.second || (p.second == min_plan.second && p.first < min_plan.first)) {
				min_plan = p;
			}
		}
		cout << min_plan.first << " " << min_plan.second << endl;
	}
	return 0;
}


题目详情
53 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

树的偏斜度

对于一棵二叉树,令 nL 表示仅有左孩子的结点的个数,令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。

时间限制:1000

内存限制:65536

输入

输入在第一行给出正整数 n (≤ 103),为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列,键值为 1 到 n 的整数。同行数字间以空格分隔。

输出

在一行中按以下格式输出树的偏斜度: Ds = nL - nR


样例输入

7
1 2 7 5 4 3 6
1 2 3 4 7 5 6

样例输出

2 = 3 - 1
答案与解析
参考答案
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
 
pair<int, int> calcSkew(vector<int>& post, vector<int>& in, int ps, int pe, int is, int ie) {
    if (ps > pe) return {0, 0};
    int root = post[pe], idx = is;
    while (in[idx] != root) idx++;
    pair<int, int> left = calcSkew(post, in, ps, ps + idx - is - 1, is, idx - 1);
    pair<int, int> right = calcSkew(post, in, ps + idx - is, pe - 1, idx + 1, ie);
    return {left.first  + right.first  + (idx > is && idx == ie), left.second  + right.second  + (idx < ie && idx == is)};
}
 
int main() {
    int n;
    cin >> n;
    vector<int> post(n), in(n);
    for (int &x : post) cin >> x;
    for (int &x : in) cin >> x;
    pair<int, int> res = calcSkew(post, in, 0, n - 1, 0, n - 1);
    cout << res.first  - res.second  << " = " << res.first  << " - " << res.second  << endl;
}
//参考代码2
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {
	if (inStart > inEnd || postStart > postEnd) return nullptr;
	int rootVal = postorder[postEnd];
	TreeNode* root = new TreeNode(rootVal);
	int rootIndex = inMap[rootVal];
	int leftSize = rootIndex - inStart;
	root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1, inMap);
	root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1, inMap);
	return root;
}

void countSkew(TreeNode* node, int& nL, int& nR) {
	if (!node) return;
	bool hasLeft = node->left != nullptr;
	bool hasRight = node->right != nullptr;
	if (hasLeft && !hasRight) nL++;
	else if (!hasLeft && hasRight) nR++;
	countSkew(node->left, nL, nR);
	countSkew(node->right, nL, nR);
}

int main() {
	int n;
	cin >> n;
	vector<int> post(n), in(n);
	for (int i = 0; i < n; i++) cin >> post[i];
	for (int i = 0; i < n; i++) cin >> in[i];
	
	unordered_map<int, int> inMap;
	for (int i = 0; i < n; i++) inMap[in[i]] = i;
	
	TreeNode* root = buildTree(in, post, 0, n-1, 0, n-1, inMap);
	
	int nL = 0, nR = 0;
	countSkew(root, nL, nR);
	
	cout << nL - nR << " = " << nL << " - " << nR << endl;
	return 0;
}


题目详情
54 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 1 树与二叉树

是不是堆

二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。

时间限制:1000

内存限制:65536

输入

输入在一行中给出两个正整数:m(≤ 100)是将要测试的完全二叉树的数量;n(1 < n ≤ 1000)是完全二叉树中的结点数。 随后 m 行,每行给出 n 个互不相同的键值(均在整型范围内),为完全二叉树的层序遍历序列。

输出

对输入的每棵完全二叉树,如果它是最大堆(大顶堆),就在一行中输出 `Max Heap`;如果是最小堆(小顶堆),则输出 `Min Heap`;如果根本不是堆,则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

样例输出

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10
答案与解析
参考答案
//参考代码1
#include <iostream>
#include <vector>
using namespace std;
 
string checkHeap(const vector<int>& tree) {
    int n = tree.size(); 
    for (int i = 0; i < n; ++i) {
        int l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && tree[i] > tree[l]) return "Min Heap";
        if (r < n && tree[i] > tree[r]) return "Min Heap";
        if (l < n && tree[i] < tree[l]) return "Max Heap";
        if (r < n && tree[i] < tree[r]) return "Max Heap";
    }
    return "Not Heap";
}
 
void printPostOrder(const vector<int>& tree, int i, vector<int>& res) {
    if (i >= tree.size())  return;
    printPostOrder(tree, 2 * i + 1, res);
    printPostOrder(tree, 2 * i + 2, res);
    res.push_back(tree[i]); 
}
 
int main() {
    int m, n;
    cin >> m >> n;
    while (m--) {
        vector<int> tree(n);
        for (int &x : tree) cin >> x;
        cout << checkHeap(tree) << endl;
        vector<int> res;
        printPostOrder(tree, 0, res);
        for (int i = 0; i < res.size();  ++i) cout << res[i] << (i == res.size()  - 1 ? '\n' : ' ');
    }
}


//参考代码2
#include <iostream>
#include <vector>
using namespace std;

void postOrder(int index, const vector<int>& arr, vector<int>& res) {
	if (index >= arr.size()) return;
	postOrder(2 * index + 1, arr, res);
	postOrder(2 * index + 2, arr, res);
	res.push_back(arr[index]);
}

int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<int>> testCases(m, vector<int>(n));
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> testCases[i][j];
		}
	}
	
	for (const auto& arr : testCases) {
		bool is_max = true, is_min = true;
		int size = arr.size();
		for (int i = 0; i < size; ++i) {
			int left = 2 * i + 1;
			int right = 2 * i + 2;
			if (left < size) {
				if (arr[i] < arr[left]) is_max = false;
				if (arr[i] > arr[left]) is_min = false;
			}
			if (right < size) {
				if (arr[i] < arr[right]) is_max = false;
				if (arr[i] > arr[right]) is_min = false;
			}
			if (!is_max && !is_min) break;
		}
		
		if (is_max) cout << "Max Heap\n";
		else if (is_min) cout << "Min Heap\n";
		else cout << "Not Heap\n";
		
		vector<int> post;
		postOrder(0, arr, post);
		for (int i = 0; i < post.size(); ++i) {
			if (i) cout << ' ';
			cout << post[i];
		}
		cout << endl;
	}
	return 0;
}

题目详情