算法競賽入門經典習題  第三章

在下面的習題中，前一半的題目幾乎只需要“按照題目說的做”，但后面的題目需要一些思考甚至靈感。

為了保證學習效果，請至少獨立完成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.