C++ 程序设计 OJ4 - 参考答案 MASTER 2019 年 月 30 日 1
1 STRINGSORT 1 StringSort 题目描述 编写程序, 利用 string 类完成一个字符串中字符的排序 ( 降序 ) 并输出 输入描述 输入仅一行, 是一个仅由大小写字母和数字组成的字符串 输出描述 输出排序后的字符串 样例输入 abcde 样例输出 edcba 提示 使用 std::sort 第三个参数是比较函数, 本题类似 bool Compare(char fisrt, char second); http://en.cppreference.com/w/cpp/algorithm/sort 2
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 } 10 11 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
2 STRINGSSORT 2 StringsSort 描述 编写程序, 利用 vector 容器输入若干个 string 类数据元素, 将其排序后输出 输入 输入的第一行是一个正整数 N, 表示接下来的字符串的个数 输出 将输入的字符串 ( 按字典序 ) 排序后输出, 每行一个 样例输入 4 C++ ACM BJFU Object 样例输出 ACM BJFU C++ Objec 提示 4
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 } 19 20 s o r t ( vstring. begin ( ), vstring. end ( ) ) ; 21 22 f o r ( i n t i =0; i<n ; i++) 23 { 24 cout << vstring [ i ] << endl ; 2 } 26 27 return 0 ; 28 }
3 SIMPLELIST 3 SimpleList 描述 编写程序, 定义一个结构体 struct Student{ int no; string name; }; 并用这个结构体练习使用 list 包含往 list 里添加元素以及输出 list 的所有元素 输入 第一行一个整数 n, 表示共有 n 个学生信息接下来 n 行, 每行是一个整数和一个字符串, 分别表示学生的学号和姓名 输出 按顺序输出 list 中的所有元素, 每个元素占一行 样例输入 3 1010101 zhangsan 1010102 lisi 1010103 wangwu 样例输出 1010101, zhangsan 1010102, lisi 1010103, wangwu 6
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 } ; 10 11 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 } 23 24 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 } 30 31 return 0 ; 32 } 7
4 CARDGAME 4 CardGame 题目描述 桌上有一叠牌, 从第一张牌 ( 即位于顶面的牌 ) 开始从上往下依次编号为 1~n 当至少还剩两张牌时进行以下操作 : 把第一张牌扔掉, 然后把新的第一张放到整叠牌的最后 请模拟这个过程, 依次输出每次扔掉的牌以及最后剩下的牌的编号 输入 输入正整数 n(n<1000000) 输出 在一行内依次输出每次扔掉的牌以及最后剩下的牌的编号, 每个编号后跟一个空格 ( 所有输出最后加一个按行符 ) 样例输入 7 样例输出 1 3 7 4 2 6 提示 可以用 std::queue 实现 8
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 ) ; 12 13 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
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 格式详见样例 样例输入 4 1 2 3 1 2 1 3 3 3 1 2 3 样例输出 found at 4 2 not found 3 found at 3 提示 可以直接使用 algorithm 头文件中的 sort 和 lower_bound 函数, 后者的功能是查找大于等于 x 的第一个位置, 原型自己查 10
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 ( ) ) ; 19 20 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