C/C++编程七级 题库
专属教室
题目描述
在一所学校中,有 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;
}简单路径
题目描述
给定一个简单无向图,包含 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;
}数字之和
题目描述
给定一个数字字符串 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;
}花车巡游
题目描述
嘉年华的花车巡游正在展示精心编排的队列变换!
最初,所有 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;
}公平
题目描述
有多干所精英学院和 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;
}给定一棵包含 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
答案整理中……
子序列
题目描述
给定两个整数序列,第一个序列长度为 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;
}逻辑表达式
题目描述
给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^:
& 表示逻辑与运算
| 表示逻辑或运算
^ 表示逻辑异或运算
表达式还包含三种基本逻辑值: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;
}联盟
题目描述
在国际会议上,共有 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;
}工作规划
题目描述
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;
}树的同构
给定两棵树 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
答案整理中……
网红点打卡攻略
一个旅游景点,如果被带火了的话,就被称为“网红点”。大家来网红点游玩,俗称“打卡”。在各个网红点打卡的快(省)乐(钱)方法称为“攻略”。你的任务就是从一大堆攻略中,找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。
时间限制: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;
}树的偏斜度
对于一棵二叉树,令 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;
}是不是堆
二叉堆可以用一棵完全二叉树来实现,但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。
时间限制: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;
}