算法竞赛入门经典（第2版）—第三章

零碎知识点整理

• isalpha(a)判断字符a是否为字母，返回值非0表示a是字母，否则不是字母。isdigit(a)判断字符a是否为数字。isupper(a)判断字符a是否为大写英文字母。islower(a)判断字符a是否为小写英文字母。toupper(a)将字符a转换为大写字母，tolower(a)将字符a转换为小写字母。注意头文件为<cctype>或<ctype.h>。

题目

340 - Master-Mind Hints（数组统计）

题目链接：340 - Master-Mind Hints
参考博文：340 - Master-Mind Hints

• 题目大意：题意过于复杂。大概如下，先输入一个n，为序列长度。然后是若干行数据，第一行是答案序列，接下来的若干行是猜测序列，以一组都为0的数位结尾。此为一组数据。所有数据的结尾，会有一个“0”做为标记。找到答案序列和猜测序列之间，两序列相同位置拥有相等数字的组数A，并找到两序列都拥有该数字B，但位置不对应的组数。输出是用格式为(A,B)。
• 思路：重点是找出A后，根据A找出B。找B时需要寻找储存答案序列和猜测序列各个数值的个数，然后根据取二者值最小者，累加后，在减去A即可得到B。避免了搜索的复杂运算。

代码：

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

const int MAX = 1005;
int N, a[MAX], b[MAX], n1[15], n2[15];
int main()
{
    int T = 1;
    while(scanf("%d", &N)!=EOF && N)
    {
        memset(n1, 0, sizeof(n1));
        for(int i=0; i<N; i++)
        {
            scanf("%d", &b[i]);
            n1[b[i]]++;
        }
        printf("Game %d:\n", T++);
        while(1)
        {
            int A = 0, B = 0;
            memset(n2, 0, sizeof(n2));
            for(int i=0; i<N; i++)
            {
                scanf("%d", &a[i]);
                n2[a[i]]++;
                if(b[i]==a[i]) A++;
            }
            if(!a[0]) break;
            for(int i=1; i<10; i++)
            {
                B += min(n1[i], n2[i]);
            }
            B -= A;
            printf("    (%d,%d)\n", A, B);
        }
    }
    return 0;
}

1583 - Digit Generator（预处理，查表）

题目链接：1583 - Digit Generator

• 题目大意：输入一个数，找出这个数的最小生成元。
  生成元的意思是：一个整数，比如245，它本身加上它各位数之和等于256 (= 245 + 2 + 4 + 5)，则245就是256的一个生成元。
• 思路：有两种方法，一个是打表，即遍历出0-100000范围内的所有生成元，并将其与对应的数建立映射，则在输入该数时，直接可得该数的生成元。第二种方法是枚举，但是对于数字d，可以只枚举max(0, d-50)-d范围内的数字（从生成元的定义和范围可知）。
  代码：
  打表法：
  参考博文：1583 - Digit Generator
  枚举法：

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

int T, d;
bool check(int n, int t)
{
    int a = n, b = n;
    while(b)
    {
        a += b%10;
        b /= 10;
    }
    if(a==t) return 1;
    else     return 0;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &d);
        int flag = 0;
        int st = max(0, d-50);
        for(int i=st; i<d; i++)
        {
            if(check(i, d))
            {
                flag = i;
                break;
            }
        }
        if(!flag) printf("0\n");
        else      printf("%d\n", flag);
    }
    return 0;
}

1584 - Circular Sequence（字典序）

题目链接：1584 - Circular Sequence

• 题目大意：输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）的一种表示法，你的任务是输出该环状串的最小字典序表示。例如，CTCC的最小表示是CCCT，CGAGTCAGCT的最小表示为AGCTCGAGTC。
• 思路：遍历字符串中所有的字符，以该字符为起始，然后比较得出最小的字典序开始的字符下标。

代码：

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

int len, T;
char s[101];

//比较以p开始的字符串和q开始的字符串那个字典序小
int Less(char s[], int p, int q)
{
    for(int i=0; i<len; i++)
    {
        if(s[(p+i)%len]!=s[(q+i)%len])
            return s[(p+i)%len]<s[(q+i)%len];
    }
    return 0;//相等
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", s);
        int ans = 0;
        len = strlen(s);
        for(int i=1; i<len; i++)
        {
            if(Less(s, i, ans)) ans = i;
        }
        for(int i=0; i<len; i++)
        {
            printf("%c", s[(i+ans)%len]);
        }
        printf("\n");
    }
    return 0;
}