算法竞赛入门经典(第二版)-刘汝佳-第三章 数组与字符串 例题+习题（17/18）

说明

本文是我对第三章题目的练习总结，建议配合紫书——《算法竞赛入门经典（第2版）》阅读本文。
另外为了方便做题，我在VOJ上开了一个contest，欢迎一起在上面做：第三章contest
如果想直接看某道题，请点开目录后点开相应的题目！！！

例题

例3-1 UVA 272 TeX 中的引号

思路
这个题主要讲带空格的输入输出处理。我总结了一下，主要有三种方案：
1、用getchar()一个一个字符处理
2、用fgets读入（gets已经过时）
3、用getline读入
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
    char c;
    bool flag = true;
    while ((c = getchar()) != EOF) {
        if (c == '\"') {
            printf("%s", flag ? "``" : "''");
            flag = !flag;
        } else
            printf("%c", c);
    }

    return 0;
}

---

例3-2 UVA 10082 WERTYU

思路
常量数组的妙用，可以使程序简洁很多。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

int main(void)
{
    char c;
    while ((c = getchar()) != EOF) {
        char *p = strchr(s, c);
        if (!p) putchar(c);
        else putchar(s[p-s-1]);
    }

    return 0;
}

---

例3-3 UVA 401 回文词

思路
常量字符串和字符串数组的妙用，使程序更简洁。
另外，学习了strchr函数，主要功能是在字符串中查找字符，返回字符指针。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const char mirror[] = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char *msg[4] = {" -- is not a palindrome.",
    " -- is a regular palindrome.",
    " -- is a mirrored string.",
    " -- is a mirrored palindrome."};

char trans(char c)
{
    if (c <= '9') return mirror[c - '0' + 25];
    return mirror[c - 'A'];
}

int main(void)
{
    char s[30];
    while (cin >> s) {
        int p = 1, m = 1;
        int n = strlen(s);
        for (int i = 0; i <= n/2; i ++) {
            if (s[i] != s[n-1-i]) p = 0;
            if (trans(s[i]) != s[n-1-i]) m = 0;
        }
        printf("%s%s\n\n", s, msg[m*2+p]);
    }

    return 0;
}

---

例3-4 UVA 340 猜数字游戏的提示

思路
当数值范围较小时，可以用统计数组。我这里判断正确值和错误值的方式与例题稍有不同，思路大同小异。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000;
const int M = 10;

int n, a0[N], c0[M], c2[M];
int a1[N], c1[M];

int main(void)
{
    int t = 0;
    while (cin >> n && n) {
        memset(c0, 0, sizeof(c0));
        for (int i = 0; i < n; i ++) {
            scanf("%d", &a0[i]);
            c0[a0[i]]++;
        }

        printf("Game %d:\n", ++t);
        while (true) {
            int flag = false;
            int cntA = 0, cntB = 0;
            memcpy(c2, c0, sizeof(c0));
            memset(c1, 0, sizeof(c1));
            for (int i = 0; i < n; i ++) {
                scanf("%d", &a1[i]);
                if (a1[i]) flag = true;
                c1[a1[i]]++;
                if (a1[i] == a0[i]) {
                    cntA ++;
                    c2[a0[i]] --;
                    c1[a0[i]] --;
                }
            }
            if (flag == false)
                break;
            for (int i = 1; i < M; i ++)
                if (c2[i]) cntB += min(c1[i], c2[i]);
            printf("    (%d,%d)\n", cntA, cntB);
        }
    }

    return 0;
}

---

例3-5 UVA 1583 生成元

思路
当计算过程复杂而且对结果有多次查询时，就应当考虑将计算结果保存成表，从而大大提高查询效率。
这是本题的主要思想。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100000;

int main(void)
{
    int n, a[N+1];
    memset(a, 0, sizeof(a));
    for (int i = 1; i < N; i ++) {
        int m = i, sum = 0;
        while (m) { sum += m%10; m /= 10;}
        n = sum + i;
        if (n <= N && a[n] == 0) a[n] = i;
    }

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        printf("%d\n", a[n]);
    }

    return 0;
}

---

例3-6 UVA 1584 环状序列

思路
此题考查字符串排序。我的做法与书中不同，我是将长度为n字符串s复制一份连接到它的后面成为s2，这样环状序列的所有表示就是s2中所有长度为n的子字符串，用strncmp比较即可。
书中做法和我的方法都避免了n次字符串复制操作。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100;

