算法竞赛入门经典（第二版） 答案汇总（持续更新）

大佬们，更不动了啊，真的没时间啊

第二章

习题2-1 水仙花数（ daffodil）
输出

输出100～ 999中的所有水仙花数。 若3位数ABC满足ABC＝ A3＋ B3＋ C3， 则称其为水仙花
数。 例如153＝ 13＋ 53＋ 33， 所以153是水仙花数。

# include <iostream>

using namespace std;

int main(){

int ABC = 100;

for( ; ABC <= 999; ABC++){

int A3, B3, C3;

A3 = ABC / 100; B3 = ABC / 10 % 10; C3 = ABC % 10;

if(ABC == A3*A3*A3 + B3*B3*B3 + C3*C3*C3)

cout << ABC << ' ' ;

}

cout << endl;

return 0;

}

习题2-2 韩信点兵（ hanxin）
相传韩信才智过人， 从不直接清点自己军队的人数， 只要让士兵先后以三人一排、 五人
一排、 七人一排地变换队形， 而他每次只掠一眼队伍的排尾就知道总人数了。 输入包含多组
数据， 每组数据包含3个非负整数a， b， c， 表示每种队形排尾的人数（ a＜ 3， b＜ 5， c＜
7） ， 输出总人数的最小值（ 或报告无解） 。 已知总人数不小于10， 不超过100。 输入到文件

结束为止。

# include <iostream>

# define LOCAL

using namespace std;

int main(){

int a, b, c, flag = 0, count = 0;

while(cin >> a >> b >> c){

count++;

flag = 0;

for(int i = 0; i < 34; i++){

int num = 3 * i + a;

if(num % 5 == b && num % 7 == c && num >0 && num < 100){

cout << "Case " << count << ": " << num << endl;

flag = 1;

}

}

if(!flag)

cout << "Case " << count << ": " << "NO answer!" << endl;

}

}

习题2-3 倒三角形（ triangle）
输入正整数n≤20， 输出一个n层的倒三角形。 例如， n＝ 5时输出如下：
#########
#######
#####
###

#

# include <iostream>

using namespace std;

int main(){

int n, k;

cin >> n;

k = 2*n-1;

for(int i = 0; i < n; i++){

for(int j = i; j > 0; j--){

cout << ' ';

}

for( ; k > 0; k--){

cout << "*";

}

k = 2*n-1 - (i+1)*2;

cout << endl;

}

return 0;

}

题2-4 子序列的和（ subsequence）
输入两个正整数n＜ m＜ 106， 输出 ， 保留5位小数。 输入包含多组数据，
结束标记为n＝ m＝ 0。 提示： 本题有陷阱。 

# include <iostream>

using namespace std;

int main(){

long long n, m, count = 0;

double sum = 0;

while(cin >> n >> m){

count++;

if(n > m || (n == 0 && m == 0)){

cout << "Case " << count << ": " << "GG" << endl;

return 0;

}

for(long long i = n; i <= m; i++)

sum += 1 / (double) i / i;

printf("Case %d: %.5lfn", count, sum);

}

return 0;

}

习题2-5 分数化小数（ decimal）
输入正整数a， b， c， 输出a/b的小数形式， 精确到小数点后c位。 a， b≤106， c≤100。 输
入包含多组数据， 结束标记为a＝ b＝ c＝ 0。 

# include <iostream>

using namespace std;

int main(){

int a, b, c, count = 0;

while(cin >> a >> b >> c){

count++;

if(a == 0 && b == 0 && c == 0)

return 0;

else

printf("Case: %d: %.*lfn", count++, c, (double) a / b);

}

return 0;

}

习题2-6 排列（ permutation）
用1， 2， 3， …， 9组成3个三位数abc， def和ghi， 每个数字恰好使用一次， 要
求abc： def： ghi＝ 1： 2： 3。 按照“abc def ghi”的格式输出所有解， 每行一个解。 提示： 不必太动脑筋。

# include <iostream>

using namespace std;

void Judge(int array[], int num){

int a = num % 10, b = num / 10 % 10, c = num / 100;

array[a]++; array[b]++; array[c]++;

}

