《算法竞赛入门经典-第二版》第三章习题答案_算法竞赛入门经典第二版答案pdf

作者：小惠珠哦 | 2024-08-18 06:54:13

踩

算法竞赛入门经典第二版答案pdf

《算法竞赛入门经典-第二版》课后习题答案

第三章（未更完）

习题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<stdio.h>
#include <string.h>
#define maxn 85
int main() {
    int number,tot = 0,numx=0;
    char s[maxn];
    scanf("%d",&number);
    while(number--){
        tot=0;
        numx=0;
        scanf("%s", s);
        for(int i = 0; i < strlen(s); i++){
            if(s[i] == 'O') tot=++numx+tot;
            else if (s[i] == 'X') numx=0;
        }
        printf("%d\n", tot);
    }
}

习题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<stdio.h>
#include <string.h>
#define maxn 85
int main() {
    int T,flag,num=0;
    char s[maxn];
    int result[4];
    //进行判定的分子式数目
    scanf("%d",&T);
    while(T--){
        //结果数组赋初值
        memset(result,0, sizeof(result));
        scanf("%s", s);
        for(int i = 0; i < strlen(s); i++){
            switch(s[i]){
                case 'C':
                    flag=0;
                    break;
                case 'H':
                    flag=1;
                    break;
                case 'O':
                    flag=2;
                    break;
                case 'N':
                    flag=3;
                    break;
            }
            //num表示该元素的个数
            num=0;
            //如果该元素接下来的字符是数字将计算个数，否则个数等于1
           while(s[i+1]>=48 &&s[i+1]<=57){
               ++i;
              num=num*10+(s[i]-'0');
           }
           if(num==0) num=1;
           result[flag]= result[flag]+num;
        }
        //结果输出
        printf("%.3f\n", result[0]*12.01+1.008*result[1]+result[2]*16.00+result[3]*14.01);
    }
}
'运行

习题3-3 数数字（Digit Counting , ACM/ICPC Danang 2007, UVa1225）

把前n（n≤10000）个整数顺次写在一起：123456789101112…数一数0～9各出现多少次（输出10个整数，分别是0，1，…，9出现的次数）


#include<stdio.h>
#include <string.h>
int main() {
    int T,number,numcount[10];
    scanf("%d",&T);
    while(T--){
        memset(numcount,0, sizeof(numcount));
       scanf("%d",&number);
        for (int i = 1; i <= number; i++) {
            int flag=i;
            //先将末位数字计数之后一步一步将十位百位计数
            while (flag>=10){
                numcount[flag%10]++;
                flag=flag/10;
            }
             numcount[flag]++;
        }
        //结果输出,最后一个数据输出之后不含空格直接换行
        for (int j = 0; j <9 ; j++) {
            printf("%d ",numcount[j]);
        }
        printf("%d\n",numcount[9]);
    }
}

习题3-4 周期串（Periodic Strings, UVa455）

如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。输入一个长度不超过80的字符串，输出其最小周期。


#include<stdio.h>
#include <string.h>
#define maxn 85
bool IsPs(const char* s, int p){
    //p将s分成strlen(s)/p段，判断每个段中的第i个数是否相等。
    for (int i = 0; i <p ; i++) {
        for (int j = 0; j <strlen(s)/p-1 ; j++) {
            if(s[j*p+i]!=s[(j+1)*p+i]) return false;
        }
    }
    return true;
}
int main() {
    int T;
    char s[maxn];
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        int length = strlen(s);
        //从1到k判断字符串是否以i为周期
        for (int i = 1; i <=length; i++)
        {
            //s不能整除i，肯定不以i为周期，跳过循环。
            if(length%i!=0) continue;
            //判断以s是否以i为周期，是的话结果输出
            if(IsPs(s,i))
            {
            printf("%d\n", i);
            if (T) printf("\n");
            break;
            }
        }
    }
}

习题3-5 谜题（Puzzle, ACM/ICPC World Finals 1993, UVa227）

有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A, B, L, R，分别表示把空格上、下、左、右的相邻字母移到空格中。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“Thispuzzle has no final configuration.”，例如，图3-5中执行ARRBBL0后，效果如图3-6所示。

输入：

AAAAA
DDDDD
SSSSS
GGGGG
EEEE
AZ
0
AAAAA
DDDDD
SSSSS
GGGGG
EEEE
A0
Z

预期输出：

Puzzle #1:
This puzzle has no final configuration.

Puzzle #2:
A A A A A
D D D D D
S S S S S
G G G G
E E E E G

输入直接用scanf（%s,s）当有空格的时候就会停止读入导致空格读取不上，

输出格式要注意很容易出现格式错误。


#include<stdio.h>
int main() {
char s[5][10];
int line =0,row=0,count =0 ;
while (1){
    //读取数组的值
    for (int i = 0; i <5 ; i++)
        {
        scanf("%[^\n]%*c",s[i]);
        if(s[i][0]=='Z') return 0;
        for (int j = 0; j <5 ; j++) {
            //找到空值的位置
            if(s[i][j]==' ')
            {
            line=i;
            row=j;
            }
        }
    }
    bool flag= true;
    char c;
    //对指令依次进行判断是否能执行
    while((c=getchar())!='0'){
        //前面已经有指令已经不能执行，后面的代码就没必要执行了
        if(!flag)continue;
        //判断指令能否执行
        switch(c){
            case 'A':
                if(line-1>=0){
                    s[line][row]=s[line-1][row];
                    s[--line][row]=' ';
                }
                else flag=false;
                break;
            case 'B':
                if(line+1<5){
                    s[line][row]=s[line+1][row];
                    s[++line][row]=' ';
                }
                else flag=false;
                break;
            case 'L':
                if(row-1>=0){
                    s[line][row]=s[line][row-1];
                    s[line][--row]=' ';
                }
                else flag=false;
                break;
            case 'R':
                if(row+1<5){
                    s[line][row]=s[line][row+1];
                    s[line][++row]=' ';
                }
                else flag=false;
                break;
            case '\n':
                break;
            default:
                flag=false;
                break;
        }
 
    }
    //通过getchar函数将\n去掉
    getchar();
    //结果输出
    if(count!=0)printf("\n");
    printf("Puzzle #%d:\n",++count);
    if(flag){
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j <4 ; j++) {
                putchar(s[i][j]);
                putchar(' ');
            }
            putchar(s[i][4]);
           putchar('\n');
        }
    }
    else printf("This puzzle has no final configuration.\n");
}
}

习题3-6　纵横字谜的答案（Crossword Answers, ACM/ICPC World Finals 1994,UVa232）

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

接下来要找出所有横向单词（Across）。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down）。这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】