C/C++编程六级 题库
无向图的邻接矩阵是对称矩阵。( )
哈希冲突是指两个不同的关键字,通过哈希函数得到了相同的哈希地址。( )
一棵有n个节点的树,恰好有n-1条边。( )
波兰表达式
波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
#include <bits/stdc++.h>
using namespace std;
double exp() {
char s[20];
cin >> s;
switch (s[0]) {
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return stof(s);
}
}
int main() {
printf("%0.6f", exp());
return 0;
}括号配对
字符串中可能有三种成对的括号,"( )"、"[ ]"、"{ }"。请判断字符串的括号是否都正确配对。无括号也算正确配对。括号交叉算不正确配对,例如"12{34[78}ab]"就不算正确配对。但是一对括号被包含在另一对括号里面,例如"12{ab[8]}"不影响正确性。
时间限制:1000
内存限制:65536
输入
第一行为整数n(n<40),接下来有n行,每行一个无空格的字符串,长度小于1000。
输出
对每行字符串,如果括号配对,输出"YES",否则输出"NO"。
样例输入
2
12{ab[8]}
12{34[78}ab]样例输出
YES NO
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n;
while (n--) {
cin >> s;
stack<char> st;
int ls = s.size();
bool sign = true;
for (int i = 0; i < ls; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
st.push(s[i]);
else if (!st.empty() && s[i] == ')') {
if (st.top() == '(')
st.pop();
else
sign = false;
} else if (s[i] == '}') {
if (!st.empty() && st.top() == '{')
st.pop();
else
sign = false;
} else if (s[i] == ']') {
if (!st.empty() && st.top() == '[')
st.pop();
else
sign = false;
}
}
if (st.empty() && sign)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}扑克牌排序(2023.3)
假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:
1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序
2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。
例如,对于如下的四张牌,有如下的升序排序结果:
D3,C4,A4,C1
升序排序的结果为A4,C1,C4,D3
有人提出了如下的排序策略:
先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。
例如,对于上面的结果,依次进队后,结果如下:
队列1:C1;队列3:D3,队列4:C4,A4
将其依次出队后,结果为C1,D3,C4,A4
然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。
例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:
队列1:A4;队列3:C1,C4;队列4:D3
将其依次出队后,结果为A4,C1,C4,D3,排序结束。
请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。
时间限制:1000
内存限制:65536
输入
输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9
输出
输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)
样例输入
8 D8 A6 C3 B8 C5 A1 B5 D3
样例输出
Queue1:A1 Queue2: Queue3:C3 D3 Queue4: Queue5:C5 B5 Queue6:A6 Queue7: Queue8:D8 B8 Queue9: QueueA:A1 A6 QueueB:B5 B8 QueueC:C3 C5 QueueD:D3 D8 A1 A6 B5 B8 C3 C5 D3 D8
提示
第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
queue<string> qn[9];
queue<string> color[4];
queue<string> qs;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
int t = s[1] - '0' - 1;
qn[t].push(s);
}
for (int i = 0; i <= 8; i++) {
cout << "Queue" << i + 1 << ":";
while (!qn[i].empty()) {
s = qn[i].front();
switch (s[0]) {
case 'A':
color[0].push(s);
break;
case 'B':
color[1].push(s);
break;
case 'C':
color[2].push(s);
break;
case 'D':
color[3].push(s);
break;
}
qn[i].pop();
cout << s << " ";
}
cout << endl;
}
for (int i = 0; i <= 3; i++) {
cout << "Queue" << (char)('A' + i) << ":";
while (!color[i].empty()) {
s = color[i].front();
color[i].pop();
qs.push(s);
cout << s << " ";
}
cout << endl;
}
while (!qs.empty()) {
cout << qs.front() << " ";
qs.pop();
}
return 0;
}滑动窗口
给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。
下面是一个例子:
数组是 [1 3 -1 -3 5 3 6 7], k = 3。

