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

C/C++编程四级 题库

共 88 道题 ,第 5 / 5 页 · 按题型筛选,点「查看答案」核对解析
81 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

兔子不吃窝边草

有谚语云:“兔子不吃窝边草”。现给定若干块排列成一条线的草皮,假设兔子从任何一块草皮开始吃,但吃完一块后,绝对不吃直接相邻的草皮,则兔子最多可以吃掉多少草?

时间限制: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;
}
题目详情
82 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

漂亮的序列

对于给定的整数 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;
}
题目详情
83 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

园林修整

园林修整中,常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了,就需要裁剪;如果太矮了,则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比,所以需要你替他想一种最省力的修整方案。

时间限制: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;
}
题目详情
84 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

字母游戏

一个简单的字母游戏是这样进行的:游戏开始时,我们有两个由小写英文字母组成的串 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;
}
题目详情
85 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

两枚硬币

伊娃喜欢收集全宇宙的硬币,包括火星币等等。一天她到了一家宇宙商店,这家商店可以接受任何星球的货币,但有一个条件,无论什么价格,都必须用 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;
}
题目详情
86 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

完美数列

给定一个正整数数列,和正整数 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;
}
题目详情
87 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 1 指针

多样解码

将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 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;
}
题目详情
88 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

二进制串的评分

对于一个给定的二进制串 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;
}
题目详情