C/C++编程四级 题库
兔子不吃窝边草
有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?
时间限制:10000
内存限制:65536
输入
输入第一行给出两个正整数,即 N (≤ 105) 为草皮的块数、 i (1 ≤ i ≤ N) 为兔子开始吃的第一块草皮的编号。第二行给出 N 个正整数 (≤ 103),以空格分隔,依次表示每块草皮的含草量。
输出
首先在一行中输出这只兔子最多可以吃掉的草量。下一行按兔子吃草的顺序输出每块被吃掉的草皮的编号。同行数字以 1 个空格分隔,行首尾不得有多余空格。 注意:我们必须假设兔子只朝一个方向跳着吃草,否则如果它可以来回跳,就能吃掉所有的草了。如果朝左右两个方向得到的结果一样,则兔子总是喜欢向左边跳;并且如果有多块草皮都可以得到同样的结果,兔子总是选择跳到离自己最近的那块。
样例输入
样例1:
10 4 2 1 4 3 1 1 5 2 3 1
样例2:
10 8 2 1 4 3 1 1 5 2 3 1
样例输出
样例1:
11 4 7 9
样例2:
9 8 6 3 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, vector<int>> solve_dp(const vector<int>& vals) {
int n = vals.size();
if (n == 0) return {0, {}};
vector<int> dp(n, 0);
dp[0] = vals[0];
if (n >= 1) {
dp[1] = max(vals[0], vals[1]);
}
for (int j = 2; j < n; ++j) {
dp[j] = max(dp[j - 1], dp[j - 2] + vals[j]);
}
vector<int> selected;
int j = n - 1;
while (j >= 0) {
if (j == 0) {
selected.push_back(j);
break;
}
if (dp[j] == dp[j - 1]) {
--j;
} else {
selected.push_back(j);
j -= 2;
}
}
reverse(selected.begin(), selected.end());
return {dp.back(), selected};
}
int main() {
int N, i;
cin >> N >> i;
vector<int> arr(N);
for (int j = 0; j < N; ++j) {
cin >> arr[j];
}
vector<int> left_pos, left_vals;
for (int pos = i - 2; pos >= 1; --pos) {
left_pos.push_back(pos);
left_vals.push_back(arr[pos - 1]);
}
auto [left_sum, left_idx] = solve_dp(left_vals);
int total_left = arr[i - 1] + left_sum;
vector<int> left_path;
for (int idx : left_idx) {
left_path.push_back(left_pos[idx]);
}
vector<int> right_pos, right_vals;
for (int pos = i + 2; pos <= N; ++pos) {
right_pos.push_back(pos);
right_vals.push_back(arr[pos - 1]);
}
auto [right_sum, right_idx] = solve_dp(right_vals);
int total_right = arr[i - 1] + right_sum;
vector<int> right_path;
for (int idx : right_idx) {
right_path.push_back(right_pos[idx]);
}
bool choose_left = false;
if (total_left > total_right) {
choose_left = true;
} else if (total_left == total_right) {
choose_left = true;
} else {
choose_left = false;
}
vector<int> path;
path.push_back(i);
if (choose_left) {
for (int pos : left_path) {
path.push_back(pos);
}
} else {
for (int pos : right_path) {
path.push_back(pos);
}
}
cout << (choose_left ? total_left : total_right) << endl;
for (size_t k = 0; k < path.size(); ++k) {
if (k > 0) cout << " ";
cout << path[k];
}
cout << endl;
return 0;
}漂亮的序列
对于给定的整数 m,我们称一个序列是“漂亮”的,如果它包含至少 2 个整数,并且有 2 个相邻数字的差不超过m。你的任务是计算一个给定的 n 个正整数的序列中,有多少个子序列是漂亮的。
时间限制:6000
内存限制:65536
输入
输入第一行给出 2 个正整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 103),随后一行给出序列中 n 个不超过 105 的正整数。同行数字间以空格分隔。
输出
输出原始序列中漂亮子序列的个数。因为答案可能非常大,所以你需要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
4 2 5 3 8 6
样例输出
8
提示
样例解释:
1、子序列下标为 {1, 2}, 对应值为 {5, 3};
2、子序列下标为 {1, 4}, 对应值为 {5, 6};
3、子序列下标为 {3, 4}, 对应值为 {8, 6};
4、子序列下标为 {1, 2, 3}, 对应值为 {5, 3, 8};
5、子序列下标为 {1, 2, 4}, 对应值为 {5, 3, 6};
6、子序列下标为 {1, 3, 4}, 对应值为 {5, 8, 6};
7、子序列下标为 {2, 3, 4}, 对应值为 {3, 8, 6};
8、子序列下标为 {1, 2, 3, 4}, 对应值为 {5, 3, 8, 6}。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
class FenwickTree {
private:
vector<int> tree;
int n;
public:
FenwickTree(int size) : n(size) {
tree.assign(n + 2, 0); // 索引从1到n+1
}
void update(int idx, int val) {
idx++; // 树状数组从1开始
if (idx > n) return; // 超出范围的不处理
while (idx <= n) {
tree[idx] = (tree[idx] + val) % MOD;
idx += idx & -idx;
}
}
int query(int idx) {
idx++; // 转换为树状数组的索引
if (idx < 0) return 0;
int res = 0;
while (idx > 0) {
res = (res + tree[idx]) % MOD;
idx -= idx & -idx;
}
return res;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int max_a = *max_element(a.begin(), a.end());
int max_val = max_a + m;
FenwickTree bit(max_val);
long long sum_dp = 0;
int total_sum = 0;
for (int ai : a) {
int left = ai - m - 1;
int sum_left = bit.query(left);
int right = ai + m;
int sum_right = (total_sum - bit.query(right) + MOD) % MOD;
int dp_i = (sum_left + sum_right + 1) % MOD;
sum_dp = (sum_dp + dp_i) % MOD;
bit.update(ai, dp_i);
total_sum = (total_sum + dp_i) % MOD;
}
long long S = (sum_dp - n + MOD) % MOD;
// 计算2^n mod MOD
auto powmod = [](long long a, int b, int mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
};
long long T = (powmod(2, n, MOD) - 1 - n + MOD) % MOD;
long long ans = (T - S + MOD) % MOD;
cout << ans << '\n';
return 0;
}园林修整
园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。
时间限制:10000
内存限制:65536
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000),随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内,同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号(从 1 开始)。如果解不唯一,输出那个需要最少替换树木的解,题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔,行首尾不得有多余空格。 如果没有树需要调整,则根据树高的升降性质,在一行中输出 Non-ascending(表示“非递增”)或 Non-descending(表示非递减)。
样例输入
样例1:
10 2 3 8 2 4 5 10 1 7 11
样例2:
3 1 2 3
样例输出
样例1:
4 2 3 7 8
样例2:
Non-descending
提示
样例1解释:
首先,要将树木修整成按高度非递减的样式,我们需要调整 4 棵树;而要修整成非递增样式,则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次,存在 4 种不同的递增序列解:
1、保持树高为 2、3、4、5、10、11 的树不变,我们需要替换掉高度为 2、1、7 的 3 棵树,因为它们太矮了;
2、保持树高为 2、3、4、5、7、11 的树不变,我们需要替换掉高度为 2、1 的 2 棵树;
3、保持树高为 2、2、4、5、10、11 的树不变,我们需要替换掉高度为 1、7 的 2 棵树;
4、保持树高为 2、2、4、5、7、11 的树不变,我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解,即裁剪编号为 2、3、7(对应高度为 3、8、10)的树,替换掉第 8 棵高度为 1 的树。
参考代码:
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
struct Result {
int changes;
int replaces;
vector<int> removed;
};
Result processDirection(const vector<int>& a, bool nonDecreasing) {
int n = a.size();
vector<int> dp(n, 1);
vector<int> prev(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
bool valid = nonDecreasing ? (a[j] <= a[i]) : (a[j] >= a[i]);
if (valid && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
}
int maxLen = *max_element(dp.begin(), dp.end());
vector<int> candidates;
for (int i = 0; i < n; ++i) {
if (dp[i] == maxLen) {
candidates.push_back(i);
}
}
int bestReplace = 1e9;
vector<int> bestIndices;
for (int candidate : candidates) {
vector<int> path;
int current = candidate;
while (current != -1) {
path.push_back(current);
current = prev[current];
}
reverse(path.begin(), path.end());
set<int> pathSet(path.begin(), path.end());
vector<int> sortedPath(path.begin(), path.end());
sort(sortedPath.begin(), sortedPath.end());
int replace = 0;
for (int k = 0; k < n; ++k) {
if (pathSet.count(k)) continue;
auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);
if (it != sortedPath.begin()) {
int leftIdx = *(--it);
if (a[k] < a[leftIdx]) {
replace++;
}
}
}
if (replace < bestReplace || (replace == bestReplace && path.size() > bestIndices.size())) {
bestReplace = replace;
bestIndices = sortedPath;
}
}
set<int> reserved(bestIndices.begin(), bestIndices.end());
vector<int> removed;
for (int i = 0; i < n; ++i) {
if (!reserved.count(i)) {
removed.push_back(i + 1);
}
}
sort(removed.begin(), removed.end());
return { n - maxLen, bestReplace, removed };
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
bool isNonDescending = true;
for (int i = 1; i < N; ++i) {
if (a[i] < a[i-1]) {
isNonDescending = false;
break;
}
}
if (isNonDescending) {
cout << "Non-descending\n";
return 0;
}
bool isNonAscending = true;
for (int i = 1; i < N; ++i) {
if (a[i] > a[i-1]) {
isNonAscending = false;
break;
}
}
if (isNonAscending) {
cout << "Non-ascending\n";
return 0;
}
Result asc = processDirection(a, true);
Result desc = processDirection(a, false);
bool useAsc;
if (asc.changes < desc.changes) {
useAsc = true;
} else if (asc.changes > desc.changes) {
useAsc = false;
} else {
useAsc = (asc.replaces <= desc.replaces);
}
Result res = useAsc ? asc : desc;
cout << res.changes << '\n';
for (size_t i = 0; i < res.removed.size(); ++i) {
if (i > 0) cout << ' ';
cout << res.removed[i];
}
cout << '\n';
return 0;
}字母游戏
一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母,只是顺序不同。换句话说,将 S 中的字母重排顺序就可以得到 T。游戏的每一步,我们可以将 S 中的任一字母移动到串头或串尾,问将 S 变换成 T 至少需要多少步?
时间限制:6000
内存限制:65536
输入
输入分两行,先后给出字母串 S 和 T。如题面所描述的,两者包含同样的小写英文字母,只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg goodmorning
样例输出
8
提示
样例解释:
1、 从 iononmrogdg 开始;
2、 将最后一个 g 移动到串头: giononmrogd;
3、 将 m 移动到串尾: giononrogdm;
4、 将第一个 o 移动到串尾: ginonrogdmo;
5、 将 r 移动到串尾: ginonogdmor;
6、 将第一个 n 移动到串尾: gionogdmorn;
7、 将 i 移动到串尾: gonogdmorni;
8、 将第一个 n 移动到串尾: googdmornin;
9、 将第二个 g 移动到串尾: goodmorning。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int n = s.size();
unordered_map<char, vector<int>> pos_map;
for (int i = 0; i < n; ++i) {
pos_map[s[i]].push_back(i);
}
int max_len = 0;
for (int i = 0; i < n; ++i) {
int current_pos = -1;
int count = 0;
for (int j = i; j < n; ++j) {
char c = t[j];
if (pos_map.find(c) == pos_map.end()) {
break;
}
vector<int>& v = pos_map[c];
auto it = upper_bound(v.begin(), v.end(), current_pos);
if (it == v.end()) {
break;
}
current_pos = *it;
count++;
}
if (count > max_len) {
max_len = count;
}
}
cout << n - max_len << endl;
return 0;
}两枚硬币
伊娃喜欢收集全宇宙的硬币,包括火星币等等。一天她到了一家宇宙商店,这家商店可以接受任何星球的货币,但有一个条件,无论什么价格,都必须用 2 枚硬币一次付清,不能多也不能少。而她有多达 105 个硬币,于是求助于你。给定任一价格,请帮她找出可以付款的 2 枚硬币。
时间限制:1000
内存限制:65536
输入
第 1 行给出 2 个正整数:n (≤ 105)为硬币枚数、m(≤ 103)为伊娃要付清的价格; 第 2 行给出 n 枚硬币的面值,均为不超过 500 的正整数。同行数字间以空格分隔。
输出
在一行中输出两枚硬币的面值 v1 和 v2 ,以 1 个空格分隔,满足条件 v1+v2=m,并且 v1 ≤ v2。如果这样的解不唯一,输出 v1 最小的那个解。如果解不存在,则输出 `No Solution`。
样例输入
样例#1:
8 15 1 2 8 7 2 4 11 15
样例#2:
7 14 1 8 7 2 4 11 15
样例输出
样例#1:
4 11
样例#2:
No Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> coins(n);
for (int i = 0; i < n; ++i) {
cin >> coins[i];
}
if (n < 2) {
cout << "No Solution" << endl;
return 0;
}
sort(coins.begin(), coins.end());
int left = 0, right = n - 1;
while (left < right) {
int sum = coins[left] + coins[right];
if (sum == m) {
cout << coins[left] << " " << coins[right] << endl;
return 0;
} else if (sum < m) {
++left;
} else {
--right;
}
}
cout << "No Solution" << endl;
return 0;
}完美数列
给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M ≤ m*p,则称这个数列是完美数列。
现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
时间限制:1000
内存限制:65536
输入
输入第一行给出两个正整数 n 和 p,其中 n(≤ 105)是输入的正整数的个数,p(≤ 109)是给定的参数。第二行给出 n 个正整数,每个数不超过 109。
输出
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
样例输入
10 8 2 3 20 4 5 1 6 7 8 9
样例输出
8
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, p;
cin >> n >> p;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
sort(nums.begin(), nums.end());
int max_len = 0;
for (int i = 0; i < n; ++i) {
long long target = (long long)nums[i] * p;
auto it = upper_bound(nums.begin() + i, nums.end(), target);
int cnt = it - (nums.begin() + i);
if (cnt > max_len) {
max_len = cnt;
}
}
cout << max_len << endl;
return 0;
}多样解码
将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`,也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的,不能被解码为 `H`。
本题就请你计算一下,给定的数字串有多少种不同的解码结果。
时间限制:1000
内存限制:65536
输入
输入在一行中给出一个不超过 104 位的数字串,串非空且不包含空格。
输出
输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大,你只需要输出其对 1000000007 取模后的结果。
样例输入
1213407
样例输出
5
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
string s;
cin >> s;
int n = s.size();
vector<long long> dp(n + 1, 0);
dp[0] = 1; // 空字符串有一种解码方式
for (int i = 1; i <= n; ++i) {
// 单独处理当前字符,总是允许
dp[i] = dp[i-1];
// 处理两位的情况
if (i >= 2) {
// 提取前两位字符并转换为整数
int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0');
if (two_digit >= 10 && two_digit <= 25) {
dp[i] += dp[i-2];
}
}
dp[i] %= MOD;
}
cout << dp[n] % MOD << endl;
return 0;
}二进制串的评分
对于一个给定的二进制串 s(即仅由字符 0 和 1 组成的串),其评分是这样计算的:将原串切分为若干段,使得每段包含的字符是一样的,且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值(如果只有一段,评分就是这段的长度)。
异或(Exclusive OR,简称 XOR)是一种数学运算符,用于计算机中的位运算。当且仅当两个输入值不同时,异或运算输出为真(1),否则输出为假(0)。
例如,串 "10001100001" 可以切分为 5 段,即 "1"、"000"、"11"、"0000"、"1",其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。
假设每一步我们可以交换 2 个相邻的字符,并且可以这样执行任意多步(当然也可以执行 0 步)。对每个可能的评分 x,你能得到多少个不同的串?将原串 s 通过交换操作变成评分为 x 的串,所用的最少步骤是多少次?
时间限制:1000
内存限制:65536
输入
输入在一行中给出非空的原始二进制串 s,其长度不超过 64。
输出
对每个可能的评分,在一行中输出 3 个空格分隔的整数,依次为:评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。
样例输入
010
样例输出
1 1 0 3 2 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
// 计算二进制串的评分
int calcScore(const std::string& s) {
int score = 0, count = 1;
for (int i = 1; i <= s.size(); ++i) {
if (i == s.size() || s[i] != s[i - 1]) {
score ^= count;
count = 1;
} else {
++count;
}
}
return score;
}
// 广度优先搜索
void bfs(const std::string& start, std::unordered_map<int, std::pair<int, int>>& res) {
std::unordered_map<std::string, int> minSteps;
std::queue<std::string> q;
q.push(start);
minSteps[start] = 0;
while (!q.empty()) {
std::string s = q.front();
q.pop();
int score = calcScore(s);
int steps = minSteps[s];
if (res.find(score) == res.end()) {
res[score] = {1, steps};
} else {
res[score].first++;
res[score].second = std::min(res[score].second, steps);
}
for (int i = 0; i < s.size() - 1; ++i) {
std::string newStr = s;
std::swap(newStr[i], newStr[i + 1]);
if (minSteps.find(newStr) == minSteps.end()) {
minSteps[newStr] = steps + 1;
q.push(newStr);
}
}
}
}
int main() {
std::string s;
std::cin >> s;
std::unordered_map<int, std::pair<int, int>> res;
bfs(s, res);
std::vector<int> scores;
for (const auto& p : res) {
scores.push_back(p.first);
}
std::sort(scores.begin(), scores.end());
for (int score : scores) {
std::cout << score << " " << res[score].first << " " << res[score].second << std::endl;
}
return 0;
}