C++ 程序设计 OJ4 - 参考答案 MASTER 2019 年 5 月 30 日 1

Size: px

Start display at page:

Download "C++ 程序设计 OJ4 - 参考答案 MASTER 2019 年 5 月 30 日 1"

从齐谈
5 years ago
Views:

1 C++ 程序设计 OJ4 - 参考答案 MASTER 2019 年月 30 日 1

2 1 STRINGSORT 1 StringSort 题目描述编写程序, 利用 string 类完成一个字符串中字符的排序 ( 降序 ) 并输出输入描述输入仅一行, 是一个仅由大小写字母和数字组成的字符串输出描述输出排序后的字符串样例输入 abcde 样例输出 edcba 提示使用 std::sort 第三个参数是比较函数, 本题类似 bool Compare(char fisrt, char second); 2

3 1 STRINGSORT 1 #i n c l u d e <iostream> 2 #i n c l u d e <s t r i n g > 3 #i n c l u d e <algorithm> 4 using namespace std ; 6 bool Compare( char a, char b) 7 { 8 return a > b ; 9 } i n t main ( ) 12 { 13 s t r i n g s t r ; 14 cin >> s t r ; 1 s o r t ( s t r. begin ( ), s t r. end ( ), Compare) ; 16 cout << s t r ; 17 return 0 ; 18 } 3

4 2 STRINGSSORT 2 StringsSort 描述编写程序, 利用 vector 容器输入若干个 string 类数据元素, 将其排序后输出输入输入的第一行是一个正整数 N, 表示接下来的字符串的个数输出将输入的字符串 ( 按字典序 ) 排序后输出, 每行一个样例输入 4 C++ ACM BJFU Object 样例输出 ACM BJFU C++ Objec 提示 4

5 2 STRINGSSORT 1 #inclu de <iostream> 2 #inclu de <vector> 3 #include<s t r i n g > 4 #i n c l u d e <algorithm> 6 using namespace std ; 7 8 i n t main ( ) 9 { 10 vector<s t r i n g > vstring ; 11 i n t n ; 12 cin >> n ; 13 f o r ( i n t i =0; i<n ; i++) 14 { 1 s t r i n g s t r ; 16 cin >> s t r ; 17 vstring. push_back ( s t r ) ; 18 } s o r t ( vstring. begin ( ), vstring. end ( ) ) ; f o r ( i n t i =0; i<n ; i++) 23 { 24 cout << vstring [ i ] << endl ; 2 } return 0 ; 28 }

6 3 SIMPLELIST 3 SimpleList 描述编写程序, 定义一个结构体 struct Student{ int no; string name; }; 并用这个结构体练习使用 list 包含往 list 里添加元素以及输出 list 的所有元素输入第一行一个整数 n, 表示共有 n 个学生信息接下来 n 行, 每行是一个整数和一个字符串, 分别表示学生的学号和姓名输出按顺序输出 list 中的所有元素, 每个元素占一行样例输入 zhangsan lisi wangwu 样例输出 , zhangsan , lisi , wangwu 6

7 3 SIMPLELIST 1 #inclu de <iostream> 2 #include<l i s t > 3 #include<s t r i n g > 4 using namespace std ; 6 s t r u c t Student { 7 i n t no ; 8 s t r i n g name ; 9 } ; i n t main ( ) 12 { 13 l i s t <Student> l i ; 14 1 i n t num; 16 cin >> num; 17 f o r ( i n t i =0; i<num; i++) 18 { 19 Student stu ; 20 cin >> stu. no >> stu. name ; 21 l i. push_back ( stu ) ; 22 } l i s t <Student >:: i t e r a t o r i t r ; 2 f o r ( i t r=l i. begin ( ) ; i t r!= l i. end ( ) ; i t r ++) 26 { 27 Student stu = * i t r ; // 类似指针, 取指向的值要用 * 操作 28 cout << stu. no << ", " << stu. name << endl ; 29 } return 0 ; 32 } 7

