GESP-C++四级 题库
以下C++代码,尝试对有 n 个整数的数组 arr 进行排序。这个代码实现了选择排序算法。( )
正确,每次找到最小的值的索引minIndex,和当前数值交换,符合选择排序的特征。
int& a 和 &a 是一样的,都是取 a 的地址。
&a是取a的地址,而int& a 是引用变量,作用是获取某个变量的“引用”,即给某一个变量起一个别名。
定义数组 int a[2024][3][16]={2,0,2,4,3,1,6} ,则 cout << a[2023][2][15] 的结果不确定。( )
画布裁剪
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 在高为 h 宽为 w 的矩形画布上绘制了一幅画。由于画布边缘留白太多,小 A 想适当地裁剪画布,只保留画的主体。
具体来说,画布可以视为 h 行 w 列的字符矩阵,其中的字符均为 ASCII 码位于 33~126 之间的可见字符,小 A只保留画布中由第 x1 行到第 x2 行、第 y1 列到第 y2 列构成的子矩阵。
小 A 将画布交给了你,你能帮他完成画布的裁剪吗?
【输入描述】
第一行,两个正整数 h、w,分别表示画布的行数与列数。
第二行,四个正整数 x1、x2、y1、y2,表示保留的行列边界。
接下来 h 行,每行一个长度为 w 的字符串,表示画布内容。
【输出描述】
输出共 x2 - x1 + 1 行,每行一个长度为 y2 - y1 + 1 的字符串,表示裁剪后的画布。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于所有测试点,保证 1 <= h、w <= 100,1 <= x1 <= x2 <= h,1 <= y1 <= y2 <= w。
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
string s[105];
int x1, x2, y1, y2;
int main() {
cin >> n >> m >> x1 >> x2 >> y1 >> y2;
for (int i = 0; i < n; i++)
cin >> s[i];
for (int i = x1 - 1; i < x2; i++) {
string s1 = s[i].substr(y1 - 1, y2 - y1 + 1);
cout << s[i].substr(y1 - 1, y2 - y1 + 1) << endl;
}
return 0;
}排序
时间限制:1 s,内存限制:512 MB
【问题描述】
体育课上有 n 名同学排成一队,从前往后数第 i 位同学的身高为 hi,体重为 wi。
目前排成的队伍看起来参差不齐,老师希望同学们能按照身高从高到低的顺序排队,如果身高相同则按照体重从重到轻排序。
在调整队伍时,每次只能交换相邻两位同学的位置。老师想知道,最少需要多少次交换操作,才能将队伍调整成目标顺序。
【输入描述】
第一行,一个正整数 n,表示队伍人数。
接下来 n 行,每行两个正整数 hi 和 wi,分别表示第 i 位同学的身高和体重。
【输出描述】
输出一行,一个整数,表示最少需要的交换次数。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于所有测试点,保证 1 <= n <= 3000,0 <= hi、wi<= 10^9。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, ans = 0;
cin >> n;
vector<pair<int,int>> a(n);
for (int i = 0; i < n; i ++)
cin >> a[i].first >> a[i].second;
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
if (a[i] < a[j])
ans ++;
cout << ans << '\n';
return 0;
}字符排序
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 个仅包含小写字母的字符串 s1,s2,...,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t 。小杨希望最后构成的字符串 满足:
假设 ti为字符串 t 的第 i 个字符,对于所有的 j<i 均有 tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如e<g<p<s。
小杨想知道是否存在满足条件的字符串排列顺序。
输入格式
第一行包含一个正整数 T TT,代表测试数据组数。
对于每组测试数据,第一行包含一个正整数 n ,含义如题面所示。
之后 n 行,每行包含一个字符串 si。
输出格式
对于每组测试数据,如果存在满足条件的排列顺序,输出 1,否则输出 0。
输入样例
输出样例
样例解释
对于第一组测试数据,一种可行的排列顺序为 aa+ac+de,构成的字符串 t 为 aaacde,满足条件。
对于全部数据,保证有 1≤t,n≤100,每个字符串的长度不超过 10。
#include<bits/stdc++.h>
using namespace std;
string s[110];
void bubble_sort(string *a, int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
string t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
bubble_sort(s, n);
string t="";
for(int i=1;i<=n;i++){
t+=s[i];
}
int m = t.size();
int fl=1;
for(int i=1;i<m;i++){
if(t[i]<t[i-1]){
fl=0;
break;
}
}
cout<<fl<<"\n";
}
}小杨的字典
时间限制:1.0 s
内存限制:128.0 MB
问题描述
在遥远的星球,有两个国家 A 国和 B 国,他们使用着不同的语言:A 语言和 B 语言。小杨是 B 国的翻译官,他的工作是将 A 语言的文章翻译成 B 语言的文章。
为了顺利完成工作,小杨制作了一本字典,里面记录了 个 A 语言单词对应的 B 语言单词,巧合的是,这些单词都由地球上的 26 个小写英文字母组成。
小杨希望你写一个程序,帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号 !()-[]{}\|;:'",./?<> 和一些 A 语言单词构成,每个单词之间必定由至少一个标点符号分割,你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地,如果遇到不在字典中的单词,请使用大写 UNK 来替换它。
例如,小杨的字典中包含 2 个 A 语言单词 abc 和 d ,它们的 B 语言翻译分别为 a 和 def ,那么我们可以把 A语言文章 abc.d.d.abc.abcd. 翻译成 B 语言文章 a.def.def.a.UNK. ,其中,单词 abcd 不在词典内,因此我们需要使用 UNK 来替换它。
输入描述
第一行一个整数N,表示词典中的条目数。保证N≤100。
接下来 行,每行两个用单个空格隔开的字符串A,B,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有A不重复;保证A和B的长度不超过10。
最后一行一个字符串S,表示需要翻译的 A 语言文章。保证字符串 的长度不超过1000,保证字符串S只包含小写字母以及标点符号 !()-[]{}\|;:'",./?<> 。
输出描述
输出一行,表示翻译后的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例输入 2
样例输出 2
样例输入 3
样例输出 3
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string, string> dict;
int main() {
int N;
cin >> N;
while (N--) {
string word1, word2;
cin >> word1 >> word2;
dict[word1] = word2;
}
string content, word = "";
cin >> content, content += "\n";
int m = content.length();
for (int i = 0; i < m; i++) {
if (content[i] >= 'a' && content[i] <= 'z')
word += content[i];
else {
if (word != "") {
if (dict.count(word))
cout << dict[word];
else
cout << "UNK";
word = "";
}
cout << content[i];
}
}
return 0;
}