int main(void)
{
    int t, n;
    char s0[2*N+1], s1[2*N+1];

    cin >> t;
    while (cin >> s0) {
        n = strlen(s0);
        strcpy(s1, s0);
        strcat(s0, s1);
        strcpy(s1, s0);
        int mi = 0;
        for (int i = 0; i < n; i ++) {
            if (strncmp(s0+mi, s1+i, n) > 0)
                mi = i;
        }
        strncpy(s1, s0+mi, n);
        s1[n] = '\0';
        printf("%s\n", s1);
    }

    return 0;
}

---

#习题

习3-1 UVA 1585 得分

思路
用add变量记录当前的O字符连续出现的个数，遇到X清零。
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
    int t;
    char s[81];

    cin >> t;
    while (t--) {
        scanf("%s", s);
        int add = 0, sum = 0;
        for (int i = 0; s[i]; i ++) {
            if (s[i] == 'O') {
                add ++;
                sum += add;
            } else
                add = 0;
        }
        printf("%d\n", sum);
    }

    return 0;
}

---

习3-2 UVA 1586 分子量

思路
考察基本的输入分析，可以先读入整个字符串然后分析。
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const char name[] = "CHON";
double weight[] = {12.01, 1.008, 16.00, 14.01};

int main(void)
{
    int t;
    char s[81];

    cin >> t;
    while (t--) {
        scanf("%s", s);
        int num;
        double sum = 0;
        int i = 0;
        while (s[i]) {
            int j;
            for (j = 0; j < 4; j ++) {
                if (s[i] == name[j]) break;
            }
            i ++;
            num = 1;
            if (isdigit(s[i])) num = (s[i++]-'0');
            if (isdigit(s[i])) num = num*10 + (s[i++]-'0');
            sum += num * weight[j];
        }
        printf("%.3lf\n", sum);
    }

    return 0;
}

---

习3-3 UVA 1225 数数字

思路
这个题暴力搜索也能过，因为数据范围太小。但这样就失去了意义。
我用函数写的，具有较强的普适性。主要思想是对每一位分别分析——当前位、高位、低位分别为指定数字——情况下的数的个数。
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int cnt(int n, int x)
{
    int res = 0;
    int fact = 1, high = n/10, crt = n%10, low = 0;
    while (high || (x && crt >= x)) {
        //printf("%d %d %d %d\n", fact, high, crt, low);
        res += high*fact;
        if (x == 0) res -= fact;
        if (crt > x) res += fact;
        if (crt == x) res += (low+1);
        low += fact*crt;
        crt = high%10;
        high /= 10;
        fact *= 10;
    }
    return res;
}


int main(void)
{
    int t, n;
    cin >> t;
    while (t --) {
        cin >> n;
        for (int i = 0; i < 10; i ++) {
            printf("%d%c", cnt(n, i), i == 9 ? '\n' : ' ');
        }
    }

    return 0;
}

---

习3-4 UVA 455 周期串

思路
字符串的周期一定是长度的约数，根据这个进行枚举就可以了。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main(void)
{
    int t;
    char s[81];

    cin >> t;
    while (t --) {
        scanf("%s", s);
        int i;
        int n = strlen(s);
        for (i = 1; i <= n; i ++) {
            if (n % i) continue;
            bool flag = true;
            for (int j = 1; j < n/i; j ++) {
                for (int k = 0; k < i; k ++) {
                    if (s[k] != s[k+j*i]) {
                        flag = false; break;
                    }
                }
                if (flag == false) break;
            }
            if (flag == true) break;
        }
        printf("%d\n", i);
        if (t) printf("\n");
    }

    return 0;
}

---

习3-5 UVA 227 谜题

