C/C++编程五级 题库
以下哪个STL容器是基于红黑树实现的,元素自动有序且不重复?( )
STL中,用于在容器中查找指定元素的函数是?( )
以下关于`vector`容器的说法,错误的是?( )
以下代码的输出是?( )
set<int> s; s.insert(5); s.insert(2); s.insert(8); for (int x : s) cout << x <<" ";
C++ 的 set 是有序且元素唯一的容器,默认升序。
以下代码的输出是?( )
map<string, int> m; m["apple"]= 5; m["banana"] = 3; cout << m["apple"];
map 是 C++ 标准模板库的字典,m["apple"] 的值已经设为 5,输出为:5。
查找键 "key" 是否存在,正确的代码是?( )
find() 返回迭代器,如果等于 end() 说明没找到,否则存在。
count() 对于 map 返回 0 或 1,可以判断键是否存在。
set 的组织特点是?( )
C++ 中的 set 是基于红黑树实现的有序关联容器,元素有序、不重复。
`string`类的`c_str()`函数可以将string对象转换为C风格的const char*字符串。( )
map 中的一个键不能对应两组数据。( )
在 C++ 的 map(和 unordered_map)中,每个键只能对应一个值,如果插入相同键的新值,会覆盖旧值。
map 的查找单个键的时间复杂度是 O(log n)。( )
在 C++ 中,map 是基于红黑树(平衡二叉搜索树)实现的,插入、删除、查找操作的时间复杂度都是 O(log n)。
通配符匹配
给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。
其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。
‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。
两个字符串完全匹配才算匹配成功。
时间限制:2000
内存限制:262144
输入
输入为一个数字n表示测试字符串与字符模式对数,换行。(n ≤ 30) 后续2n行为每组匹配的s与p,每行字符串后换行。 s 非空,只包含从 a-z 的小写字母。 p 非空,只包含从 a-z 的小写字母,以及字符 ? 和 *。 字符串s和p的长度均小于50
输出
每一组匹配串匹配成功输出‘yes’,否则输出‘no’。
样例输入
3 abc abc abc a*c abc a??c
样例输出
yes yes no
#include <iostream>
#include <cstring>
using namespace std;
bool isMatch(char* s, char* p) {
int m = strlen(s);
int n = strlen(p);
int i = 0; // s的指针
int j = 0; // p的指针
int star = -1; // 上一个星号的位置
int match = 0; // 上一个星号匹配到的位置
while (i < m) {
if (j < n && (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况
i++;
j++;
}
else if (j < n && p[j] == '*') { // '*'的情况
star = j; // 保存上一个星号的位置
match = i; // 保存当前匹配到的位置
j++; // p的指针向后移动一位
}
else if (star != -1) { // p中有星号,并且当前字符和p的字符不同,则回溯
j = star + 1; // p的指针回到上一个星号的下一位
match++; // 匹配位置向后移动一位
i = match; // s的指针回到上一个星号匹配到的位置的下一位
}
else { // 最后一种情况,匹配失败
return false;
}
}
while (j < n && p[j] == '*') { // 如果p中还有星号,则可以匹配空字符串
j++;
}
return j == n; // s和p都遍历完了才算匹配成功
}
int main() {
int n; // 测试样例数
cin >> n;
char s[51]; // s的最大长度为50,再加上一个结束符'\0'
char p[51]; // p的最大长度为50,再加上一个结束符'\0'
for (int i = 0; i < n; i++) {
cin >> s >> p;
if (isMatch(s, p)) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
}
return 0;
}求逆序对数
对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
时间限制:500
内存限制:65536
输入
输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列
输出
每组数据对应一行,输出逆序对的个数
样例输入
5 1 2 3 4 5 5 5 4 3 2 1 1 1 0
样例输出
0 10 0
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int merge(int a[], int s, int m, int e) {
vector<int> a1;
int m1 = s, m2 = m + 1, c = 0;
while (m1 <= m && m2 <= e) {
if (a[m1] > a[m2]) {
c += m - m1 + 1;
a1.push_back(a[m2]);
m2++;
} else {
a1.push_back(a[m1]);
m1++;
}
}
while (m1 <= m) {
a1.push_back(a[m1]);
m1++;
}
while (m2 <= e) {
a1.push_back(a[m2]);
m2++;
}
int k = 0;
for (int i = s; i <= e; i++)
a[i] = a1[k++];
return c;
}
int solve(int a[], int s, int e) {
if (s >= e)
return 0;
int m = (s + e) / 2;
int l = solve(a, s, m);
int r = solve(a, m + 1, e);
int l_r = merge(a, s, m, e);
return l + r + l_r;
}
int main() {
int n;
int a[N];
while (scanf("%d", &n) && n != 0) {
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int sum = solve(a, 0, n - 1);
cout << sum << endl;
}
return 0;
}分成互质组
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
时间限制:1000
内存限制:65536
输入
第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。
输出
一个正整数,即最少需要的组数。
样例输入
6 14 20 33 117 143 175
样例输出
3
// 参考答案1:
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int n, cnt, ans = N, p[N];
vector<int> s[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int k, int x) {
for (int i = 0; i < s[k].size(); i++)
if (gcd(s[k][i], x) > 1)
return false;
return true;
}
void dfs(int u) {
if (u == n) {
ans = min(ans, cnt);
return;
}
for (int i = 0; i < cnt; i++)
if (check(i, p[u])) {
s[i].push_back(p[u]);
dfs(u + 1);
s[i].pop_back();
}
s[cnt++].push_back(p[u]);
dfs(u + 1);
s[--cnt].pop_back();
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(0);
cout << ans << endl;
return 0;
}
// 参考答案2:
#include <iostream>
using namespace std;
const int N = 15;
int n;
int p[N];
int group[N][N];
bool used[N];
int ans = N;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int group[], int k, int x) {
for (int i = 0; i < k; i++)
if (gcd(p[group[i]], x) > 1)
return false;
return true;
}
void dfs(int g, int gc, int cnt, int start) {
if (g >= ans)
return;
if (cnt == n)
ans = g;
bool flag = false;
for (int i = start; i < n; i++)
if (!used[i] && check(group[g], gc, p[i])) {
used[i] = true;
group[g][gc] = i;
dfs(g, gc + 1, cnt + 1, i + 1);
used[i] = false;
flag = true;
}
if (!flag)
dfs(g + 1, 0, cnt, 0);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i];
dfs(1, 0, 0, 0);
cout << ans << endl;
return 0;
}拼点游戏
C和S两位同学一起玩拼点游戏。有一堆白色卡牌和一堆蓝色卡牌,每张卡牌上写了一个整数点数。C随机抽取n张白色卡牌,S随机抽取n张蓝色卡牌,他们进行n回合拼点,每次两人各出一张卡牌,点数大者获得三颗巧克力,小者获得一颗巧克力,如果点数相同,每人各得二颗巧克力,使用过的卡牌不得重复使用。已知C和S取到的卡牌点数,请编程计算S最多和最少能得到多少颗巧克力。
时间限制:1000
内存限制:65536
输入
输入包含多组测试数据。 每组测试数据的第一行是一个整数n(1<=n<=1000),接下来一行是n个整数,表示C抽到的白色卡牌的点数,下一行也是n个整数,表示S抽到的蓝色卡牌的点数。 输入的最后以一个0表示结束。
输出
对每组数据,输出一行,内容是两个整数用空格格开,分别表示S最多和最少可获得的巧克力数。
样例输入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
样例输出
9 5 4 4 4 4
#include <bits/stdc++.h>
using namespace std;
int n, o = 0;
int c[1000] = {0}, s[1000] = {0};
int c1[1000], s1[1000];
int main() {
while (cin >> n, n) {
o++;
for (int i = 0; i < n; i++) {
cin >> c[i];
}
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int cs = 0, ss = 0;
int ch = 0, sh = 0, ct = n - 1, st = n - 1;
sort(c, c + n);
sort(s, s + n);
while (ch <= ct) {
if (s[st] > c[ct]) {
ss += 3;
cs += 1;
st--;
ct--;
} else if (s[st] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[st] == c[ct]) {
if (s[sh] <= c[ch]) {
if (s[sh] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[sh] == c[ct]) {
ss += 2;
cs += 2;
sh++;
ct--;
}
} else {
ss += 3;
cs += 1;
sh++;
ch++;
}
}
}
s1[o] = ss;
for (int i = 0; i < n; i++) {
swap(c[i], s[i]);
}
cs = 0, ss = 0;
ch = 0, sh = 0, ct = n - 1, st = n - 1;
sort(c, c + n);
sort(s, s + n);
while (ch <= ct) {
if (s[st] > c[ct]) {
ss += 3;
cs += 1;
st--;
ct--;
} else if (s[st] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[st] == c[ct]) {
if (s[sh] <= c[ch]) {
if (s[sh] < c[ct]) {
ss += 1;
cs += 3;
sh++;
ct--;
} else if (s[sh] == c[ct]) {
ss += 2;
cs += 2;
sh++;
ct--;
}
} else {
ss += 3;
cs += 1;
sh++;
ch++;
}
}
}
c1[o] = cs;
}
for (int i = 1; i <= o; i++) {
cout << s1[i] << " " << c1[i] << endl;
}
return 0;
}数字变换
给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加1。如果加1后大于9,则变为0
3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。
时间限制:1000
内存限制:65536
输入
有最多 100,000 组数据 每组数据就是包含5个数字的字符串
输出
对每组数据,输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
char a[6] = "12345";
bool vis[100000][4][3];
int ans[100000];
struct node {
string a;
int op2, op3, step;
node(string aa, int o2, int o3, int ss = 0)
: a(aa), op2(o2), op3(o3), step(ss){};
};
queue<node> q;
int main() {
memset(vis, false, sizeof(vis));
memset(ans, -1, sizeof(ans));
q.push(node("12345", 0, 0));
vis[12345][0][0] = true;
ans[12345] = 0;
while (!q.empty()) {
node no = q.front();
q.pop();
string temp = no.a;
if (ans[int(atof(temp.c_str()))] == -1)
ans[int(atof(temp.c_str()))] = no.step;
// cout<<no.a<<endl;
// 第一种操作
for (int i = 0; i < 4; i++) {
swap(temp[i], temp[i + 1]);
if (!vis[int(atof(temp.c_str()))][no.op2][no.op3]) {
vis[int(atof(temp.c_str()))][no.op2][no.op3] = true;
q.push(node(temp, no.op2, no.op3, no.step + 1));
}
swap(temp[i], temp[i + 1]);
}
// 第二种操作
if (no.op2 < 3) {
for (int i = 0; i < 5; i++) {
temp = no.a;
int num = temp[i] - '0';
num++;
if (num == 10)
num = 0;
temp[i] = '0' + num;
if (!vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3]) {
vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3] = true;
q.push(node(temp, no.op2 + 1, no.op3, no.step + 1));
}
}
}
// 第三种操作
if (no.op3 < 2) {
for (int i = 0; i < 5; i++) {
temp = no.a;
int num = temp[i] - '0';
num *= 2;
if (num > 9)
num %= 10;
temp[i] = '0' + num;
if (!vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1]) {
vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1] = true;
q.push(node(temp, no.op2, no.op3 + 1, no.step + 1));
}
}
}
}
while (cin >> a) {
cout << ans[int(atof(a))] << endl;
}
return 0;
}Freda的越野跑
Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。
假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?
时间限制:1000
内存限制:262144
输入
第一行1个整数N。 第二行为N 个非负整数,按从前到后的顺序给出每个人的跑步速度。 对于50%的数据,2<=N<=1000。 对于100%的数据,2<=N<=100000。
输出
一个整数,表示有多少对参赛者之间发生赶超事件。
样例输入
5 1 3 10 8 5
样例输出
7
提示
我们把这5个人依次编号为A,B,C,D,E,速度分别为1,3,10,8,5。 在跑步过程中: B,C,D,E均会超过A,因为他们的速度都比A快; C,D,E都会超过B,因为他们的速度都比B快; C,D,E之间不会发生赶超,因为速度快的起跑时就在前边。
#include <iostream>
using namespace std;
int a[100001];
int ta[100001];
long long int ans = 0;
void merge(int left, int right, int middle) {
int i, j, index1, index2;
for (j = left; j <= right; ++j)
ta[j] = a[j];
index1 = left;
index2 = middle + 1;
i = left;
while (index1 <= middle && index2 <= right) {
if (ta[index1] >= ta[index2]) {
a[i] = ta[index1];
++i;
++index1;
} else {
a[i] = ta[index2];
ans += middle - index1 + 1; // 这个右子列元素超过了左子列中剩余的元素
++i;
++index2;
}
}
while (index1 <= middle) {
a[i] = ta[index1];
++i;
++index1;
}
while (index2 <= right) {
a[i] = ta[index2];
++i;
++index2;
}
}
void mergesort(int left, int right) {
int middle;
if (left < right) {
middle = (left + right) / 2;
mergesort(left, middle);
mergesort(middle + 1, right);
merge(left, right, middle);
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
mergesort(0, n - 1);
cout << ans;
// system("pause");
return 0;
}问题求解
给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。
举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
时间限制:1000
内存限制:65536
输入
输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。
输出
对于每个N,输出对应的M。
样例输入
1 2 3 4 78 0
样例输出
2 4 5 8 83
//解法1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 1001
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int cnt=0;
int temp=n;
while(temp>0)
{
if(temp%2)
cnt++;
temp/=2;
}
int sum=0;
while(1)
{
temp=++n;
while(temp>0)
{
if(temp%2)
sum++;
temp/=2;
}
if(cnt==sum)
{
cout<<n<<endl;
break;
}
sum=0;
}
}
return 0;
}//解法2 样例代码 枚举
using namespace std;
int n; // 定义变量 n
int tj(int x) {
int ans = 0; // 定义变量 ans
while (x) { // 当 x 不为0循环执行
if (x &)
ans++; // 如果 x 的最低位为1,则将 ans 加1
x >>= 1; // 将 x 右移1位,即将 x 的二进制表示向右移动一位
}
return ans; // 返回 ans
}
int main() {
while (1) { // 无限循环
cin >> n; // 从标准输入读取一个整数 n
if (!n)break; 如果 n 为0,则结束循环
int t = tj(n); // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
for (int i = n + 1;; i++) { // 从 n+1 开始递增遍历整数 i
if (t == tj(i)) {
cout << i << endl; // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
break; // 结束循环
}
}
}
return 0; // 返回 0,表示程序正常结束
}