8 4 CARDGAME 4 CardGame 题目描述桌上有一叠牌, 从第一张牌 ( 即位于顶面的牌 ) 开始从上往下依次编号为 1~n 当至少还剩两张牌时进行以下操作 : 把第一张牌扔掉, 然后把新的第一张放到整叠牌的最后请模拟这个过程, 依次输出每次扔掉的牌以及最后剩下的牌的编号输入输入正整数 n(n< ) 输出在一行内依次输出每次扔掉的牌以及最后剩下的牌的编号, 每个编号后跟一个空格 ( 所有输出最后加一个按行符 ) 样例输入 7 样例输出提示可以用 std::queue 实现 8

9 4 CARDGAME 1 #i n c l u d e <iostream> 2 #i n c l u d e <queue> 3 using namespace std ; 4 i n t main ( ) 6 { 7 queue<int > q ; 8 i n t n ; 9 cin >> n ; 10 f o r ( i n t i = 1 ; i <= n ; ++i ) 11 q. push ( i ) ; while ( q. s i z e ( ) >= 2) 14 { 1 cout << q. f r o n t ( ) << ' ' ; 16 q. pop ( ) ; 17 q. push ( q. f r o n t ( ) ) ; 18 q. pop ( ) ; 19 } 20 cout << q. f r o n t ( ) << ' ' << endl ; 21 return 0 ; 22 } 9

10 MARBLE marble 描述现有 N 个大理石, 每个大理石上写了一个非负整数首先对这些整数从小到大排序, 然后回答 Q 个问题每个问题问是否有一个大理石写着某个整数 x, 如果是, 就回答哪个大理石上写着 x( 如果有多个大理石上出现 x, 那么回答第一次出现的大理石编号 ) 排序后的大理石从左到右编号为 1~N 输入输入包含多组测试数据, 每组数据分三行第一行是两个正整数 N(N<1000) 和 Q(Q<1000) 第二行是 N 个非负整数第三行是 Q 个非负整数输出对于每一个询问 (x), 如果有第 i 个大理石上写着 x, 则输出 x found at i, 否则输出 x not found 格式详见样例样例输入样例输出 found at 4 2 not found 3 found at 3 提示可以直接使用 algorithm 头文件中的 sort 和 lower_bound 函数, 后者的功能是查找大于等于 x 的第一个位置, 原型自己查 10

11 MARBLE 1 #i n c l u d e <iostream> 2 #i n c l u d e <vector> 3 #i n c l u d e <algorithm> 4 using namespace std ; 6 i n t main ( ) 7 { 8 i n t N, Q; 9 while ( cin >> N >> Q) 10 { 11 vector<int > vmarbles ; 12 i n t temp ; 13 while (N ) 14 { 1 cin >> temp ; 16 vmarbles. push_back ( temp) ; 17 } 18 s o r t ( vmarbles. begin ( ), vmarbles. end ( ) ) ; while (Q ) 21 { 22 i n t x ; 23 cin >> x ; 24 i n t p = lower_bound ( vmarbles. begin ( ), vmarbles. end ( ), x ) vmarbles. begin ( ) ; // 在非递减序列 [ First, Last ) 中找到第一个大于等于 x 的位置, 注意用法 2 i f ( vmarbles [ p ] == x ) 26 cout << x << " found at " << p + 1 << endl ; 27 e l s e 28 cout << x << " not found " << endl ; 29 } 30 } 31 return 0 ; 32 } 11

C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1

C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1 1 CARDGAME 1 CardGame 题目描述桌上有一叠牌, 从第一张牌 ( 即位于顶面的牌 ) 开始从上往下依次编号为 1~n 当至少还剩两张牌时进行以下操作 : 把第一张牌扔掉, 然后把新的第一张放到整叠牌的最后请模拟这个过程, 依次输出每次扔掉的牌以及最后剩下的牌的编号输入输入正整数 n(n