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

Size: px

Start display at page:

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

棒棒宰
4 years ago
Views:

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

2 1 ANTI-PHRASE 1 Anti-phrase 题目描述输入一些单词, 找出所有满足以下条件的单词 : 该单词不能通过字母重排, 得到输入文本中的另外一些单词在判断是否满足条件时, 字母不区分大小写如单词 tied 可以通过重排得到单词 EdiT, 重排时不考虑大小写输出时应保留输入时的大小写, 并按字典序进行排列 ( 所有大写字母在所有小写字母的前面 ) 输入输入最多 20 行, 每行可能包含若干个单词, 每行最多 80 个字符每个单词最多 20 个字符, 仅由大小写字母组成单词之间用若干个空格隔开输入最后一行仅由一个字符 '#' 组成, 表示结束输入输出按要求输出单词, 一行输出一个单词样例输入 ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS dried noel dire Disk mace Rob dries # 样例输出 Disk NotE derail dried eye ladder soon 提示把每个单词标准化, 即全部转化为小写字母后再进行排序, 然后再放到 map 中进行统计 2

3 1 ANTI-PHRASE 1 // UVa156 Ananagrams 2 // Rujia Liu 3 // 题意 : 输入一些单词, 找出所有满足如下条件的单词 : 该单词不能通过字母重排得到输入文本中的另外一个单词 4 // 算法 : 把每个单词标准化, 即全部转化为小写字母然后排序, 然后放到 map 中进行统计 5 #inclu de <iostream> 6 #include<s t r i n g > 7 #inclu de <cctype> 8 #inclu de <vector> 9 #inclu de <map> 10 #inclu de <algorithm> 11 using namespace std ; map<s t r i n g, int> cnt ; 14 vector<s t r i n g > words ; // 将单词 s 进行标准化 17 s t r i n g repr ( const s t r i n g &s ) { 18 s t r i n g ans = s ; 19 f o r ( i n t i = 0 ; i < ans. length ( ) ; i++) 20 ans [ i ] = tolower ( ans [ i ] ) ; 21 s o r t ( ans. begin ( ), ans. end ( ) ) ; 22 return ans ; 23 } i n t main ( ) { 26 i n t n = 0 ; 27 s t r i n g s ; 28 while ( cin >> s ) { 29 i f ( s [ 0 ] == '#' ) break ; 30 words. push_back ( s ) ; 31 s t r i n g r = repr ( s ) ; 32 i f (! cnt. count ( r ) ) cnt [ r ] = 0 ; 33 cnt [ r ]++; 34 } 35 vector<s t r i n g > ans ; 36 f o r ( i n t i = 0 ; i < words. s i z e ( ) ; i++) 37 i f ( cnt [ repr ( words [ i ] ) ] == 1) ans. push_back ( words [ i ] ) ; 38 s o r t ( ans. begin ( ), ans. end ( ) ) ; 39 f o r ( i n t i = 0 ; i < ans. s i z e ( ) ; i++) 40 cout << ans [ i ] << "\n" ; 41 return 0 ; 42 } 3

4 2 BLOCKS 2 Blocks 题目描述从左到右有 n 个木块, 编号为 0 到 n-1, 要求模拟以下操作 (a 和 b 都是木块编号 ) move a onto b: 把木块 a b 上的木块放回各自的原位, 再把 a 放到 b 上 ; move a over b: 把 a 上的木块放回各自的原位, 再把 a 放到含 b 的堆上 ; pile a onto b: 把 b 上的木块放回各自的原位, 再把 a 连同 a 上的木块移到 b 上 ; pile a over b: 把 a 连同 a 上的木块移到含 b 的堆上 a 和 b 在同一堆的指令是非法指令, 应当忽略当输入 quit 时, 结束操作并输出 0~n-1 的位置上的木块情况, 按照从底部到顶部的顺序排列输入首先输入一个正整数 n(n <= 100), 表示木块总数接下来输入若干条指令, 输入格式见样例输入最后一行输入 "quit" 表示操作结束输出输出 n 行, 第 i 行表示编号为 i 的木块上的木块情况, 按照从底部到顶部的顺序排列, 每两个数之间一个空格, 最后一个数后面没有空格样例输入 10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit 样例输出 0: 0 1: : 3: 3 4: 5: : 7: 8: 9: 提示建议使用 STL 中的 vector 处理 4