int main(){

for(int i = 100; i < 334; i++){

int a[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int abc = i * 1, def = i * 2, ghi = i * 3, j;

Judge(a, abc); Judge(a, def); Judge(a, ghi);

for(j = 1; j < 10; j++){

if(a[j] != 1 || a[0] != 0)

break;

}

if(j == 10){

cout << abc << ' ' << def << ' ' << ghi << endl;

}

}

}

课后思考题2。 下面的程序运行结果是什么？ “！ ＝ ”运算符表示“不相等”。 提示： 请上机实
验， 不要凭主观感觉回答。

#include<stdio.h>

int main()

{

double i;

for(i = 0; i != 10; i += 0.1)

printf("%.1fn", i);

return 0;

}

例：const double EFS = 0.000001; for(int i = 0; i - 10.0 < EFS; i++);

第三章

3-12 处的例子（很有意思，个人推荐试一下）

//输出流的问题

# include <iostream>

using namespace std;

int main(){

int count = 1;

count = count++;

cout << count << endl;

cout << count++ << ',' << count++ << ',' << count++ << endl;

}

习题3-1 得分（ Score, ACM/ICPC Seoul 2005, UVa1585）
给出一个由O和X组成的串（ 长度为1～ 80） ， 统计得分。 每个O的得分为目前连续出现

的O的个数， X的得分为0。 例如， OOXXOXXOOO的得分为1+2+0+0+1+0+0+1+2+3。

# include <iostream>

using namespace std;

int main(){

char s[100001], ch = 1;

int n = 0;

scanf("%d", &n);

while(n--){

int flag = 0, i = 0, score = 0;

scanf("%s", s);

while(s[i] != ''){

if(s[i++] == 'O') score += ++flag;

else flag = 0;

}

cout << score << endl;

}

return 0;

}

习题3-2 分子量（ Molar Mass, ACM/ICPC Seoul 2007, UVa1586）
给出一种物质的分子式（ 不带括号） ， 求分子量。 本题中的分子式只包含

给出一种物质的分子式（ 不带括号） ， 求分子量。 本题中的分子式只包含4种原子， 分
别为C, H, O, N， 原子量分别为12.01, 1.008, 16.00, 14.01（ 单位： g/mol） 。 例如， C6H5OH的

分子量为94.108g/mol。

# include <iostream>

# include <cstring>

using namespace std;

int main(){

const double C = 12.01, H = 1.008, O = 16.00, N = 14.01;

int n;

scanf("%d", &n);

while(n--){

double sum_w = 0;

char s[10000];

scanf("%s", s);

for(int i = 0; i < strlen(s); ){

int num = 0, j = i + 1, k = i;

if(s[j] - '0' < 9 && s[j] != ''){

num = s[j] - '0', j++;

for( ; s[j] - '0' < 9 && s[j] != ''; j++)

num = num * 10 + (s[j] - '0');

i = j;

}

else num = 1, i++;

switch (s[k]){

case 'C': sum_w += 12.01 * num; break;

case 'H': sum_w += 1.008 * num; break;

case 'O': sum_w += 16.00 * num; break;

case 'N': sum_w += 14.01 * num; break;

}

}

printf("%.3lfn", sum_w);

}

return 0;

}

习题3-3 数数字（ Digit Counting , ACM/ICPC Danang 2007, UVa1225）
把前n（ n≤10000） 个整数顺次写在一起： 123456789101112…数一数0～ 9各出现多少次

（ 输出10个整数， 分别是0， 1， …， 9出现的次数） 。

# include <iostream>

# include <cstring>

using namespace std;

int main(){

int n, a;

cin >> n;

while(n--){

int s[10];

memset(s, 0, sizeof(s));

cin >> a;

for(int i = 1; i <= a; i++){

int j = 0, k = i;

while(1){

int a1 = k % 10;

s[a1]++, k /= 10;

if(k / 10 == 0 && k % 10 == 0)

break;

}

}

for(int i = 0; i < 9; i++)

cout << s[i] << ' ';

cout << s[9] << endl;

}

return 0;

}

习题3-4 周期串（ Periodic Strings, UVa455）
如果一个字符串可以由某个长度为k的字符串重复多次得到， 则称该串以k为周期。 例
如， abcabcabcabc以3为周期（ 注意， 它也以6和12为周期） 。

输入一个长度不超过80的字符串， 输出其最小周期。

# include <iostream>

# include <cstring>

using namespace std;

int main(){

int n;

scanf("%d", &n);

while(n--){

char s[100];

scanf("%s", s);

int flag = 0;

for(int min_len = 1; min_len <= strlen(s); min_len++){

if(strlen(s) % min_len != 0) continue;

for(int i = 0; i < strlen(s); i++){

if(s[i % min_len] != s[i])

break;

else if(i == strlen(s) - 1){

flag = 1;

if(n) cout << min_len << endl << endl;

else cout << min_len << endl;

}

}

if(flag) break;

}

}

return 0;

}

习题3-5 谜题（ Puzzle, ACM/ICPC World Finals 1993, UVa227）
有一个5*5的网格， 其中恰好有一个格子是空的， 其他格子各有一个字母。 一共有4种指
令： A, B, L, R， 分别表示把空格上、 下、 左、 右的相邻字母移到空格中。 输入初始网格和指
令序列（ 以数字0结束） ， 输出指令执行完毕后的网格。 如果有非法指令， 应输出“This

puzzle has no final configuration.”， 例如， 图3-5中执行ARRBBL0后， 效果如图3-6所示

# include <iostream>

# include <cstring>

using namespace std;

int main(){

int n = 1, c = 0;

while(n++){

int flag = 0;

char s[10][10], s1[100];

int x = 0, y = 0, index_x, index_y;

for(int i = 0; i < 5; i++){

fgets(s[i], 100, stdin);

if(s[0][0] == 'Z') return 0;

}

for(int i = 0; i < 5; i++)

for(int j = 0; j < 5; j++){

if(s[i][j] < 'A' || s[i][j] > 'Z'){

x = i, y = j;

index_x = x, index_y = y;

break;

}

}

int j = 0;

while((s1[j++] = getchar()) != '0'){}

getchar(); j = 0;

while(s1[j++] != '0'){

switch(s1[j-1]){

case 'A':

index_x--; break;

case 'B':

index_x++; break;

case 'L':

index_y--; break;

case 'R':

index_y++; break;

}

if(index_x < 0 || index_x > 4 || index_y < 0 || index_y > 4){

flag = 1; break;

}

else{

s[x][y] = s[index_x][index_y];

s[index_x][index_y] = ' ';

x = index_x, y = index_y;

}

}

if(c++) cout << endl;

cout << "Puzzle #" << n - 1 << ':' << endl;

if(flag) {

cout << "This puzzle has no final configuration." << endl;

continue;

}

for(int i = 0; i < 5; i++){

for(int j = 0; j < 5; j++){

if(j) cout << ' ';

cout << s[i][j];

}

cout << endl;

}

}

return 0;

}

习题3-6 纵横字谜的答案（ Crossword Answers, ACM/ICPC World Finals 1994,
UVa232）
输入一个r行c列（ 1≤r， c≤10） 的网格， 黑格用“*”表示， 每个白格都填有一个字母。 如
果一个白格的左边相邻位置或者上边相邻位置没有白格（ 可能是黑格， 也可能出了网格边
界） ， 则称这个白格是一个起始格。
首先把所有起始格按照从上到下、 从左到右的顺序编号为1, 2, 3,…， 如图3-7所示 

# include <iostream>

# include <cstring>

using namespace std;

int main(){

int n = 1, null = 0;

while(n++){

int row, col, count = 0, flag[100][100];

char s[100][100];

memset(flag, 0, sizeof(flag));

cin >> row;

if(!row) break;

cin >> col; getchar();

for(int i = 0; i < row; i++)

fgets(s[i], 100, stdin);

for(int i = 0; i < row; i++){

for(int j = 0; j < col; j++){

if((s[i][j] != '*') && (i - 1 < 0 || j - 1 < 0 || s[i-1][j] == '*' || s[i][j-1] == '*')){

flag[i][j] = ++count;

null++;

}

else if(s[i][j] != '*') flag[i][j] = 99999;

}

}

if(!null) {

cout << "puzzle #" << n-1 << ':' << endl << "Across" << endl << "Down" << endl;

continue;

}

if(n > 2) cout << endl;

cout << "puzzle #" << n-1 << ':' << endl << "Across";

for(int i = 0; i < row; i++){

for(int j = 0; j < col; j++){

if((!flag[i][j-1] && flag[i][j]) || (j - 1 < 0 && flag[i][j]))

printf("n%3d.", flag[i][j]);

if(flag[i][j]) cout << s[i][j];

}

}

cout << endl << "Down";

for(int fr = 0; fr < row; fr++){

for(int fc = 0; fc < col; fc++){

if((flag[fr][fc] && flag[fr][fc] < 1000 && !flag[fr-1][fc]) || (fr - 1 < 0) && flag[fr][fc]){

printf("n%3d.", flag[fr][fc]);

for(int i = fr; i < row; i++){

if(flag[i][fc]) cout << s[i][fc];

else break;

}

}

}

}

cout << endl;

}

return 0;

}

习题4-1 象棋（ Xiangqi, ACM/ICPC Fuzhou 2011, UVa1589）
考虑一个象棋残局， 其中红方有n（ 2≤n≤7） 个棋子， 黑方只有一个将。 红方除了有一个
帅（ G） 之外还有3种可能的棋子： 车（ R） ， 马（ H） ， 炮（ C） ， 并且需要考虑“蹩马
腿”（ 如图4-4所示） 与将和帅不能照面（ 将、 帅如果同在一条直线上， 中间又不隔着任何棋
子的情况下， 走子的一方获胜） 的规则。
输入所有棋子的位置， 保证局面合法并且红方已经将军。 你的任务是判断红方是否已经

把黑方将死。 关于中国象棋的相关规则请参见原题。

# include <iostream>

# include <cstring>

# include <cmath>

using namespace std;

struct pst{

char ch;

int x;

int y;

};

bool is_alive(int flag[][11], int x, int y){

for(int i = 1; i < 4; i++){

for(int j = 4; j < 7; j++){

if(abs(x - i) == 1 && y == j && !flag[i][j])

return false;

else if(abs(y - j) == 1 && x == i && !flag[i][j])

return false;

}

}

return true;

}

void Gernal(int flag[][11], int x, int y){

for(int i = x-1; i > 0; i--){

if(flag[i][y] == 999)

break;

else{

flag[i][y] = 1;

}

}

}

void Chariot(int flag[][11], int x, int y){

for(int i = 0; i < 11; i++){

if(flag[i][y] == 999) break;

else flag[i][y] = 1;

if(i == x - 1) i++;

}

for(int j = 0; j < 11; j++){

if(flag[x][j] == 999) break;

else flag[j][y] = 1;

if(j == y - 1) j++;

}

}

void Cannon(int flag[][11], int x, int y){

for(int i = x+1; i < 11; i++){

if(flag[i][y] == 999 && i != 10){

for(int k = i+1; k < 11 && flag[k][y] != 999; k++){

flag[k][y] = 1;

}

break;

}

}

for(int i = x-1; i > 0; i--){

if(flag[i][y] == 999 && i != 1){

for(int k = i-1; k > 0 && flag[k][y] != 999; k--){

flag[k][y] = 1;

}

}

}

for(int j = y+1; j < 11; j++){

if(flag[x][j] == 999 && j != 10){

for(int k = j+1; k < 11 && flag[x][k] != 999; k++){

flag[x][k] = 1;

}

break;

}

}

for(int j = y-1; j > 0; j--){

if(flag[x][j] == 999 && j != 1){

for(int k = j-1; k > 0 || flag[x][k] != 999; k--){

flag[x][k] = 1;

}

}

}

}

void Horse(int flag[][11], int x, int y){

if(flag[x + 1][y] != 999){

flag[x + 2][y + 1] = 1;

flag[x + 2][y - 1] = 1;

}

if(flag[x - 1][y] != 999){

flag[x - 2][y + 1] = 1;

flag[x - 2][y - 1] = 1;

}

if(flag[x][y + 1] != 999){

flag[x + 1][y + 2] = 1;

flag[x - 1][y + 2] = 1;

}

if(flag[x][y - 1] != 999){

flag[x + 1][y - 2] = 1;

flag[x - 1][y - 2] = 1;

}

}

int main(){

freopen("C:\1.txt", "r", stdin);

int N, bg_x, bg_y, flag[11][11];

memset(flag, 0, sizeof(flag));

pst red[100];

while(1){

cin >> N >> bg_x >> bg_y;

if(!N) break;

for(int i = 0; i < N; i++){

cin >> red[i].ch >> red[i].x >> red[i].y;

flag[red[i].x][red[i].y] = 999;

}

for(int i = 0; i < N; i++){

switch(red[i].ch){

case 'G':

Gernal(flag, red[i].x, red[i].y);

break;

case 'R':

Chariot(flag, red[i].x, red[i].y);

break;

case 'C':

Cannon(flag, red[i].x, red[i].y);

break;

case 'H':

Horse(flag, red[i].x, red[i].y);

break;

}

}

if(is_alive(flag, bg_x, bg_y))

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

相关知识

前端文档汇总（含代码规范、开发流程、知识分享,持续更新）
算法竞赛入门经典第二版
2025深圳春季插班生最新消息汇总（持续更新）
2024无锡三八妇女节活动汇总（持续更新）
2023杭州七夕节活动汇总（持续更新）
2023开封春节灯会活动汇总（持续更新）
2024烟台母亲节活动汇总（持续更新）
【Mind+】图形化编程系列教程大全 持续更新 DF创客社区
2024年惠州春节活动汇总(持续更新)
奉化水蜜桃去哪里采摘？附采摘地汇总（持续更新）

网址: 算法竞赛入门经典（第二版） 答案汇总（持续更新） https://www.huajiangbk.com/newsview1438540.html