思路
这个题我用了两个常量数组，inst数组的作用是将字符翻译成方向数组对应的下标（0-3），方向数组dir的作用是表示四个方向x和y坐标的变化。这样一个循环就ok了，不需要4个方向重复写4次代码。
另外注意最后一组数据后面没有空行，UVA很多题目都要求这样输出。
代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const char inst[] = "ABLR";
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main(void)
{
    int t = 0;
    char s[5][6];
    char c;
    while ((s[0][0] = getchar()) != 'Z') {
        int bi = 0, bj = 0;
        for (int i = 0; i < 5; i ++) {
            for (int j = 0; j < 5; j ++) {
                if (!i && !j) continue;
                s[i][j] = getchar();
                if (s[i][j] == ' ') {bi = i, bj = j;}
            }
            getchar();
        }
        bool legal = true;
        while ((c = getchar()) != '0') {
            if (legal == false || c == '\n') continue;
            int k;
            for (k = 0; k < 4; k ++) {
                if (c == inst[k]) break;
            }
            if (k == 4)
                legal = false;
            else {
                int ni = bi+dir[k][0], nj = bj+dir[k][1];
                if (0 <= ni && ni < 5 && 0 <= nj && nj < 5) {
                    swap(s[bi][bj], s[ni][nj]);
                    bi = ni, bj = nj;
                } else
                    legal = false;
            }
        }
        if (++t > 1) printf("\n");
        printf("Puzzle #%d:\n", t);
        if (legal == false)
            printf("This puzzle has no final configuration.\n");
        else {
            for (int i = 0; i < 5; i ++) {
                for (int j = 0; j < 5; j ++) {
                    printf("%c%c", s[i][j], j == 4 ? '\n' : ' ');
                }
            }
        }
        getchar();
    }

    return 0;
}

---

习3-6 UVA 232 纵横字谜的答案

思路
因为需要编号，应当先扫描并保存起始格的位置，然后分别输出横向和纵向的单词。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10;

int main(void)
{
    int t = 0;
    int n, m;
    char s[N][N+1];
    int cnt = 0;
    int pos[N*N+1][2];
    while (scanf("%d", &n) != EOF && n) {
        scanf("%d", &m);
        getchar();
        cnt = 0;
        memset(pos, 0, sizeof(pos));
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                s[i][j] = getchar();
                if (s[i][j] == '*') continue;
                if (i == 0 || j == 0 || s[i-1][j] == '*' || s[i][j-1] == '*') {
                    pos[cnt][0] = i, pos[cnt][1] = j;
                    cnt ++;
                }
            }
            getchar();
        }

        if (t > 0) printf("\n");
        printf("puzzle #%d:\n", ++t);
        printf("Across\n");
        for (int k = 0; k < cnt; k ++) {
            int i = pos[k][0], j = pos[k][1];
            if (j > 0 && s[i][j-1] != '*') continue;
            printf("%3d.", k+1);
            do {
                printf("%c", s[i][j]);
                j ++;
            } while (j < m && s[i][j] != '*');
            printf("\n");
        }
        printf("Down\n");
        for (int k = 0; k < cnt; k ++) {
            int i = pos[k][0], j = pos[k][1];
            if (i > 0 && s[i-1][j] != '*') continue;
            printf("%3d.", k+1);
            do {
                printf("%c", s[i][j]);
                i ++;
            } while (i < n && s[i][j] != '*');
            printf("\n");
        }
    }

    return 0;
}

---

习3-7 UVA 1368 DNA 序列

思路
找出每列中ACGT出现次数最多的字符，就是最优解序列在这一列的字符值。另外注意要求的是字典序最小的解。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000;
const int M = 50;
char *DNA = "ACGT";

int main(void)
{
    int m, n;
    char s[M][N+1];
    int cnt[N][4];
    int ans[N];
    int d;

    int t;
    cin >> t;
    while (t --) {
        cin >> m >> n;
        for (int i = 0; i < m; i ++)
            scanf("%s", s[i]);

        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                cnt[j][strchr(DNA, s[i][j]) - DNA] ++;
            }
        }
        memset(ans, 0, sizeof(ans));
        d = 0;
        for (int j = 0; j < n; j ++) {
            for (int k = 0; k < 4; k ++) {
                if (cnt[j][k] > cnt[j][ans[j]])
                    ans[j] = k;
            }
            for (int k = 0; k < 4; k ++)
                if (k != ans[j]) d += cnt[j][k];
        }

        for (int j = 0; j < n; j ++)
            putchar(DNA[ans[j]]);
        printf("\n%d\n", d);
    }

    return 0;
}

---

习3-8 UVA 202 循环小数

思路
求循环节需要模拟循环小数的求解过程。那么什么时候会出现循环呢？在除的过程中，除数b是不变的，而被除数a一直在变化，那么当a变换为之前出现过的某个值时，就出现了循环。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 3000;

int main(void)
{
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF) {
        printf("%d/%d = %d.", a, b, a/b);
        a %= b;
        int n = 0;;
        int dec[N+1];
        int arr[N+1];
        bool used[N+1] = {0};
        while (!used[a]) {
            arr[n] = a;
            used[a] = 1;
            a *= 10;
            dec[n] = a/b;
            n++;
            a %= b;
        }
        int m = 0;
        for (m = 0; m < n; m++) {
            if (arr[m] == a) break;
        }

        for (int i = 0; i < m; i++)
            printf("%d", dec[i]);
        printf("(");
        for (int i = m; i < n && i < m+50; i++)
            printf("%d", dec[i]);
        int len = n - m;
        if (len > 50) printf("...");
        printf(")\n   %d = number of digits in repeating cycle\n\n", len);
    }

    return 0;
}