5 2 BLOCKS 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 <vector> 4 #i n c l u d e <algorithm> 5 using namespace std ; 6 7 const i n t maxn = 30; 8 vector<int> p i l e [ maxn ] ; // 最多有 maxn 个堆, 每个堆都是一个 v e c t o r 9 i n t N; // 找到编号为 num 的堆 p 及其高度 h, 修改引用 12 void find_block ( i n t num, i n t &p, i n t &h) 13 { 14 f o r ( i n t i = 0 ; i < N; ++i ) 15 f o r ( i n t index = 0 ; index < p i l e [ i ]. s i z e ( ) ; ++index ) 16 { 17 i f ( p i l e [ i ] [ index ] == num) 18 { 19 p = i ; h = index ; 20 return ; 21 } 22 } 23 } // 把第 p 堆在高度 h 之上的木块移回原位 26 void clear_above ( i n t p, i n t h) 27 { 28 f o r ( i n t i = h+1; i < p i l e [ p ]. s i z e ( ) ; ++i ) 29 { 30 i n t x = p i l e [ p ] [ i ] ; 31 p i l e [ x ]. push_back ( x ) ; // 归位 32 } 33 p i l e [ p ]. r e s i z e (h+1) ; // 只保留下标 0~h 的元素 34 } // 把 p1 堆中高度 h1 及其之上的木块整体移动到 p2 顶部 37 void pile_upon ( i n t p1, i n t h1, i n t p2 ) 38 { 39 f o r ( i n t i = h1 ; i < p i l e [ p1 ]. s i z e ( ) ; ++i ) 40 p i l e [ p2 ]. push_back ( p i l e [ p1 ] [ i ] ) ; 41 p i l e [ p1 ]. r e s i z e ( h1 ) ; // 只保留下标 0~h 1 的元素 42 } void print_status ( ) // 打印输出 46 { 47 f o r ( i n t i = 0 ; i<n; ++i ) 48 { 49 p r i n t f ( "%d:", i ) ; 5

6 2 BLOCKS 50 f o r ( i n t j = 0 ; j < p i l e [ i ]. s i z e ( ) ; ++j ) 51 p r i n t f ( " %d", p i l e [ i ] [ j ] ) ; 52 p r i n t f ( "\n" ) ; 53 } 54 } i n t main ( ) 57 { 58 cin >> N; 59 s t r i n g s1, s2 ; 60 i n t a, b ; 61 f o r ( i n t i = 0 ; i<n; ++i ) p i l e [ i ]. push_back ( i ) ; // 堆初始化 62 while ( cin >> s1 >> a >> s2 >> b) 63 { 64 i n t pa, pb, ha, hb ; 65 find_block ( a, pa, ha ) ; // 找到数字 a 66 find_block (b, pb, hb) ; // 找到数字 b 67 i f ( pa == pb) continue ; // 非法指令 // 合并后的 3 句话操作 70 i f ( s1 == "move" ) // 要 move a 一定会归位 a 上面的木块 71 clear_above ( pa, ha ) ; 72 i f ( s2 == "onto" ) // 要 onto b 一定会归位 b 上面的木块 73 clear_above (pb, hb) ; 74 pile_upon ( pa, ha, pb) ; // 把 a 及其之上的木块移到 b 堆上 /* 合并前 77 i f ( s1 == move && s2 == onto ) 78 { 79 clear_above ( pa, ha ) ; 80 clear_above ( pb, hb ) ; 81 p i l e [ pb ]. push_back ( a ) ; 82 p i l e [ pa ]. pop_back () ; 83 } 84 e l s e i f ( s1 == move && s2 == over ) 85 { 86 clear_above ( pa, ha ) ; 87 p i l e [ pb ]. push_back ( a ) ; 88 p i l e [ pa ]. pop_back () ; 89 } 90 e l s e i f ( s1 == p i l e && s2 == onto ) 91 { 92 clear_above ( pb, hb ) ; 93 pile_upon ( pa, ha, pb ) ; 94 } 95 e l s e i f ( s1 == p i l e && s2 == over ) 96 pile_upon ( pa, ha, pb ) ; 97 */ 98 // p r i n t _ s t a t u s () ;// 观察每一次移动 6

7 2 BLOCKS 99 } 100 print_status ( ) ; 101 return 0 ; 102 } 7

8 3 WORDS 3 Words 题目描述输入一个文本, 找出所有不同的单词 ( 连续的字母序列 ), 按字典序从小到大输出单词比较时不考虑大小写, 输出时统一输出全部小写的单词输入输入最多 100 行, 每行最多输入 100 个字符输出按字典序从小到大输出所有不同的单词样例输入 Adventures in Disneyland Two blondes were going to Disneyland when they came to a fork in the road. The sign read: "Disneyland Left." So they went home. 样例输出 a adventures blondes came disneyland fork going home in left read road sign so the they to two went were when 提示建议使用 STL 中的 set 进行处理 8

9 3 WORDS 1 // UVa10815 Andy s F i r s t Dictionary 2 // Rujia Liu 3 // 题意 : 输入一个文本, 找出所有不同的单词 ( 连续字母序列 ), 按字典序从小到大输出单词不分大小写 4 #inclu de <iostream> 5 #include<s t r i n g > 6 #include<set> 7 #inclu de <sstream> 8 using namespace std ; 9 10 i n t main ( ) 11 { 12 set<s t r i n g > d i c t ; 13 s t r i n g s, buf ; 14 while ( cin >> s ) 15 { 16 f o r ( i n t i = 0 ; i < s. length ( ) ; i++) 17 i f ( i s a l p h a ( s [ i ] ) ) s [ i ] = tolower ( s [ i ] ) ; e l s e s [ i ] = ' ' ; 18 stringstream s s ( s ) ; 19 while ( s s >> buf ) d i c t. i n s e r t ( buf ) ; 20 } 21 f o r ( set<s t r i n g >:: i t e r a t o r i t = d i c t. begin ( ) ; i t!= d i c t. end ( ) ; ++i t ) 22 cout << * i t << "\n" ; 23 return 0 ; 24 } 9

