算法竞赛入门经典习题 第三章

算法竞赛入门经典习题  第三章

在下面的习题中，前一半的题目几乎只需要“按照题目说的做”，但后面的题目需要一些思考甚至灵感。

为了保证学习效果，请至少独立完成8道习题。 

习题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。

//输入字符串判断X与O然后处理得分。

//如果为X则重置为0，否则一直加1，每次将得到分值相加。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;int main(){    int t;    char s[200];    int kase = 0;    scanf("%d", &t);    while (t--)    {        int score = 0, sum = 0;        scanf("%s", s);        int l = strlen(s);        for (int i = 0; i < l; i++)        {            if (s[i] == 'X')                score = 0;            if (s[i] == 'O')                score++;            sum += score;        }        PRintf("%d/n", sum);    }    return 0;}
#include <cstdio>#include <cstring>const int maxn = 150;int main(){    char s[maxn];    int t, kase = 0;    scanf("%d", &t);    while (t--)    {        int num = 0, score = 0;        scanf("%s", s);        int l = strlen(s);        for (int i = 0; i < l; i++)        {            if (s[i] == 'O')            {                num++;                score += num;            }            else                num = 0;        }        printf("%d/n", score);    }    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。 
【解题思路分析】
1. 建立字母到数值(原子量)的映射数组。 2. 原子后面数值可能为多位数，一直往后判断，直到不是数字，i值自增。 3. 碰到字母直接加原子量；碰到数字用（数字-1）乘以原子量。
#include <iostream>#include <cstring>#include <cstdio>#include <cctype>const double m[] = {0, 0, 12.01, 0, 0, 0, 0, 1.008, 0, 0, 0, 0, 0, 14.01, 16.00};int main(){    char s[150];    int t;    scanf("%d", &t);    while (t--)    {        memset(s, '0', sizeof(s));        double sum = 0;        scanf("%s", s);        char ch = s[0];        int l = strlen(s), n;        for(int i = 0; i < l; i++)        {            if (isalpha(s[i]))            {                ch = s[i];                sum += m[ch - 'A'];            }            else            {                n = s[i] - '0';                if (isdigit(s[i+1]))                {                    n = n*10 + (s[i+1] - '0');                    i++;                }                sum += m[ch - 'A'] * (n - 1);            }        }        printf("%.3lf/n", sum);    }    return 0;}----------------------其他方法------------------------
#include<stdio.h>#include<string.h>#include<ctype.h>//int isdigit(int,char)需要的头文件#define MAX 20double getWeight(char c){    double w = 0;    switch (c) {        case 'c':        case 'C': w = 12.01;break;        case 'h':        case 'H': w = 1.008;break;        case 'o':        case 'O': w = 16.00;break;        case 'n':        case 'N': w = 14.01;break;    }    return w;}int main() {    char str[MAX];    scanf("%s", str);    if(isdigit(str[0])){//isdigit判断字符是不是数字        printf("输入格式错误！/n");        return 0;    }    double weight = 0;    double sum = 0;    for (int i=0; i<strlen(str);i++){        int num = 1;        for(int pre=0; isdigit(str[i]);i++){            num = pre*10+str[i]-'0';            pre = num;        }        sum += num * weight;   //weight = str[i-1]'s weight        if(i<strlen(str)) weight = getWeight(str[i]);  //weight = str[i]'s weight    }    sum += weight;//加上最后一次循环的原子量    printf("分子量为：%.3lfg/mol/n", sum);    return 0;}
习题3-3数数字（Digit Counting , ACM/ICPC Danang 2007, UVa1225）
把前n（n≤10000）个整数顺次写在一起：123456789101112…数一数0～9各出现多少次
（输出10个整数，分别是0，1，…，9出现的次数）。
注意：  数个数时别漏0，且从1开始数。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int main(){    int t;    scanf("%d", &t);    while (t--)    {        int n, x;        scanf("%d", &n);        int a[10];        memset(a, 0, sizeof(a));        for (int i = 1; i <= n; i++)        {            x = i;            while (x)            {                a[x%10]++;                x /= 10;            }        }        printf("%d", a[0]);        for (int i = 1; i < 10; i++)            printf(" %d", a[i]);        printf("/n");    }    return 0;}注：本题可参考-骑金刚跨长城-解题过程，因崔思婷。
习题3-4周期串（Periodic Strings, UVa455）
如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。
例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。
输入一个长度不超过80的字符串，输出其最小周期。
【解题思路分析】
1.如果i为最小周期，那么字符串长度必定是i的整数倍
2.再判断i是否为周期。
#include <cstdio>#include <cstring>const int maxn = 82;int main(){    char s[maxn];    int t;    scanf("%d", &t);    while (t--)    {        memset(s, '0', sizeof(s));        scanf("%s", s);        int m = strlen(s);        for (int i = 1; i < m; i++)        {            if (m % i == 0)            {                bool f = true;                for (int j = i; j < 2*i; j++)                {                    if (s[j - i] != s[j])                        f = false;                }                if (f)                {                    printf("%d/n", i);                    break;                }            }        }    }    return 0;}
注意：类似abcdeabcabcdeabcabcdeabcabcdeabcabcdeabc的判断以及最小周期。
To Be Continued.