第1章 ACM 程序设计简介………………………………………………………………… 1
1.1 ACM 国际大学生程序设计竞赛……………………………………………………… 1
1.1.1 历史和背景……………………………………………………………………… 1
1.1.2 竞赛组织和竞赛规则…………………………………………………………… 1
1.2 在线评测系统简介……………………………………………………………………… 2
1.3 浙江省大学生程序设计竞赛…………………………………………………………… 2
1.4 浙江大学ACM 在线评测系统………………………………………………………… 3
1.4.1 注册和登录……………………………………………………………………… 3
1.4.2 【Problems】菜单项……………………………………………………………… 4
1.4.3 【Contests】菜单项……………………………………………………………… 5
1.4.4 【Home】菜单项………………………………………………………………… 5
1.5 在线评测的详细实施过程……………………………………………………………… 6
1.5.1 编程语言、集成开发环境和编译器的选择…………………………………… 6
1.5.2 如何选择一个题目……………………………………………………………… 7
1.5.3 ZOJ1001-A+BProblem和题目的组成结构描述…………………………… 9
1.5.4 ZOJ1001-A+BProblem汉语翻译………………………………………… 11
1.5.5 ZOJ1001-A+BProblem用C语言实现的程序代码……………………… 11
1.5.6 主函数的基本结构…………………………………………………………… 12
1.5.7 由Ctrl+Z控制的循环测试………………………………………………… 12
1.5.8 由Ctrl+Z处理的一类ACM 题目的基本结构…………………………… 14
1.5.9 本地测试……………………………………………………………………… 15
1.5.10 提交程序代码并查询评测结果……………………………………………… 17
1.5.11 评测状态详述………………………………………………………………… 19
第2章 基础题………………………………………………………………………………… 23
2.1 ZOJ2736-Daffodilnumber ………………………………………………………… 23
2.1.1 题目内容……………………………………………………………………… 23
2.1.2 汉语翻译……………………………………………………………………… 23
2.1.3 算法分析(一)………………………………………………………………… 24
2.1.4 参考代码(一)………………………………………………………………… 25
·4 · C语言程序设计进阶(ACM 实践)
2.1.5 运算符‘/’、‘%’在求整数上各位数字的应用……………………………… 26
2.1.6 算法分析(二)………………………………………………………………… 30
2.1.7 参考代码(二)………………………………………………………………… 32
2.1.8 函数scanf()、getchar()控制字符变量的输入……………………………… 32
2.2 ZOJ3333-GuessthePrice …………………………………………………………… 35
2.2.1 题目内容……………………………………………………………………… 35
2.2.2 汉语翻译……………………………………………………………………… 35
2.2.3 算法分析……………………………………………………………………… 36
2.2.4 参考代码……………………………………………………………………… 37
2.2.5 固定T个测试例子的循环控制……………………………………………… 37
2.3 ZOJ3322-WhoisOlder ……………………………………………………………… 39
2.3.1 题目内容……………………………………………………………………… 39
2.3.2 汉语翻译……………………………………………………………………… 39
2.3.3 算法分析(一)………………………………………………………………… 39
2.3.4 参考代码(一)………………………………………………………………… 41
2.3.5 多分支选择结构与if-else语句……………………………………………… 42
2.3.6 算法分析(二)………………………………………………………………… 48
2.3.7 参考代码(二)………………………………………………………………… 49
2.3.8 算法分析(三)………………………………………………………………… 50
2.3.9 参考代码(三)………………………………………………………………… 51
2.4 ZOJ3487-OrdinalNumbers ………………………………………………………… 52
2.4.1 题目内容……………………………………………………………………… 52
2.4.2 汉语翻译……………………………………………………………………… 52
2.4.3 算法分析……………………………………………………………………… 53
2.4.4 参考代码……………………………………………………………………… 54
2.5 ZOJ3191-StrangeClock……………………………………………………………… 55
2.5.1 题目内容……………………………………………………………………… 55
2.5.2 汉语翻译……………………………………………………………………… 56
2.5.3 算法分析(一)………………………………………………………………… 56
2.5.4 参考代码(一)………………………………………………………………… 58
2.5.5 算法分析(二)………………………………………………………………… 59
2.5.6 参考代码(二)………………………………………………………………… 61
2.5.7 由测试例子的特殊数据控制的循环测试…………………………………… 61
2.6 ZOJ1904-Beavergnaw………………………………………………………………… 63
2.6.1 题目内容……………………………………………………………………… 63
2.6.2 汉语翻译……………………………………………………………………… 64
2.6.3 算法分析……………………………………………………………………… 65
2.6.4 参考代码……………………………………………………………………… 67
目 录 ·5 ·
2.7 ZOJ3202-Second-priceAuction……………………………………………………… 68
2.7.1 题目内容……………………………………………………………………… 68
2.7.2 汉语翻译……………………………………………………………………… 68
2.7.3 算法分析(一)………………………………………………………………… 69
2.7.4 参考代码(一)………………………………………………………………… 73
2.7.5 算法分析(二)………………………………………………………………… 74
2.7.6 参考代码(二)………………………………………………………………… 76
2.8 ZOJ2857-ImageTransformation …………………………………………………… 77
2.8.1 题目内容……………………………………………………………………… 77
2.8.2 汉语翻译……………………………………………………………………… 78
2.8.3 算法分析……………………………………………………………………… 79
2.8.4 参考代码……………………………………………………………………… 80
2.8.5 测试例子中的数组定义……………………………………………………… 82
2.9 ZOJ3323-SomaliPirates …………………………………………………………… 84
2.9.1 题目内容……………………………………………………………………… 84
2.9.2 汉语翻译……………………………………………………………………… 85
2.9.3 算法分析(一)………………………………………………………………… 85
2.9.4 参考代码(一)………………………………………………………………… 88
2.9.5 算法分析(二)………………………………………………………………… 88
2.9.6 参考代码(二)………………………………………………………………… 91
2.10 ZOJ3168-SortZOJ7………………………………………………………………… 92
2.10.1 题目内容……………………………………………………………………… 92
2.10.2 汉语翻译……………………………………………………………………… 92
2.10.3 算法分析……………………………………………………………………… 92
2.10.4 参考代码……………………………………………………………………… 95
2.10.5 字符和字符串的输入输出…………………………………………………… 96
2.11 ZOJ3610-YetAnotherStoryofRock-paper-scissors……………………………… 98
2.11.1 题目内容……………………………………………………………………… 98
2.11.2 汉语翻译……………………………………………………………………… 99
2.11.3 算法分析…………………………………………………………………… 100
2.11.4 参考代码…………………………………………………………………… 100
2.12 ZOJ3210-AStackorAQueue …………………………………………………… 101
2.12.1 题目内容…………………………………………………………………… 101
2.12.2 汉语翻译…………………………………………………………………… 102
2.12.3 算法分析(一)……………………………………………………………… 102
2.12.4 参考代码(一)……………………………………………………………… 106
2.12.5 算法分析(二)……………………………………………………………… 107
2.12.6 参考代码(二)……………………………………………………………… 109
·6 · C语言程序设计进阶(ACM 实践)
2.12.7 数组中循环查找的处理…………………………………………………… 110
2.13 ZOJ3499-Median ………………………………………………………………… 113
2.13.1 题目内容…………………………………………………………………… 113
2.13.2 汉语翻译…………………………………………………………………… 114
2.13.3 算法分析…………………………………………………………………… 114
2.13.4 参考代码…………………………………………………………………… 115
第3章 字符串题…………………………………………………………………………… 117
3.1 ZOJ2970-Faster,Higher,Stronger ……………………………………………… 117
3.1.1 题目内容……………………………………………………………………… 117
3.1.2 汉语翻译……………………………………………………………………… 118
3.1.3 算法分析……………………………………………………………………… 118
3.1.4 参考代码……………………………………………………………………… 121
3.1.5 字符串比较函数strcmp() ………………………………………………… 123
3.2 ZOJ1755-ClayBully………………………………………………………………… 124
3.2.1 题目内容……………………………………………………………………… 124
3.2.2 汉语翻译……………………………………………………………………… 125
3.2.3 算法分析(一)………………………………………………………………… 125
3.2.4 参考代码(一)………………………………………………………………… 127
3.2.5 字符串拷贝函数strcpy()…………………………………………………… 127
3.2.6 算法分析(二)………………………………………………………………… 128
3.2.7 参考代码(二)………………………………………………………………… 129
3.2.8 二维字符数组存放字符串…………………………………………………… 130
3.3 ZOJ1365-MileageBank …………………………………………………………… 131
3.3.1 题目内容……………………………………………………………………… 131
3.3.2 汉语翻译……………………………………………………………………… 132
3.3.3 算法分析……………………………………………………………………… 133
3.3.4 参考代码……………………………………………………………………… 136
3.4 ZOJ3492-KagomeKagome ………………………………………………………… 137
3.4.1 题目内容……………………………………………………………………… 137
3.4.2 汉语翻译……………………………………………………………………… 138
3.4.3 算法分析……………………………………………………………………… 138
3.4.4 参考代码……………………………………………………………………… 140
3.5 ZOJ3207-80ers′Memory…………………………………………………………… 141
3.5.1 题目内容……………………………………………………………………… 141
3.5.2 汉语翻译……………………………………………………………………… 142
3.5.3 算法分析……………………………………………………………………… 143
3.5.4 参考代码……………………………………………………………………… 144
目 录 ·7 ·
3.6 ZOJ3479-ChineseZodiac…………………………………………………………… 145
3.6.1 题目内容……………………………………………………………………… 145
3.6.2 汉语翻译……………………………………………………………………… 146
3.6.3 算法分析(一)………………………………………………………………… 147
3.6.4 参考代码(一)………………………………………………………………… 148
3.6.5 算法分析(二)………………………………………………………………… 148
3.6.6 参考代码(二)………………………………………………………………… 149
3.7 ZOJ3594-SexagenaryCycle ………………………………………………………… 150
3.7.1 题目内容……………………………………………………………………… 150
3.7.2 汉语翻译……………………………………………………………………… 151
3.7.3 算法分析……………………………………………………………………… 151
3.7.4 参考代码……………………………………………………………………… 153
3.8 ZOJ2851-CodeFormatter ………………………………………………………… 154
3.8.1 题目内容……………………………………………………………………… 154
3.8.2 汉语翻译……………………………………………………………………… 155
3.8.3 算法分析……………………………………………………………………… 155
3.8.4 参考代码……………………………………………………………………… 158
3.9 ZOJ2971-GiveMetheNumber …………………………………………………… 159
3.9.1 题目内容……………………………………………………………………… 159
3.9.2 汉语翻译……………………………………………………………………… 160
3.9.3 算法分析……………………………………………………………………… 161
3.9.4 参考代码……………………………………………………………………… 166
3.10 ZOJ3490-StringSuccessor………………………………………………………… 168
3.10.1 题目内容…………………………………………………………………… 168
3.10.2 汉语翻译…………………………………………………………………… 169
3.10.3 算法分析…………………………………………………………………… 170
3.10.4 参考代码…………………………………………………………………… 174
3.11 ZOJ3713-In7-bit ………………………………………………………………… 177
3.11.1 题目内容…………………………………………………………………… 177
3.11.2 汉语翻译…………………………………………………………………… 178
3.11.3 算法分析(一)……………………………………………………………… 179
3.11.4 参考代码(一)……………………………………………………………… 181
3.11.5 算法分析(二)……………………………………………………………… 183
3.11.6 参考代码(二)……………………………………………………………… 183
第4章 模拟题……………………………………………………………………………… 185
4.1 ZOJ2850-BeautifulMeadow ……………………………………………………… 185
4.1.1 题目内容……………………………………………………………………… 185
4.1.2 汉语翻译……………………………………………………………………… 186
·8 · C语言程序设计进阶(ACM 实践)
4.1.3 算法分析……………………………………………………………………… 186
4.1.4 参考代码……………………………………………………………………… 188
4.2 ZOJ3600-TaxiFare ………………………………………………………………… 190
4.2.1 题目内容……………………………………………………………………… 190
4.2.2 汉语翻译……………………………………………………………………… 191
4.2.3 算法分析……………………………………………………………………… 191
4.2.4 参考代码……………………………………………………………………… 192
4.3 ZOJ3693-HappyGreatBG ………………………………………………………… 194
4.3.1 题目内容……………………………………………………………………… 194
4.3.2 汉语翻译……………………………………………………………………… 195
4.3.3 算法分析……………………………………………………………………… 195
4.3.4 参考代码……………………………………………………………………… 197
4.4 ZOJ3714-JavaBeans ……………………………………………………………… 197
4.4.1 题目内容……………………………………………………………………… 197
4.4.2 汉语翻译……………………………………………………………………… 198
4.4.3 算法分析(一)………………………………………………………………… 198
4.4.4 参考代码(一)………………………………………………………………… 200
4.4.5 算法分析(二)………………………………………………………………… 201
4.4.6 参考代码(二)………………………………………………………………… 201
4.5 ZOJ2965-AccuratelySay"CocaCola"! …………………………………………… 202
4.5.1 题目内容……………………………………………………………………… 202
4.5.2 汉语翻译……………………………………………………………………… 203
4.5.3 算法分析……………………………………………………………………… 203
4.5.4 参考代码……………………………………………………………………… 205
4.6 ZOJ3193-AccuratelySay"CocaCola"!Again …………………………………… 206
4.6.1 题目内容……………………………………………………………………… 206
4.6.2 汉语翻译……………………………………………………………………… 207
4.6.3 算法分析……………………………………………………………………… 207
4.6.4 参考代码……………………………………………………………………… 211
4.7 ZOJ3498-Javabeans ………………………………………………………………… 212
4.7.1 题目内容……………………………………………………………………… 212
4.7.2 汉语翻译……………………………………………………………………… 213
4.7.3 算法分析……………………………………………………………………… 213
4.7.4 参考代码……………………………………………………………………… 215
4.8 ZOJ3706-BreakStandardWeight ………………………………………………… 216
4.8.1 题目内容……………………………………………………………………… 216
4.8.2 汉语翻译……………………………………………………………………… 217
4.8.3 算法分析……………………………………………………………………… 217
目 录 ·9 ·
4.8.4 参考代码……………………………………………………………………… 222
4.9 ZOJ3212-K-Nice …………………………………………………………………… 225
4.9.1 题目内容……………………………………………………………………… 225
4.9.2 汉语翻译……………………………………………………………………… 226
4.9.3 算法分析(一)………………………………………………………………… 226
4.9.4 参考代码(一)………………………………………………………………… 229
4.9.5 算法分析(二)………………………………………………………………… 230
4.9.6 参考代码(二)………………………………………………………………… 232
4.10 ZOJ3313-Clock …………………………………………………………………… 232
4.10.1 题目内容…………………………………………………………………… 232
4.10.2 汉语翻译…………………………………………………………………… 233
4.10.3 算法分析…………………………………………………………………… 233
4.10.4 参考代码…………………………………………………………………… 234
4.11 ZOJ3326-AnAwfulProblem……………………………………………………… 235
4.11.1 题目内容…………………………………………………………………… 235
4.11.2 汉语翻译…………………………………………………………………… 236
4.11.3 算法分析…………………………………………………………………… 236
4.11.4 参考代码…………………………………………………………………… 240
4.12 ZOJ3603-DrawSomethingCheat ………………………………………………… 242
4.12.1 题目内容…………………………………………………………………… 242
4.12.2 汉语翻译…………………………………………………………………… 243
4.12.3 算法分析…………………………………………………………………… 244
4.12.4 参考代码…………………………………………………………………… 249
4.13 ZOJ3486-JudgeInternalError…………………………………………………… 251
4.13.1 题目内容…………………………………………………………………… 251
4.13.2 汉语翻译…………………………………………………………………… 252
4.13.3 算法分析…………………………………………………………………… 252
4.13.4 参考代码…………………………………………………………………… 253
4.14 ZOJ3607-LazierSalesgirl ………………………………………………………… 254
4.14.1 题目内容…………………………………………………………………… 254
4.14.2 汉语翻译…………………………………………………………………… 255
4.14.3 算法分析…………………………………………………………………… 255
4.14.4 参考代码…………………………………………………………………… 258
4.15 ZOJ3712-HardtoPlay …………………………………………………………… 259
4.15.1 题目内容…………………………………………………………………… 259
4.15.2 汉语翻译…………………………………………………………………… 261
4.15.3 算法分析…………………………………………………………………… 261
4.15.4 参考代码…………………………………………………………………… 263
·10 · C语言程序设计进阶(ACM 实践)
第5章 数学题……………………………………………………………………………… 265
5.1 ZOJ2099-FramePolygonalLine…………………………………………………… 265
5.1.1 题目内容……………………………………………………………………… 265
5.1.2 汉语翻译……………………………………………………………………… 266
5.1.3 算法分析……………………………………………………………………… 266
5.1.4 参考代码……………………………………………………………………… 269
5.2 ZOJ2969-EasyTask………………………………………………………………… 270
5.2.1 题目内容……………………………………………………………………… 270
5.2.2 汉语翻译……………………………………………………………………… 271
5.2.3 算法分析……………………………………………………………………… 272
5.2.4 参考代码……………………………………………………………………… 274
5.3 ZOJ3488-ConicSection …………………………………………………………… 274
5.3.1 题目内容……………………………………………………………………… 274
5.3.2 汉语翻译……………………………………………………………………… 275
5.3.3 算法分析……………………………………………………………………… 276
5.3.4 参考代码……………………………………………………………………… 280
5.4 ZOJ3203-LightBulb ……………………………………………………………… 281
5.4.1 题目内容……………………………………………………………………… 281
5.4.2 汉语翻译……………………………………………………………………… 282
5.4.3 算法分析……………………………………………………………………… 282
5.4.4 参考代码……………………………………………………………………… 287
5.5 ZOJ2975-KindsofFuwas ………………………………………………………… 288
5.5.1 题目内容……………………………………………………………………… 288
5.5.2 汉语翻译……………………………………………………………………… 289
5.5.3 算法分析……………………………………………………………………… 290
5.5.4 参考代码……………………………………………………………………… 296
5.6 ZOJ3702-Gibonaccinumber ……………………………………………………… 297
5.6.1 题目内容……………………………………………………………………… 297
5.6.2 汉语翻译……………………………………………………………………… 298
5.6.3 题目分析……………………………………………………………………… 298
5.6.4 参考代码……………………………………………………………………… 302
5.7 ZOJ2829-BeautifulNumber ……………………………………………………… 304
5.7.1 题目内容……………………………………………………………………… 304
5.7.2 汉语翻译……………………………………………………………………… 304
5.7.3 算法分析(一)………………………………………………………………… 304
5.7.4 参考代码(一)………………………………………………………………… 306
5.7.5 算法分析(二)………………………………………………………………… 307
5.7.6 参考代码(二)………………………………………………………………… 308
目 录 ·11 ·
5.8 ZOJ3609-ModularInverse ………………………………………………………… 309
5.8.1 题目内容……………………………………………………………………… 309
5.8.2 汉语翻译……………………………………………………………………… 309
5.8.3 算法分析(一)………………………………………………………………… 310
5.8.4 参考代码(一)………………………………………………………………… 311
5.8.5 算法分析(二)………………………………………………………………… 312
5.8.6 参考代码(二)………………………………………………………………… 313
5.9 ZOJ3194-Coverage ………………………………………………………………… 313
5.9.1 题目内容……………………………………………………………………… 313
5.9.2 汉语翻译……………………………………………………………………… 314
5.9.3 算法分析……………………………………………………………………… 314
5.9.4 参考代码 …………………………………………………………………… 319
5.10 ZOJ3483-GaussianPrime ………………………………………………………… 320
5.10.1 题目内容…………………………………………………………………… 320
5.10.2 汉语翻译…………………………………………………………………… 321
5.10.3 算法分析(一)……………………………………………………………… 321
5.10.4 参考代码(一)……………………………………………………………… 324
5.10.5 算法分析(二)……………………………………………………………… 326
5.10.6 参考代码(二)……………………………………………………………… 328
5.10.7 算法分析(三)……………………………………………………………… 330
5.10.8 参考代码(三)……………………………………………………………… 331
5.10.9 算法分析(四)……………………………………………………………… 332
5.10.10 参考代码(四)……………………………………………………………… 335
第6章 图论题……………………………………………………………………………… 337
6.1 ZOJ3708-DensityofPowerNetwork ……………………………………………… 337
6.1.1 题目内容……………………………………………………………………… 337
6.1.2 汉语翻译……………………………………………………………………… 338
6.1.3 算法分析(一)………………………………………………………………… 339
6.1.4 参考代码(一)………………………………………………………………… 340
6.1.5 算法分析(二)………………………………………………………………… 341
6.1.6 参考代码(二)………………………………………………………………… 342
6.1.7 算法分析(三)………………………………………………………………… 343
6.1.8 参考代码(三)………………………………………………………………… 344
6.2 ZOJ3710-Friends …………………………………………………………………… 346
6.2.1 题目内容……………………………………………………………………… 346
6.2.2 汉语翻译……………………………………………………………………… 347
6.2.3 算法分析……………………………………………………………………… 347
6.2.4 参考代码……………………………………………………………………… 352
·12 · C语言程序设计进阶(ACM 实践)
6.3 ZOJ3328-WuXing ………………………………………………………………… 354
6.3.1 题目内容……………………………………………………………………… 354
6.3.2 汉语翻译……………………………………………………………………… 356
6.3.3 算法分析……………………………………………………………………… 356
6.3.4 参考代码……………………………………………………………………… 359
6.4 ZOJ3332-StrangeCountryII ……………………………………………………… 359
6.4.1 题目内容……………………………………………………………………… 359
6.4.2 汉语翻译……………………………………………………………………… 360
6.4.3 算法分析……………………………………………………………………… 360
6.4.4 参考代码……………………………………………………………………… 364
6.5 ZOJ2966-BuildTheElectricSystem ……………………………………………… 366
6.5.1 题目内容……………………………………………………………………… 366
6.5.2 汉语翻译……………………………………………………………………… 366
6.5.3 算法分析……………………………………………………………………… 367
6.5.4 参考代码……………………………………………………………………… 369
6.6 ZOJ3204-Connectthem …………………………………………………………… 370
6.6.1 题目内容……………………………………………………………………… 370
6.6.2 汉语翻译……………………………………………………………………… 371
6.6.3 算法分析……………………………………………………………………… 372
6.6.4 参考代码……………………………………………………………………… 375
参考文献……………………………………………………………………………………… 378