10 4 UGLYNUMBER 4 UglyNumber 题目描述丑数是指不能被 2,3,5 以外的其他素数整除的数 ( 即因子中, 只包含 2,3,5) 把丑数从小到大排列起来, 结果如下 : 1,2,3,4,5,6,8,9,10,12,15, 输入输入有多组, 每组输入一个 n(n<=10000) 输出输出第 n 个丑数, 以换行结尾样例输入 1500 样例输出提示从小到大生成各个丑数最小的丑数是 1, 对于任意丑数 x,2x,3x 和 5x 也是丑数下一个最小的丑数在 2m, 3n, 5k(m,n,k 为整数 ) 中产生可以使用 priority_queue, 每次取最小的丑数 10

11 4 UGLYNUMBER 1 #inclu de <iostream> 2 #inclu de <vector> 3 #inclu de <queue> 4 #include<set> 5 #inclu de <algorithm> 6 using namespace std ; 7 8 typedef long long LL ; 9 const i n t c o e f f [ 3 ] = { 2,3,5 } ; LL UglyNumber ( ) 13 { unsigned long long i n t N[ ] ; N[ 1 ] = 1 ; i n t p2 = 1, p3 = 1, p5 = 1 ; f o r ( i n t n = 2 ; n <= 1500; n++) { while (N[ p2 ] * 2 <= N[ n 1 ] ) p2++; while (N[ p3 ] * 3 <= N[ n 1 ] ) p3++; while (N[ p5 ] * 5 <= N[ n 1 ] ) p5++; N[ n ] = min(n[ p2 ] * 2, min(n[ p3 ] * 3, N[ p5 ] * 5) ) ; } 32 return 0 ; 33 } s t r u c t cmp { 36 bool operator ( ) (LL a, LL b) { 37 return a > b ; 38 } 39 } ; i n t main ( ) 42 { // priority_queue<ll, vector<ll>, greater <LL> > pq ;// 优先队列 45 priority_queue<ll, vector<ll>, cmp > pq ; // 优先队列 46 set<ll> s ; // 集合 47 pq. push (1) ; 48 s. i n s e r t (1) ; 49 i n t N; 11

12 4 UGLYNUMBER 50 cin >> N; 51 f o r ( i n t i = 1 ; ; i++) 52 { 53 LL x = pq. top ( ) ; 54 pq. pop ( ) ; 55 i f ( i == N) 56 { 57 cout << x << "\n" ; 58 break ; 59 } 60 f o r ( i n t j = 0 ; j < 3 ; j++) 61 { 62 LL x2 = x* c o e f f [ j ] ; 63 i f (! s. count ( x2 ) ) { 64 s. i n s e r t ( x2 ) ; 65 pq. push ( x2 ) ; 66 } 67 } 68 } 69 return 0 ; 70 } 12

13 5 TRACK 5 Track 题目描述某城市有一个火车站, 铁轨铺设如图所示有 n 节车厢从 A 方向驶入车站, 按进站顺序编号为 1~n. 你的任务是让它们按照某种特定的顺序进入 B 方向的铁轨并驶出车站为了重组车厢, 你可以借助中转站 C 这是一个可以停放任意多节车厢的车站, 但由于末端封顶, 驶入 C 的车厢必须按照相反的顺序驶出 C 对于每个车厢, 一旦从 A 移入 C, 就不能再回到 A 了 ; 一旦从 C 移入 B, 就不能回到 C 了换句话说, 在任一时刻, 只有两种选择 :A->C 和 C->B 输入输入包含多组测试数据, 每组数据的第一行是一个正整数 n(1<n<1000), 第二行是 1~n 这 n 个整数的一个全排列输出对于每一组测试数据, 如果能按要求完成车厢重组, 请输出 Yes, 否则输出 No, 每组输出占一行样例输入样例输出 Yes No Yes 提示可以使用 stack 实现 13

14 5 TRACK 1 #i n c l u d e <iostream> 2 #i n c l u d e <stack> 3 #i n c l u d e <vector> 4 using namespace std ; 5 6 i n t main ( ) 7 { 8 i n t n ; 9 while ( cin >> n) 10 { 11 stack<int > c ; 12 vector<int > a, b ; 13 i n t temp ; 14 f o r ( i n t i = 0 ; i < n ; ++i ) 15 { 16 cin >> temp ; 17 b. push_back (temp) ; 18 a. push_back ( i + 1) ; 19 } 20 i n t i = 0, j = 0 ; 21 while ( i!= n) 22 { 23 c. push ( a [ i ++]) ; 24 while (! c. empty ( ) && c. top ( ) == b [ j ] ) 25 { 26 c. pop ( ) ; 27 j++; 28 } } 31 i f ( c. empty ( ) ) 32 cout << " Yes" << endl ; 33 e l s e 34 cout << "No" << endl ; 35 } 36 return 0 ; 37 } 14

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,