【第二章】算法竞赛入门经典(第二版)-课后习题答案.pdf

算法竞赛入门经典 第二版 第二章 课后习题答案 这是一些能解决问题的代码 3 1 Score 3 2 Molar Mass 3 3 Digit Counting 3 4 Periodic Strings 3 5 Puzzle 3 6 Crossword Answers 3 7 DNA Consensus String 3 8 Repeating Decimals 3 9 All in All 3 10 Box 3 11 Kickdown 3 12 Floating Point Numbers Chapter 3 2017年10月1日 14 59 第 1 页 ACM ICPC Seoul 2005 UVa1585 1 include 2 include 3 using namespace std 4 int main void 5 6 int a 7 cin a 8 while a 9 10 11 string s 12 cin s 13 int n s size 14 int num 0 ans 0 15 for int i 0 i n i 16 17 if s i O 18 num 19 else 20 21 for int j 1 j num j 22 ans j 23 num 0 24 25 26 for int j 1 j num j 27 ans j 28 cout ans endl 29 a 30 31 return 0 32 3 1 Score 2017年10月1日 15 00 第 2 页 ACM ICPC Seoul 2007 UVa1586 1 include 2 include 3 include 4 include 5 using namespace std 6 const double Mass 0 0 12 01 0 0 0 0 1 008 0 0 0 0 0 14 01 16 00 7 int main void 8 9 int n 10 cin n 11 while n 12 13 string s 14 double ans 0 15 cin s 16 for int i 0 i s size i 17 18 int num 19 if isupper s i 20 21 if isdigit s i 1 22 23 num s i 1 0 24 for int j i 2 j s size j 25 num num 10 s j 0 26 ans num Mass s i A 27 28 else 29 ans Mass s i A 30 31 32 cout setiosflags ios fixed setprecision 3 ans endl 33 n 34 35 return 0 36 3 2 Molar Mass 2017年10月1日 15 04 第 3 页 ACM ICPC Danang 2007 UVa1225 1 include 2 include 3 using namespace std 4 int main void 5 6 int num 7 cin num 8 while num 9 10 int s 10 11 memset s 0 sizeof s 12 int n LS 13 cin n 14 for int i 1 i n i 15 16 int LS2 i 17 while LS2 18 19 LS LS2 10 20 s LS 21 LS2 10 22 23 24 for int i 0 i 9 i 25 cout s i 26 cout s 9 endl 27 num 28 29 return 0 30 3 3 Digit Counting 2017年10月1日 15 06 第 4 页 UVa455 1 include 2 include 3 using namespace std 4 int next1 80 5 void GetNext int n const char s 获取Next数组 预处理 6 int i 0 k 1 表示字符长度 位置 7 memset next1 0 sizeof next1 8 next1 0 1 字符串的前缀和后缀最大公共长度 9 while i num 25 while num 26 27 bool out true 28 char s 80 29 cin s 30 int n strlen s 31 GetNext n s 32 33 GetNext成功获取 34 35 for int i 0 i n i 36 cout next1 i 37 cout endl 38 39 if n n next1 n 0 41 else 42 cout n 1 44 cout endl 45 num 46 47 3 4 Periodic Strings 2017年10月1日 15 07 第 5 页 47 return 0 48 第 6 页 ACM ICPC World Finals 1993 UVa227 1 include 2 include 3 include 4 define maxn 5 5 using namespace std 6 bool check int x int y int n 7 switch n 8 9 case 1 10 if x 0 11 return false 12 else 13 return true 14 break 15 case 2 16 if x 4 17 return false 18 else 19 return true 20 break 21 case 3 22 if y 4 23 return false 24 else 25 return true 26 break 27 case 4 28 if y 0 29 return false 30 else 31 return true 32 break 33 34 35 int main void 36 37 int kase 0 38 while 1 39 40 char s maxn maxn 41 42 for int i 0 i 5 i 43 for int j 0 j 5 j 44 45 s i j getchar 46 if s 0 0 Z 47 return 0 48 if s i j n 49 j 50 51 52 3 5 Puzzle 2017年10月1日 15 08 第 7 页 52 53 成功读入数组 54 55 cout endl 56 for int i 0 i 5 i 57 58 for int j 0 j 5 j 59 cout s i j 60 cout endl 61 62 63 int x y 64 for int i 0 i 5 i 65 for int j 0 j 5 j 66 if s i j 67 68 x i 69 y j 70 71 cout x x y y endl 72 bool flag true 73 getchar 吃换行符 74 while 1 75 76 char ch 77 if ch getchar n 78 79 cout ch ch endl 80 if ch 0 81 break 82 else if ch A 85 s x 1 y 86 x 87 88 else if ch B 91 s x 1 y 92 x 93 94 else if ch R 97 s x y 1 98 y 99 100 else if ch L 103 s x y 1 104 y 105 106 else 107 flag 第 8 页 107 flag false 108 109 110 cout endl 111 if kase 输出格式注意 112 cout endl 113 cout Puzzle kase endl 114 115 if flag 116 117 118 bool first true 119 for int i 0 i 5 i 120 121 for int j 0 j 5 j 122 123 if first 124 125 cout s i j 126 first 0 127 128 else 129 cout s i j 130 131 first true 132 cout endl 133 134 135 else 136 cout This puzzle has no final configuration endl 137 138 139 return 0 140 第 9 页 ACM ICPC World Finals 1994 UVa232 1 include 2 include 3 include 4 define maxn 15 5 char s maxn maxn 6 int start num maxn maxn 7 using namespace std 8 int Across int i int j int c 9 if start num i j 0 10 11 if start num i j 10 3d 12 cout start num i j 13 else 14 cout start num i j 15 for j j c j 16 17 if s i j 18 19 cout endl 20 return j 21 22 else 23 cout s i j 24 25 cout endl 26 return j 27 28 return j 29 30 31 int Down int i int j int r 32 if start num i j 0 33 34 if start num i j 10 35 cout start num i j 36 else 37 cout start num i j 38 for i i r i 39 40 if s i j 41 42 cout endl 43 return 0 44 45 else 46 47 cout 3 6 Crossword Answers 2017年10月1日 15 09 第 10 页 47 cout s i j 48 start num i j 0 49 50 51 cout r 62 if r 0 63 return 0 64 cin c 65 for int i 0 i r i 66 scanf s 67 68 Read in 69 70 for int i 0 i r i 71 72 for int j 0 j c j 73 cout s i j 74 cout endl 75 76 77 78 int num 0 79 memset start num 0 sizeof start num 80 81 the first number 82 for int i 0 i r i 83 for int j 0 j c j 84 85 if s i j 86 87 if i 0 j 0 88 start num i j num 89 else if s i j 1 s i 1 j 90 start num i j num 91 92 93 94 check the first number 95 96 for int i 0 i r i 97 98 for int j 0 j c j 99 cout start num i j 第 11 页 99 cout start num i j 100 cout endl 101 102 103 if kase 104 cout endl 105 cout puzzle kase endl 106 107 cout Across endl 108 for int i 0 i r i 109 for int j 0 j c j 110 j Across i j c 111 112 cout Down endl 113 for int i 0 i r i 114 for int j 0 j c j 115 Down i j r 116 117 118 return 0 119 第 12 页 ACM ICPC Seoul 2006 UVa1368 1 include 2 include 3 include 4 using namespace std 5 int main void 6 7 int num 8 int Hamans 0 9 cin num 10 while num 11 12 int m n 13 cin m n 14 char s m n 15 for int i 0 i s i 17 18 数组正确读入 19 20 for int i 0 i m i 21 22 for int j 0 j n j 23 cout s i j 24 cout endl 25 26 27 28 int LS 0 29 int Repeat 4 30 char ans n 31 for int j 0 j n j 32 33 memset Repeat 0 sizeof Repeat 34 for int i 0 i m i 35 36 if s i j A Repeat 0 37 else if s i j C Repeat 1 38 else if s i j G Repeat 2 39 else Repeat 3 40 思路 检查Hamming距离最小的字符 若有相同的情况则再判断字典序 41 42 43 测试Repeat的数据是否正确 44 45 for int LS 0 LS 4 LS 46 cout Repeat LS 47 cout endl 48 49 int PD 0 50 LSans 3 7 DNA Consensus String 2017年10月1日 15 10 第 13 页 50 int LSans 0 51 for int LS 0 LS 4 LS 52 if PD Repeat LS 53 54 PD Repeat LS 55 LSans LS 56 57 58 Hamans m Repeat LSans 求Hamming距离的总和 59 60 测试当前最大的数组下标是否正确 61 62 cout LSans LSans endl 63 64 switch LSans 65 66 case 0 67 ans j A 68 break 69 case 1 70 ans j C 71 break 72 case 2 73 ans j G 74 break 75 case 3 76 ans j T 77 break 78 79 80 81 for int j 0 j n j 82 cout ans j 83 cout endl 84 cout Hamans endl 85 Hamans 0 清零Hamming距离以便下一次计算 86 num 87 88 return 0 89 第 14 页 ACM ICPC World Finals 1990 UVa202 1 include 2 include 3 include 4 define maxn 5000000 5 using namespace std 6 int s maxn next1 maxn YS maxn repeat maxn 7 8 void GetNext const int n 9 memset next1 0 sizeof next1 10 next1 0 1 11 int i 0 k 1 12 while i n 13 14 if k 1 repeat i repeat k 15 16 next1 i 1 k 1 17 i 18 k 19 20 else 21 k next1 k 22 23 24 25 void Next Loop int n int 27 bool flag1 true 28 for int i 0 i n i 29 30 if next1 i 1 next1 i 0 31 continue 32 j i next1 i 33 if i j 0 34 35 loop i 2 36 if YS n YS n loop 37 break 38 39 40 41 int main void 42 43 int a b 44 int YS 1 0 45 int loop 0 46 while scanf d 49 int a1 a 50 bool flag true 51 52 memset s 0 sizeof s 53 memset YS 0 sizeof YS 54 55 模拟四则运算 计算50000位 maxn较大 56 for int i 0 i b 59 s i a b 60 if a b 61 3 8 Repeating Decimals 2017年10月1日 15 12 第 15 页 61 s i 0 62 a a s i b 10 63 YS i a 64 if a 0 65 66 flag false 67 break 68 69 70 if flag 71 72 73 模拟四则运算测试输出 74 75 cout s 0 76 for int i 1 i b 3 i 77 cout s i 78 cout endl 79 80 81 从后面开始复制以避开干扰数 82 83 memset repeat 0 sizeof repeat 84 for int i 0 i 3 b 1 i 85 repeat i s i b 1 86 87 GetNext 3 b 1 88 Next Loop 3 b 1 loop 89 90 检查next数组 91 92 cout Next endl 93 for int i 0 i 50 i 94 cout next1 i 95 cout endl 96 97 98 检查周期 99 cout loop loop endl 100 101 用于排除前方干扰数的影响 使用余数 102 bool flag2 true 103 104 for int i 0 i maxn i 105 106 for int j 0 j loop j 107 if YS i YS i loop 108 flag2 false 109 if flag2 110 111 i 112 int num 0 113 cout a1 b 114 cout s 0 115 for int j 1 j i j 116 117 cout s j 118 num 119 120 cout 50 123 124 j j 第 16 页 124 for int j i j 50 num i j 125 cout s j 126 cout 127 128 else 129 for int j i j loop i j 130 cout s j 131 cout endl 132 cout loop number of digits in repeating cycle endl 133 break 134 135 flag2 true 136 137 138 整除的情况 139 else 140 141 cout a1 b 142 cout s 0 143 for int i 1 i maxn i 144 145 if YS i 1 0 146 break 147 cout s i 148 149 cout 0 endl 150 cout 1 number of digits in repeating cycle endl 151 152 cout endl 153 154 return 0 155 第 17 页 UVa 10340 1 include 2 include 3 include 4 define maxn 100000000 5 char k maxn 6 char s maxn 7 using namespace std 8 int main void 9 10 while scanf s 14 int n1 strlen k 15 int n2 strlen s 16 int num 0 17 int wz 0 18 for int j 0 j n1 j 19 for int i wz i n2 i 20 if k j s i 21 22 num 23 wz i 1 24 break 25 26 if num n1 27 cout Yes endl 28 else 29 cout No endl 30 31 return 0 32 1 include 2 include 3 include 4 include 5 define maxn 100000 6 using namespace std 7 char s1 maxn s2 maxn 8 int value2 2 maxn 9 int main void 10 11 while scanf s s 14 int i j 15 int tem 1 16 for i 0 s1 i i 17 18 for j 0 s2 j j 19 20 if s1 i s2 j 21 value2 tem j value2 1 tem j 1 1 22 else 23 value2 tem j max value2 1 tem j value2 tem j 1 状态转移方程 24 25 tem 1 tem 空间优化 26 27 if value2 1 tem j 1 strlen s1 28 cout Yes endl 29 3 9 All in All 2017年10月1日 15 14 第 18 页 29 else 30 cout No endl 31 32 return 0 33 第 19 页 ACM ICPC NEERC 2004 UVa1587 1 include 2 include 3 include 4 include 5 using namespace std 6 struct box 7 8 int x 9 int y 10 s 6 11 bool cmp const box 14 15 16 int main void 17 18 memset s 0 sizeof s 19 20 读入长宽数据 21 while scanf d d i s i x s i y 25 26 长宽定义统一 27 for int i 0 i 6 i 28 if s i x s i y 29 swap s i x s i y 30 31 bool flag true 32 33 面积排序 34 sort s s 6 cmp 35 36 排序函数正常 37 38 cout endl 39 for int i 0 i 6 i 40 cout s i x s i y endl 41 42 43 判断矩形各面是否合法 思路来源 CSDN codekun 44 巧妙之处 排序后memcmp只存在0或大于0的返回值 45 if memcmp s s 1 sizeof box memcmp s 2 s 3 sizeof box memcmp s 4 s 5 sizeof box 46 flag false 47 48 判断矩形各长宽高是否合法 49 if s 0 x s 2 x s 0 y s 4 x s 2 y s 4 y 50 flag false 51 52 输出 53 if flag 54 cout POSSIBLE endl 55 else 56 cout IMPOSSIBLE endl 57 58 return 0 59 3 10 Box 2017年10月1日 15 14 第 20 页 ACM ICPC NEERC 2006 UVa1588 1 include 2 include 3 include 4 include 5 using namespace std 6 int