你的任务是得到滑动窗口在每个位置时的最大值和最小值。
时间限制:20000
内存限制:65536
输入
输入包括两行。 第一行包括n和k,分别表示数组的长度和窗口的大小。 第二行包括n个数字。
输出
输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。
样例输入
8 3 1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
#include#include #include using namespace std; int n, k, tmp; deque p; deque q; vector arr; vector MyMax; vector MyMin; int main() { cin >> n >> k; for (int i = 0; i < n; ++i) { scanf("%d", &tmp); arr.push_back(tmp); } for (int i = 0; i < n; ++i) { if (!p.empty() && p.front() == i - k) // 把窗口划过部分的序号删掉 p.pop_front(); while (!p.empty() && arr[p.back()] < arr[i]) // 删去队尾比当前元素小的,肯定用不到他们 p.pop_back(); p.push_back(i); // 当前元素入队 if (i >= k - 1) // 从k-1开始记录(第一个窗口 MyMax.push_back(arr[p.front()]); } for (int i = 0; i < n; ++i) { if (!q.empty() && q.front() == i - k) q.pop_front(); while (!q.empty() && arr[q.back()] > arr[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) MyMin.push_back(arr[q.front()]); } for (int i = 0; i <= n - k; ++i) cout << MyMin[i] << ' '; cout << endl; for (int i = 0; i <= n - k; ++i) cout << MyMax[i] << ' '; return 0; }
区间合并(2022-12-六级)
给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。
时间限制:1000
内存限制:65536
输入
第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。
输出
输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。
样例输入
5 5 6 1 5 10 10 6 9 8 10
样例输出
1 10
#include <bits/stdc++.h>
using namespace std;
struct Nod {
int x, y;
friend bool operator<(Nod a, Nod b) {
if (a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
} node[50005];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> node[i].x >> node[i].y;
sort(node, node + n);
int lf = node[0].x;
int rt = node[0].y;
for (int i = 1; i < n; i++) {
if (lf <= node[i].x && node[i].x <= rt) {
rt = max(rt, node[i].y);
} else {
cout << "no";
return 0;
}
}
cout << lf << " " << rt;
return 0;
}电话号码(2022-12,六级)
给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。
时间限制:1000
内存限制:65536
输入
第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。
样例输入
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
样例输出
NO YES
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Trie {
int c[10], s;
Trie() {
memset(c, 0, sizeof(c));
s = 0;
}
} t[N];
int tot;
void clear(int x) {
t[x].s = 0;
for (int i = 0; i <= 9; i++)
if (t[x].c[i])
clear(t[x].c[i]), t[x].c[i] = 0;
}
char s[15];
bool bt(int x) {
int len = strlen(s + 1);
bool bk = false;
for (int i = 1; i <= len; i++) {
int y = s[i] - '0';
if (!t[x].c[y])
t[x].c[y] = ++tot;
else if (i == len)
bk = true;
x = t[x].c[y];
if (t[x].s)
bk = true;
}
t[x].s++;
return bk;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
bool bk = false;
clear(0);
tot = 0;
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
if (bk)
continue;
if (bt(0))
bk = true;
}
if (bk)
puts("NO");
else
puts("YES");
}
return 0;
}
扑克牌排序
假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:
1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序
2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。
例如,对于如下的四张牌,有如下的升序排序结果:
D3,C4,A4,C1
升序排序的结果为A4,C1,C4,D3
有人提出了如下的排序策略:
先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。
例如,对于上面的结果,依次进队后,结果如下:
队列1:C1;队列3:D3,队列4:C4,A4
将其依次出队后,结果为C1,D3,C4,A4
然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。
例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:
队列1:A4;队列3:C1,C4;队列4:D3
将其依次出队后,结果为A4,C1,C4,D3,排序结束。
请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。
时间限制:1000
内存限制:65536
输入
输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9
输出
输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)
样例输入
8 D8 A6 C3 B8 C5 A1 B5 D3
样例输出
Queue1:A1 Queue2: Queue3:C3 D3 Queue4: Queue5:C5 B5 Queue6:A6 Queue7: Queue8:D8 B8 Queue9: QueueA:A1 A6 QueueB:B5 B8 QueueC:C3 C5 QueueD:D3 D8 A1 A6 B5 B8 C3 C5 D3 D8
提示
第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
queue<string> qn[9];
queue<string> color[4];
queue<string> qs;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
int t = s[1] - '0' - 1;
qn[t].push(s);
}
for (int i = 0; i <= 8; i++) {
cout << "Queue" << i + 1 << ":";
while (!qn[i].empty()) {
s = qn[i].front();
switch (s[0]) {
case 'A':
color[0].push(s);
break;
case 'B':
color[1].push(s);
break;
case 'C':
color[2].push(s);
break;
case 'D':
color[3].push(s);
break;
}
qn[i].pop();
cout << s << " ";
}
cout << endl;
}
for (int i = 0; i <= 3; i++) {
cout << "Queue" << (char)('A' + i) << ":";
while (!color[i].empty()) {
s = color[i].front();
color[i].pop();
qs.push(s);
cout << s << " ";
}
cout << endl;
}
while (!qs.empty()) {
cout << qs.front() << " ";
qs.pop();
}
return 0;
}现代艺术
在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。
尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示,但她的创作风格依然保持不变:从一张空白的矩形画布上,不断地画上一些矩形,在一维的情况下,这些矩形就只是一个区间。她用N种颜色,颜色编号为1~N进行创作,每种颜色只使用一次,之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。
令Picowso感到十分沮丧的是,她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作,Moonet会画一些不相交的间隔,等待这些颜色晾干,然后再画另外的一些间隔,直到画完。Moonet每次每种颜色最多只能画一个间隔,但是他可以一次画不同颜色不相交的多个间隔,只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。
时间限制:10000
内存限制:65536
输入
第一行是一个整数N,之后N行包含了N个整数,范围0到N表示纸带每个格点的颜色,0表示没有涂色。
输出
输出一行,需要复制这幅画作的最少回合数,如果这幅画不可能是Picowso的画作输出-1(比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的)
样例输入
7 0 1 4 5 1 3 3
样例输出
2
提示
在这个样例中,第一轮涂成0111133,第二轮涂成0145133,所以共需两轮。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int end_pos[N], a[N];
int n, result, flag = 1;
char v[N];
stack<int> s;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i += 1) {
scanf("%d", &a[i]);
end_pos[a[i]] = i; // 记录每个颜色的终点位置
}
v[0] = 1; // 初始化 将0视为覆盖整个画布的第一种颜色
end_pos[0] = n + 1;
s.push(0);
for (int i = 1; i <= n && flag; i++) {
if (s.top() != a[i]) {
if (v[a[i]])
flag = 0; // 颜色被使用过 标记非法
s.push(a[i]); // 加入新的颜色
}
v[a[i]] = 1; // 标记该颜色被使用过
result = max(result, (int)s.size());
if (i == end_pos[a[i]]) {
s.pop(); // 该颜色最后一次被使用 弹出改颜色
}
}
if (!flag)
cout << -1;
else
cout << result - 1;
return 0;
}字符串插入
有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。
时间限制:1000
内存限制:65536
输入
输入包括若干行,每一行为一组测试数据,格式为 str substr
输出
对于每一组测试数据,输出插入之后的字符串。
样例输入
abcab eee 12343 555
样例输出
abceeeab 12345553
#include<bits/stdc++.h>
using namespace std;
int main()
{
string str,substr;
while(cin>>str>>substr)
{
int maxn=0,maxid,i;
for(i=0;i<str.size();i++)
{
if((str[i]-'0')>maxn)
{
maxn=str[i]-'0';
maxid=i;
}
}
for(i=0;i<str.size();i++)
{
cout<<str[i];
if(i==maxid) cout<<substr;
}
cout<<endl;
}
return 0;
}机器翻译
VariantF的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
时间限制:1000
内存限制:262144
输入
第一行为两个正整数M 和N,代表内存容量和文章的长度。 第二行为N 个非负整数,按照文章的顺序,每个数(大小不超过1000000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 对于50%的数据,1<=N、M<=1000; 对于100%的数据,1<=N、M<=1000000。
输出
一个整数,为软件需要查词典的次数。
样例输入
3 7 1 2 1 5 4 4 1
样例输出
5
提示
整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词1 并调入内存。 2. 1 2:查找单词2 并调入内存。 3. 1 2:在内存中找到单词1。 4. 1 2 5:查找单词5 并调入内存。 5. 2 5 4:查找单词4 并调入内存替代单词1。 6. 2 5 4:在内存中找到单词4。 7. 5 4 1:查找单词1 并调入内存替代单词2。 共计查了5 次词典。
#include<cstdio>
int word[2000];
bool sch(int tgt,int range)//线性搜索,因为数据<1000,不会超时。
{
for(int i=0;i<range;i++)
{
if(word[i]==tgt)
{
return true;
}
}
return false;
}
int main()
{
int mem,num,tm,wor,ans=0;
scanf("%d %d",&mem,&num);
tm=0;
for(int i=0;i<2000;i++)
{
word[i]=-1;//数组初始化一定要初始化成-1!!!!
//字母代号有可能是0,所以初始化成0会出错!!!!
}
for(int i=0;i<num;i++)
{
scanf("%d",&wor);
//非常节省空间和时间的模拟
if(tm>=mem)
{
tm=0;
}
if(!sch(wor,mem))
{
//自己进行轮回。。。
ans++;
word[tm]=wor;
tm++;
}
}
printf("%d",ans);
}// 题解2
#include <bits/stdc++.h>
using namespace std;
int main() {
deque<int> v;
int m, n, ans = 0;
cin >> m >> n;
for (int i = 1, a; i <= n; i++) {
cin >> a;
if (v.empty()) {
v.push_back(a);
ans++;
} else {
auto it = std::find(v.begin(), v.end(), a);
if (it != v.end())
continue;
else {
if (v.size() == unsigned(m))
v.pop_front();
v.push_back(a);
ans++;
}
}
}
cout << ans;
return 0;
}