---

习3-9 UVA 10340 子序列

思路
顺序扫描t中字符，遇到与s首字符相同情况即删除s首字符，同时继续往前扫描。当s中字符空时，说明t删除字符可以得到s。
代码

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main(void)
{
    string s1, s2;
    while (cin >> s1 >> s2) {
        int i = 0;
        for (int j = 0; j < s2.size(); j ++) {
            if (s1[i] == s2[j]) i++;
            if (i == s1.size()) break;
        }
        printf("%s\n", i == s1.size() ? "Yes" : "No");
    }

    return 0;
}

---

习3-10 UVA 1587 盒子

思路
这种题目看似简单，但不好写标准统一的代码，而且容易漏掉一些细节而出错。我建议尽量将代码标准化，减少失误的可能。有同学用类的思想处理，有值得借鉴之处。
代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(void)
{
    int a[12];
    while (scanf("%d%d", &a[0], &a[1]) != EOF) {
        if (a[0] > a[1]) swap(a[0], a[1]);
        for (int i = 2; i < 12; i += 2) {
            scanf("%d%d", &a[i], &a[i+1]);
            if (a[i] > a[i+1]) swap(a[i], a[i+1]);
        }
        int b[12];
        memcpy(b, a, sizeof(a));
        sort(a, a+12);

        bool flag = true;
        int n[3];
        for (int i = 0; i < 3; i ++) {
            n[i] = a[i*4];
            for (int j = 1; j < 4; j ++) {
                if (n[i] != a[i*4+j])
                    flag = false;
            }
        }

        int m[3] = {0};
        for (int i = 0; i < 12; i += 2) {
            if (m[0] < 2 && b[i] == n[0] && b[i+1] == n[1]) m[0] ++;
            else if (m[1] < 2 && b[i] == n[0] && b[i+1] == n[2]) m[1] ++;
            else if (m[2] < 2 && b[i] == n[1] && b[i+1] == n[2]) m[2] ++;
            else flag = false;
        }
        if (! (m[0] == 2 && m[1] == 2) )
            flag = false;
        //printf("%d %d %d\n", m[0], m[1], m[2]);

        if (flag)
            printf("POSSIBLE\n");
        else
            printf("IMPOSSIBLE\n");
    }

    return 0;
}

---

习3-11 UVA 1588 换低档装置

思路
此题同上题一样，在标准化方面有一定困难。我一开始写的程序能通过用例，但死活就一直WA。
这段代码是参考别人的写的，其代码比较规范，值得推荐。
代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s1[110], s2[110];

int test(int k, char s1[], char s2[]) {
    for (int i = 0; s1[k+i] && s2[i]; i++)
      if (s1[k+i]+s2[i]-2*'0' > 3) return 0;
    return 1;
}

int fun(char s1[], char s2[]) {
    int k = 0;
    while (!test(k, s1, s2)) k++;
    return max(strlen(s1), strlen(s2)+k);
}

int main() {
    while (scanf("%s%s", s1, s2) != EOF) {
        printf("%d\n", min(fun(s1, s2), fun(s2, s1)));
    }
    return 0;
}

---

习3-12 UVA 11809 浮点数（未通过）

思路
我的做法是根据最大十进制数反推二进制表示中的M和E，例子都过了，但是提交后TLE。搜了一下其他人的解法，清一色的打表。这个题的M和E范围确实有限，打表只需要预先计算300个并保存，然后查表即可。
估计这个题的查询量比较大吧，否则我直接求应该也可以的。
有时间重新写一个打表的程序把这题AC掉，先贴上我的TLE代码。看到本文的大神如有指导也请不吝赐教。
代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

const double EPS = 1e-6;

int main()
{
    double a;
    while (scanf("%lf", &a) != EOF) {
        if (abs(a) < EPS) break;
        int y = 0;
        while (a >= 1) {
            a /= 2;
            y++;
        }

        int m = 0;
        a = 1-a;
        while (abs(a-1) > EPS) {
            a = a*2;
            m ++;
        }

        int e = 0;
        while (y) {
            e++;
            y /= 2;
        }

        printf("%d %d\n", m-1, e);
    }

    return 0;
}

----------)