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

C/C++编程三级 题库

共 126 道题 ,第 7 / 7 页 · 按题型筛选,点「查看答案」核对解析
121 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

狼人杀简单版

以下文字摘自《灵机一动·好玩的数学》:“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中,1 号玩家说:“2 号是狼人”,2 号玩家说:“3 号是好人”,3 号玩家说:“4 号是狼人”,4 号玩家说:“5 号是好人”,5 号玩家说:“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色,有 2 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家?

本题是这个问题的升级版:已知 n 名玩家中有 2 人扮演狼人角色,有 2 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家?

时间限制:1000

内存限制:65536

输入

输入在第一行中给出一个正整数 n(5 ≤ n ≤ 100)。随后 n 行,第 i 行给出第 i 号玩家说的话(1 ≤ i ≤ n),即一个玩家编号,用正号表示好人,负号表示狼人。

输出

如果有解,在一行中按递增顺序输出 2 个狼人的编号,其间以空格分隔,行首尾不得有多余空格。如果解不唯一,则输出最小序列解 —— 即对于两个序列 A = { a[1], ..., a[M] } 和 B = { b[1], ..., b[M] },若存在 0 ≤ k < M 使得 a[i]=b[i] (i ≤ k),且 a[k+1] < b[k+1],则称序列 A 小于序列 B。若无解则输出 `No Solution`。


样例输入

样例#1:

5
-2
+3
-4
+5
+4

样例#2:

6
+6
+3
+1
-5
-2
+4

样例#3:

5
-2
-3
-4
-5
-1

样例输出

样例#1:

1 4

样例#2:

1 5

样例#3:

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

int main() {
	int n;
	cin >> n;
	vector<int> statements(n);
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		statements[i] = stoi(s);
	}
	
	// 枚举所有可能的狼人组合(x, y),其中 x < y
	for (int x = 1; x <= n; ++x) {
		for (int y = x + 1; y <= n; ++y) {
			int lieCount = 0;
			bool wolfLie = false;
			bool xTruth = false, yTruth = false;
			
			// 验证每个玩家的发言
			for (int i = 0; i < n; ++i) {
				int target = abs(statements[i]);
				bool actual = (target == x || target == y); // 实际是否为狼人
				bool claim = (statements[i] < 0);           // 玩家的断言是否为狼人
				
				// 判断是否说谎
				if (actual != claim) {
					lieCount++;
					if (i + 1 == x || i + 1 == y) wolfLie = true; // 狼人是否说谎
				}
				
				// 记录狼人的发言真实性
				if (i + 1 == x) xTruth = (actual == claim);
				if (i + 1 == y) yTruth = (actual == claim);
			}
			
			// 验证条件:恰好两个谎言、有狼人说谎、狼人发言不同
			if (lieCount == 2 && wolfLie && xTruth != yTruth) {
				cout << x << " " << y << endl;
				return 0;
			}
		}
	}
	
	cout << "No Solution" << endl;
	return 0;
}
题目详情
122 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

增高垫

网传最大号的增高垫有 16 厘米,可以一下把 1.64 米的男孩变成一米八的大汉,不少对自己身高缺乏自信的男生女生会悄悄买来穿,特别是大家站成一排拍照的时候。

假设准备拍照的一排人中,只要有人看到身边紧挨着的人比自己高,就会忍不住穿增高垫,并且一定要比人家多穿一层。你的任务就是在看过这一排人的身高后,算出谁穿了最多层的增高垫。

时间限制:1000

内存限制:65536

输入

输入首先在第一行给出正整数 n(≤ 104),为一排人的个数。随后一行给出 n 个正整数,表示 n 个人的身高(厘米)。每个数值是不超过 300 的正整数,数字间以空格分隔。

输出

在一行中输出穿了最多层增高垫的人的位置和穿的层数(位序从左到右,从 1 开始)。如果有并列,按从左到右的顺序,每个人的信息占一行。


样例输入

10
150 160 186 200 170 175 180 186 186 183

样例输出

