ZZJC新生训练赛第五场题解
A题
思路
题目要求构造一个相邻两项互质的长度为 n 的序列。可以直接选择输出从 1 到 n 的自然数序列，因为相邻的自然数总是互质的。题目有多个测试用例，因此需要逐个处理输入，并输出对应结果。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cout << i << " ";
}
cout << '\n';
}
}
B题
思路
该题是一道模拟题，要求打印一个特定的图案。图案分为三部分：上半部分、中间部分、下半部分。每一部分的格式不同，但逻辑相对简单，可以通过逐层构造来完成。上半部分和下半部分是对称的，中间部分则是连续的星号和点的分布。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int cd = n * 4;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) cout << ".";
for (int j = 0; j < cd - 2 * (n - i); j++) cout << "*";
for (int j = 0; j < n - i; j++) cout << ".";
cout << endl;
}
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < n; j++) cout << "*";
for (int j = 0; j < cd - 2 * n; j++) cout << ".";
for (int j = 0; j < n; j++) cout << "*";
cout << endl;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n - i; j++) cout << ".";
for (int j = 0; j < cd - 2 * (n - i); j++) cout << "*";
for (int j = 0; j < n - i; j++) cout << ".";
cout << endl;
}
}
C题
思路
这道题涉及树的删除边问题。当节点数为奇数时，无论如何删除边，都会有一个连通块的大小是奇数，因此无法满足题意，需要输出 -1。当节点数为偶数时，可以通过深度优先搜索（DFS）遍历树，从叶子节点向上遍历。当一个连通块的节点数为偶数时，删除该边并增加答案计数。最后，输出删除边的最小次数。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int ans = 0;
auto dfs = [&](auto&& self, int u, int fa) -> int {
int cnt = 1;
for (auto v : g[u]) {
if (v != fa) {
int op = self(self, v, u);
cnt += op;
}
}
ans += !(cnt & 1);
return cnt;
};
dfs(dfs, 1, -1);
if (n & 1) {
cout << -1 << '\n';
} else {
cout << ans - 1 << "\n";
}
}
D题
思路
我们需要在多个生物群系中选择一个作为庇护所，并计算所有生物群系的危险度之和。危险度的定义是：对于第 \(i\) 个生物群系，危险度为：
\begin{aligned}
f(i) = (x - i)^2 \times a_i
\end{aligned}
\(x\) 是选择作为庇护所的生物群系编号，\(a_i\) 是该生物群系的危险系数。
题目要求找出某个编号 \(x\) 使得所有生物群系的危险度之和最小。
设危险度之和的公式为：
展开每一项：
其中：
- \(A = \sum_{i=1}^{n} i^2 a_i\)
- \(B = \sum_{i=1}^{n} i a_i\)
- \(C = \sum_{i=1}^{n} a_i\)
显然，\(S(x)\) 是关于 \(x\) 的二次函数。为了使 \(S(x)\) 最小，我们可以通过求导找到二次函数的顶点（直接用结论 \(-\frac{b}{2a}\) 也行）。
对 \(S(x)\) 关于 \(x\) 求导：
\(\frac{dS}{dx} = 2C x - 2B\)
令导数为零，求得最小值对应的 $ x $：
\(2C x - 2B = 0 \implies x = \frac{B}{C}\)
由于 \(x\) 必须是整数（生物群系的编号），我们只需要考虑邻近的整数值：
- \(x_1 = \left\lfloor \frac{B}{C} \right\rfloor\)
- \(x_2 = \left\lceil \frac{B}{C} \right\rceil\)
然后计算 \(S(x_1)\) 和 \(S(x_2)\)，取其中 \(S(x)\) 最小的 \(x\) 作为答案，注意用求导的做法需要特判 \(C\) 是 \(0\) 的情况。
代码
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
i64 n;
std::cin >> n;
std::vector<i64> a(n + 1);
i64 A = 0, B = 0, C = 0;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
A += a[i] * i * i;
B += a[i] * i;
C += a[i];
}
if (C == 0) {
std::cout << 0;
return 0;
}
i64 x1 = std::min(n, std::max(1LL, B / C));
i64 x2 = std::min(n, std::max(1LL, (B + C - 1) / C));
i64 s1 = A - 2 * B * x1 + C * x1 * x1;
i64 s2 = A - 2 * B * x2 + C * x2 * x2;
std::cout << std::min(s1, s2);
// 因为代码的时间复杂度已经是O(n)，所以遍历所有的x也是可以接受的
// i64 ans = 4e18; // 初始设置一个极大值，保证能被后续结果更新
// for (int i = 1; i <= n; i++) {
// // 计算每个 x=i 时的S(x)并更新最小值
// ans = std::min(ans, A - 2 * B * i + C * i * i);
// }
// std::cout << ans;
}
E题
思路
题目要求将小时部分从24小时制转换为12小时制，而分钟部分保持不变。如果小时数小于12，则输出 AM，否则输出 PM。当小时为 0 时，应转换为 12 AM。当小时大于 12 时，应减去 12 以转换为12小时制。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
for (cin >> tt; tt--;) {
int a, b;
cin >> a >> b;
bool flag = true;
if (a < 12) flag = false;
if (a == 0) a = 12;
if (a > 12) a = a - 12;
cout << a << " " << b << " ";
if (!flag) cout << "am\n";
else cout << "pm\n";
}
}
F题
思路
题目要求根据给定的条件判断能否满足某种关系。需要分类讨论：
- 如果
x > y，输出 "No"。 - 如果
n - m + x >= y，则输出 "Yes"，否则输出 "No"。
代码
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, m, x, y;
cin >> n >> m >> x >> y;
if (x > y) {
cout << "No" << endl;
continue;
}
if (n - m + x >= y)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
G题
思路
这是前缀和模板题。我们通过构建一个前缀和数组 ss[i]，使得 ss[i] 表示数组前 i 个元素的和。然后对于每个询问 (l, r)，可以在常数时间内得到区间 [l, r] 的和，公式为 ss[r] - ss[l - 1]。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
#define int long long
int n, q;
cin >> n >> q;
vector<int> ar(n + 1), ss(n + 1);
for (int i = 0; i < n; i++) {
cin >> ar[i];
ss[i + 1] = ar[i] + ss[i];
}
while (q--) {
int l, r;
cin >> l >> r;
cout << ss[r] - ss[l - 1] << '\n';
}
}
H题
思路
题目需要提取有效的输入字符并根据不同符号的情况判断输出结果。具体步骤是：
- 读取输入字符，提取
&,>等符号及0或1的二进制字符。 - 如果出现
&符号，进行逻辑与运算判断。 - 如果出现
>符号，进行逻辑或运算判断。 - 否则，执行非运算。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
bool flag1 = false, flag2 = false;
char xp;
vector<char> ar;
while (cin >> xp) {
if (xp == '&') flag1 = true;
else if (xp == '>') flag2 = true;
else if (xp >= '0' && xp <= '1') {
ar.push_back(xp);
}
}
if (flag1) {
if (ar[0] == '1' && ar[1] == '1') cout << 1 << '\n';
else cout << 0 << '\n';
}
else if (flag2) {
if (ar[0] == '1' || ar[2] == '1') cout << 1 << '\n';
else cout << 0 << '\n';
}
else {
if (ar[0] == '1') cout << 0 << '\n';
else cout << 1 << '\n';
}
}