1 3
5 3
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> height(n);
	for (int i = 0; i < n; ++i) {
		cin >> height[i];
	}
	
	vector<int> layers(n, 0);
	
	// 从左到右处理左边比自己高的情况
	for (int i = 1; i < n; ++i) {
		if (height[i - 1] > height[i]) {
			layers[i] = layers[i - 1] + 1;
		}
	}
	
	// 从右到左处理右边比自己高的情况
	for (int i = n - 2; i >= 0; --i) {
		if (height[i + 1] > height[i]) {
			layers[i] = max(layers[i], layers[i + 1] + 1);
		}
	}
	
	// 找出最大层数
	int max_layer = *max_element(layers.begin(), layers.end());
	
	// 输出所有层数等于最大层数的位置
	for (int i = 0; i < n; ++i) {
		if (layers[i] == max_layer) {
			cout << i + 1 << " " << max_layer << endl;
		}
	}
	
	return 0;
}
题目详情
123 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

三元组的离心力

三元组 (a,b,c) 的“离心力”定义为 |a-b|+|b-c|+|c-a|。现给定三个非空的整数集合 S1、S2、S3,请你找出所有跨这三个集合的三元组 (a,b,c)(即 a∈ S1,b∈ S2,c∈ S3)的最小离心力。

时间限制:1000

内存限制:65536

输入

输入第一行给出三个不超过 104 的正整数 n1、n2、n3,依次为集合 S1、S2、S3 中元素的个数(注意一个集合内没有相同的元素)。随后三行,顺次给出三个集合的元素,均为 [-104 , 104] 内的整数。同行数字间以空格分隔。

输出

在一行中输出 `LiXinLi(a, b, c) = d`,其中 `(a, b, c)` 是具有最小离心力的三元组,`d` 是对应的离心力。如果解不唯一,输出那个最大的解。 注意:(a1,a2,a3)>(b1,b2,b3) 是指,存在 1 ≤ k ≤ 3 使得 ai=bi 对 1 ≤ i < k 成立,并且 ak > bk。


样例输入

4 4 6
0 9 -1 11
10 -25 11 -10
9 2 41 17 12 30

样例输出

LiXinLi(11, 11, 12) = 2

提示

注意到样例实际上有两组解,另外一组解是 (9, 10, 9)。因为 (11, 11, 12) 比较大,所以输出的是这组解。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <climits>

using namespace std;

vector<int> find_closest(const vector<int>& arr, int x) {
	vector<int> res;
	int n = arr.size();
	if (n == 0) return res;
	auto it = lower_bound(arr.begin(), arr.end(), x);
	int pos = it - arr.begin();
	if (pos == 0) {
		res.push_back(arr[0]);
	} else if (pos == n) {
		res.push_back(arr.back());
	} else {
		int prev = arr[pos - 1];
		int curr = arr[pos];
		if (x - prev < curr - x) {
			res.push_back(prev);
		} else if (x - prev > curr - x) {
			res.push_back(curr);
		} else {
			res.push_back(prev);
			res.push_back(curr);
		}
	}
	return res;
}

int main() {
	int n1, n2, n3;
	cin >> n1 >> n2 >> n3;
	vector<int> S1(n1), S2(n2), S3(n3);
	for (int i = 0; i < n1; ++i) cin >> S1[i];
	for (int i = 0; i < n2; ++i) cin >> S2[i];
	for (int i = 0; i < n3; ++i) cin >> S3[i];
	
	sort(S1.begin(), S1.end());
	sort(S2.begin(), S2.end());
	sort(S3.begin(), S3.end());
	
	vector<tuple<int, int, int>> candidates;
	
	// Process S1 elements
	for (int a : S1) {
		auto b_list = find_closest(S2, a);
		auto c_list = find_closest(S3, a);
		for (int b : b_list) {
			for (int c : c_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	// Process S2 elements
	for (int b : S2) {
		auto a_list = find_closest(S1, b);
		auto c_list = find_closest(S3, b);
		for (int a : a_list) {
			for (int c : c_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	// Process S3 elements
	for (int c : S3) {
		auto a_list = find_closest(S1, c);
		auto b_list = find_closest(S2, c);
		for (int a : a_list) {
			for (int b : b_list) {
				candidates.emplace_back(a, b, c);
			}
		}
	}
	
	int min_range = INT_MAX;
	for (const auto& t : candidates) {
		int a = get<0>(t), b = get<1>(t), c = get<2>(t);
		int current_min = min({a, b, c});
		int current_max = max({a, b, c});
		min_range = min(min_range, current_max - current_min);
	}
	
	vector<tuple<int, int, int>> min_candidates;
	for (const auto& t : candidates) {
		int a = get<0>(t), b = get<1>(t), c = get<2>(t);
		int current_min = min({a, b, c});
		int current_max = max({a, b, c});
		if (current_max - current_min == min_range) {
			min_candidates.push_back(t);
		}
	}
	
	tuple<int, int, int> best = min_candidates[0];
	for (const auto& t : min_candidates) {
		if (t > best) {
			best = t;
		}
	}
	
	int a = get<0>(best), b = get<1>(best), c = get<2>(best);
	int d = 2 * (max({a, b, c}) - min({a, b, c}));
	cout << "LiXinLi(" << a << ", " << b << ", " << c << ") = " << d << endl;
	
	return 0;
}
题目详情
124 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

分玩具

已知 n 位小朋友对 m 件玩具的喜好(n ≤ m),现要将 m 件玩具分给 n 位小朋友,每位小朋友只能分到 1 件玩具,每件玩具也最多只能分给 1 位小朋友,并且还要求每位小朋友都能分到自己喜欢的玩具。

本题请你对任意 n 和 m 尝试列出所有满足要求的方案。

时间限制:5000

内存限制:65536

输入

输入第一行给出两个正整数 n 和 m(n ≤ m ≤ 8),即小朋友人数和玩具的数量。 随后 n 行,每行给出 m 个数字。其中第 i 行第 j 个数字为 1 表示第 i 位小朋友喜欢第 j 件玩具,为 0 则表示不喜欢。

输出

按升序列出所有满足要求的方案,格式为 (s1, … , sn)。其中 si 表示第 i 位小朋友分到了第 si 件玩具。 注:方案 (a1, … , an) < (b1, … , bn) 是指存在 1 ≤ k ≤ n,使得 ai = bi 对所有 1 ≤ i< k 成立,并且有 ak < bk。


样例输入

4 5
0 1 0 0 1
1 1 0 1 0
1 0 1 1 0
0 0 0 1 1

样例输出

(2, 1, 3, 4)
(2, 1, 3, 5)
(2, 1, 4, 5)
(2, 4, 1, 5)
(2, 4, 3, 5)
(5, 1, 3, 4)
(5, 2, 1, 4)
(5, 2, 3, 4)
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(int k, int mask, vector<int>& path, vector<vector<int>>& res, const vector<vector<int>>& preferences) {
	if (k == preferences.size()) {
		res.push_back(path);
		return;
	}
	for (int j : preferences[k]) {
		if (!(mask & (1 << (j - 1)))) {
			path.push_back(j);
			backtrack(k + 1, mask | (1 << (j - 1)), path, res, preferences);
			path.pop_back();
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> preferences(n);
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int x;
			cin >> x;
			if (x == 1) {
				preferences[i].push_back(j + 1); // 玩具编号从1开始
			}
		}
		sort(preferences[i].begin(), preferences[i].end()); // 对每个小朋友的喜好进行排序
	}
	
	vector<vector<int>> res;
	vector<int> path;
	backtrack(0, 0, path, res, preferences);
	
	sort(res.begin(), res.end());
	
	for (const auto& vec : res) {
		cout << "(";
		for (size_t i = 0; i < vec.size(); ++i) {
			if (i > 0) {
				cout << ", ";
			}
			cout << vec[i];
		}
		cout << ")" << endl;
	}
	
	return 0;
}
题目详情
125 简答题 适中 C/C++编程考级 ·C/C++编程三级 · 未分类

倒水游戏

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

int main()
{
    int ca, cb;
    cin >> ca >> cb;
    int a = 0, b = 0;  // a是A杯当前水量,b是B杯当前水量
    int t;
    cin >> t;
    while (t--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            // 1:A装满
            a = ca;
        }
        else if (op == 2)
        {
            // 2:B装满
            b = cb;
        }
        else if (op == 3)
        {
            // 3:A倒入B
            int add = min(a, cb - b);
            a -= add;
            b += add;
        }
        else if (op == 4)
        {
            // 4:B倒入A
            int add = min(b, ca - a);
            b -= add;
            a += add;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}
题目详情
126 简答题 适中 C/C++编程考级 ·C/C++编程三级 · 未分类

字符串后缀

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

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        int len = s.size();
        // ing是3个字符,优先判断长后缀,避免出错
        if (len >= 3 && s.substr(len - 3, 3) == "ing")
        {
            s = s.substr(0, len - 3);
        }
        else if (len >= 2)
        {
            string suf = s.substr(len - 2, 2);
            if (suf == "er" || suf == "ed" || suf == "ly")
            {
                s = s.substr(0, len - 2);
            }
        }
        cout << s << endl;
    }
    return 0;
}
题目详情