首页 > 代码库 > 紫书第三章数组和字符串

紫书第三章数组和字符串

2024-07-15 04:25:49 225人阅读

1 序

系统的整理下第三章的学习笔记。例题代码是在未看书本方法前自己尝试并AC的代码，不一定比书上的标程好；习题除了3-8百度了求解方法，其它均独立完成后，会适当查阅网上资料进行整理总结。希望本博文方便自己日后复习的同时，也能给他人带来点有益的帮助（建议配合紫书——《算法竞赛入门经典（第2版）》阅读本博客）。有不足或错误之处，欢迎读者指出。

2 例题

2.1 UVa272--Tex Quotes

#include <stdio.h>

int main() {
    bool logo = 1;
    char ch;

    while ((ch = getchar()) != EOF) {
        if (ch == '\"') {
            if (logo) printf("``");
            else printf("''");
            logo ^= 1;
        }
        else putchar(ch);
    }

    return 0;
}

第9~10行：我本来是用puts来输出``和‘‘，发现会自带换行符，所以用printf的%s输出，LRJ的代码是用了这技巧：q?"``":"‘‘"。
第11行：LRJ的标记变量是用q = !q来实现状态变换，我这里用异或位运算效率更高。

2.2 UVa10082--WERTYU

第一次遇这种题，以为是要用if来暴力做的变态题，然后才发现常量数组的妙用。如果不是小白书看过，真的写不出来。

注意转义字符‘\‘要写成‘\\‘，下面是第一次AC的代码。

#include <stdio.h>

char str[4][50] = {"`1234567890-=", "QWERTYUIOP[]\\",
                "ASDFGHJKL;'", "ZXCVBNM,./"};
int main() {
    int a[200], i, j;

    for (i = 0; i < 4; i++)
        for (j = 1; a[str[i][j]] = str[i][j-1]; j++);
    a[' '] = ' '; a['\t'] = '\t'; a['\n'] = '\n';
    while ((i = getchar()) != EOF) putchar(a[i]);
    return 0;
}

第9行：用相当于“哈希映射”的方式，把每个输入字符(str)，应该匹配的数值存到一个数组(a)。
第11行：这样用getchar循环读入i，对应输出a[i]就行了。

看了白书后，发现自己的办法有些复杂了（虽然效率上高一点）。为什么要分四个子串呢？完全可以合并成一行，然后用一个循环找，找到后输出前一个字符，找不到就原样输出，避免了原代码中第10行的操作。不过我的方法紫书后续也提到了，下面是我综合下优化后的代码：

#include <stdio.h>
char str[200] = {"`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./  \t\t\n\n"};
int main() {
    int a[200], i;
    for (i = 1; a[str[i]] = str[i-1]; i++);
    while ((i = getchar()) != EOF) putchar(a[i]);
    return 0;
}

第2行：注意末尾的空格、制表符、回车三个字符各连写了两个，这样不用像上次那样多写了第10行。

2.3 UVa401--Palindromes

这题以前小白书做过，写了很久，不够最后的代码还是挺精炼的。

#include <stdio.h>
#include <string.h>

char s[100], key1[] = "AEHIJLMOSTUVWXYZ12358", key2[] = "A3HILJMO2TUVMXY51SEZ8", *p;

int ispal()
{
	int i = 0, j = strlen(s) - 1;
	while (i < j) if (s[i++] != s[j--]) return 0;
	return 1;
}

int ismir()
{
	int i = -1, j = strlen(s);
	while (++i <= --j)
	{
		p = strchr(key1, s[i]);
		if (p) { if (s[j] != key2[p-key1]) return 0;}
		else return 0;
	}
	return 1;
}

int main()
{
	int t;
	while (scanf("%s", s) != EOF)
	{
		t = ismir();
		printf("%s -- is ", s);
		if (ispal()) printf("%s", t?"a mirrored palindrome":"a regular palindrome");
		else printf("%s", t?"a mirrored string":"not a palindrome");
		printf(".\n\n");
	}
	return 0;

}

关键是如何判断镜像性质：

用两个字符数组存储镜像字符的映射关系。（思想同上题）
没考虑到最中间的字符也要判断是否水平翻转后为其本身，WA几次。（只需略修改循环条件）
学习strchr函数。（该函数找不到字符时返回空指针NULL）

LRJ的代码分析：
首先回文串部分LRJ直接在main里判断，我的话没必要为了精简代码而复杂了思维，分成两个子函数不易出错。我的看似短，但总体思路更易于理解。
我是用指针来对应到左右两端，往中间移。LRJ是用下标索引，左是i，右边自然是len-1-i，两种方法都行。
至于他的r函数，正是利用了题目说没有空白输入的特性，写了那个rev字符串，然后将字符直接反转比较。因为字符串肯定没有空格，而反转后非法的字符，在LRJ代码里就变成空格了，肯定匹配不了，所以能巧妙的解决问题！

2.4 UVa340--Master-Mind Hints

这题小白书也做过，因为数字只有1~9，只要统计每个数字出现的次数，减去强匹配的数量就行。思路同书本但没有那么精简，就不贴代码了。

2.5 UVa1583--Digit Generator

思路与书本一样。

#include <stdio.h>

int y[100100];

int main() {
    for (int i = 0; i < 100000; i++) {
        int s = i, t = i;
        while (t) { s+=t%10; t/=10;}
        if (y[s] == 0) y[s] = i;
    }

    int T, pos;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &pos);
        printf("%d\n", y[pos]);
    }
    return 0;
}

2.6 UVa1584--Circular Sequence

题目：输入一个长度在2~100的字符串，要理解成环状，然后能从任意地方作为起点生成一个新的同长度字符串，问这些字符串中字典序最小的是哪个。

分析与求解：字符串的比较可以使用strcmp函数，将要比较的两个字符串首地址，即指针传入即可。那么，我们可以用一个min_p的值来存储当前字典序最小的字符串起始下标，用i来遍历1~len-1的起始下标，因为是环状，所以每轮i循环，都在字符串y末尾添加对应的字符，并添加‘\0‘方便strcmp的调用。
方法跟紫书不一样。具体思路和细节，与strcmp的灵活使用，读者可以自己分析思考。

#include <stdio.h>
#include <string.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        char y[300];
        scanf("%s", y);

        int len = strlen(y), i, min_p = 0;
        for (i = 0; i < len; i++) {
            y[i+len] = y[i];
            y[i+len+1] = 0;
            if (strcmp(y+min_p,y+i+1) > 0)
                min_p = i+1;
        }
        y[min_p+len] = 0;
        printf("%s\n", y+min_p);
    }
    return 0;
}

3 习题

3.1 UVa1585--Score

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        char s[100];
        scanf("%s", s);

        int sum = 0, cnt = 0;
        for (int i = 0; s[i]; i++) {
            if (s[i]=='X') {
                sum += cnt*(cnt+1)/2;
                cnt = 0;
            }
            else cnt++;
        }
        printf("%d\n", sum+cnt*(cnt+1)/2);
    }
    return 0;
}

每遇到X做一次更新，否则cnt++，注意第19行最后还要一次更新。

看了这段代码：http://blog.csdn.net/sinat_17231979/article/details/36869231后，发现还是想复杂了，没必要用前n项和公式，直接用一个变量记录当前有多少个O就行了：

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        char s[100];
        scanf("%s", s);

        int sum = 0, cnt = 0;
        for (int i = 0; s[i]; i++) {
            if (s[i]=='X') cnt = 0;
            else {
                cnt++;
                sum += cnt;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

3.2 UVa1586--Molar Mass

暴力每一位i，如果i+1位是数字，判断i+2位是不是数字，分情况计算数量；如果i+1位不是数字，那么数量就是默认的1。接着判断第i位是不是字母，不是则continue，否则累加相应的质量。

#include <stdio.h>
#include <ctype.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        char s[100];
        scanf("%s", s);

        double sum = 0, w;
        for (int i = 0; s[i]; i++) {
            // 算出后两位所代表的数值
            if (isdigit(s[i+1])) {
                if (isdigit(s[i+2])) w = 10*(s[i+1]-'0')+s[i+2]-'0';
                else w = s[i+1] - '0';
            }
            else w = 1;

            // 判断第一位
            if (!isalpha(s[i])) continue;
            else if (s[i] == 'C') sum += 12.01*w;
            else if (s[i] == 'H') sum += 1.008*w;
            else if (s[i] == 'O') sum += 16.00*w;
            else sum += 14.01*w;
        }
        printf("%.3lf\n", sum);
    }
    return 0;
}

3.3 UVa1225--Digit Counting

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        int N, i, t, a[10] = {};
        scanf("%d", &N);

        for (i = 1; i <= N; i++) {
            t = i;
            while (t) a[t%10]++, t/=10;
        }
        for (i = 0; i < 9; i++) printf("%d ", a[i]);
        printf("%d\n", a[9]);
    }
    return 0;
}

直接每组暴力都能过。如果会TLE，也可以建立二维数组a[10000][10]，先暴力一轮求出数据。后面只要打表就行了。

3.4 UVa455--Periodic Strings

算一个字符串的周期，其周期一定是长度的约数，按这一点枚举，并写一个判断T是不是一个字符串的周期的函数（isThePeriod）即可。

输入格式略坑，每两组测试间会有一个空行，所以我用第19行那样的方式解决。

最后注意输出格式，也要每两个隔一个空行~~~

#include <stdio.h>
#include <string.h>

int isTthePeriod(char s[], int T) {
    for (int i = 0; i < T; i++) {
        for (int j = i+T; j < strlen(s); j+=T)
            if (s[i] != s[j]) return 0;
    }
    return 1;
}

int main() {
    int T, kase, len, i;
    scanf("%d", &T);

    for (kase = 1; kase <= T; kase++)
    {
        char s[100];
        while (scanf("%s", s), len = strlen(s), !len);

        for (i = 1; i <= len; i++)
            if (len%i == 0 && isTthePeriod(s,i)) break;
        if (kase != 1) putchar('\n');
        printf("%d\n", i);
    }
    return 0;
}

3.5 UVa227--Puzzle

这题稍微有些麻烦了，模拟操作，我尽量进行了些优化，而且为了方便交换变量，用了C++里algorithm的swap，没有自己写交换函数。

【基本框架】

将5*5网格定义为全局变量s（从1开始编号），当前空格所在行列为x,y

output函数用来输出s的矩阵形式

ok用来操作一个命令为ch的移动，返回值1代表操作成功，返回0代表失败。成功的话，要更新相应的x、y和进行交换操作swap

test用来完成每组测试的操作

总结：对于复杂的问题，要想清思路，然后把大问题划分成一个个小的子问题去求解。

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

int x, y;
char s[6][6];

void output() {
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j < 5; j++)
            printf("%c ", s[i][j]);
        printf("%c\n", s[i][5]);
    }
}

int ok(char ch) {
    switch (ch) {
    case 'A':
        if (x == 1) return 0; else x--;
        swap(s[x][y], s[x+1][y]); break;
    case 'B':
        if (x == 5) return 0; else x++;
        swap(s[x][y], s[x-1][y]); break;
    case 'L':
        if (y == 1) return 0; else y--;
        swap(s[x][y], s[x][y+1]); break;
    case 'R':
        if (y == 5) return 0; else y++;
        swap(s[x][y], s[x][y-1]); break;
    }
}

int test() {
    char ch;
    int i, j;
    for (i = 1; i <= 5; i++) for (j = 1; j <= 5; j++)
        if (s[i][j] == ' ') x = i, y = j;

    while ((ch = getchar()) != '0') {
        if (ch == '\n') continue;
        if (!ok(ch)) {  // 非法操作，仍要清掉字符'0'前的值
            while (getchar() != '0');
            return 0;
        }
    }

    return 1;
}

int main() {
    int kase, i, j;

    for (kase = 1; ; kase++) {
        gets(&s[1][1]);
        if (s[1][1] == 0) {kase--; continue;}   // 注意此处读到空串，要忽略读入continue
        if (s[1][1] == 'Z' && s[1][2] == 0) break;

        if (kase != 1) putchar('\n');
        printf("Puzzle #%d:\n", kase);
        for (i = 2; i <= 5; i++) gets(&s[i][1]);
        if (test()) output();
        else printf("This puzzle has no final configuration.\n");
    }
    return 0;
}

3.6 UVa232--Crossword Answers

这题就是像中学英语填单词的那种网格。需要对起始点编号，然后按行输出、再按列输出所有单词。

#include <stdio.h>
#include <string.h>
int main() {
    int n, m, a[15][15], k, i, j;
    char s[15][15];

    for (int kase = 1; ; kase++) {
        if (scanf("%d%d ", &n, &m) != 2) break;

        k = 0;
        memset(a, 0, sizeof(a));
        memset(s, 0, sizeof(s));

        for (i = 1; i <= n; i++) gets(&s[i][1]);
        for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) {
            if (s[i][j] == '*') s[i][j] = 0;
            if (!(s[i-1][j]&&s[i][j-1]) && s[i][j]) a[i][j] = ++k;
        }

        if (kase != 1) putchar('\n');
        printf("puzzle #%d:\nAcross\n", kase);
        for (i = 1; i <= n; i++) for (j = 1; j <= m; j++)
            if (s[i][j] && !s[i][j-1]) printf("%3d.%s\n", a[i][j], s[i]+j);
        printf("Down\n");
        for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) {
            if (s[i][j] && !s[i-1][j]) {
                printf("%3d.", a[i][j]);
                for (k = i; s[k][j]; k++) putchar(s[k][j]);
                putchar('\n');
            }
        }
    }
    return 0;
}

3.7 UVa1368--DNA Consensus

思路：找出每列中ACGT出现次数最多的字符，就是最优解序列在这一列的字符值。

#include <stdio.h>
#include <string.h>

inline int c2d(char c) {
    if (c == 'A') return 0;
    else if (c == 'C') return 1;
    else if (c == 'G') return 2;
    else return 3;
}

inline int d2c(int d) {
    if (d == 0) return 'A';
    else if (d == 1) return 'C';
    else if (d == 2) return 'G';
    else return 'T';
}

int main() {
    int T, m, n, i, j, a[1010][4], sum;
    char s[50][1010];
    scanf("%d", &T);

    while (scanf("%d%d ", &m, &n) == 2) {
        for (i = 0; i < m; i++) gets(s[i]);
        memset(a, 0, sizeof(a));
        for (i = 0; i < m; i++) for (j = 0; j < n; j++)
            a[j][ c2d(s[i][j]) ]++;
        for (sum = j = 0; j < n; j++) {
            int the_max = a[j][0], id = 0;
            for (i = 1; i < 4; i++) if (a[j][i]>the_max)
                id = i, the_max = a[j][i];
            putchar(d2c(id));
            sum += m - the_max;
        }
        printf("\n%d\n", sum);
    }
    return 0;

}

3.8 UVa202--Repeating Decimals

这题需要模拟除法，当出现相同的余数时，就代表循环点的出现。下面我以5/7为例详细的讲下思路。

如上图，第0步，分子是5，分母是7（分母在整个除法中始终不变），5/7的商是0，代表这个除法的整数部分是0,，余数是5，乘以10，得50作为第1步的分子；50/7的商为7，代表这个除法的第一位小数是7，余数是1，乘以10，得10作为第2步的分子...可以发现每步的除法只跟分子有关，也就是当分子出现重复值，如上图第1步和第7步的分子值都为50时，第7步后面的运算其实是在重复第1步至第6步间的运算。所以第1步至第7步就是一个循环节。

程序实现中，可以不用存储余数的值，只需存储上图中的分子和商，我定义了A[2][3010]，用A[0][j]存储第j步的分子，A[1][j]存储第j步的商。注意最后的数值由商可以直接构成，如上图的红色字体，数值为0.7142857142...

#include <stdio.h>

int A[2][3010], p, q;

// 找i位之前是否有重复分子出现;有则返回周期，否则返回-1.
inline int myfind() {
    for (p = 1; p < q; p++) {
        if (A[0][p] == A[0][q])
            return q - p;
    }
    return -1;
}

int main() {
    int kase, a, b, i, len;
    for (kase = 1; scanf("%d%d", &a, &b) != EOF; kase++) {
        A[0][0] = a; A[1][0] = a/b;
        for (q = 1; ; q++) {
            A[0][q] = (A[0][q-1] - b*A[1][q-1])*10;
            A[1][q] = A[0][q]/b;
            len = myfind();
            if (len > 0) break;
        }
        printf("%d/%d = %d.", a, b, A[1][0]);
        for (i = 1; i < p; i++) printf("%d", A[1][i]);
        putchar('(');
        for (i = p; i < q; i++) {
            if (i > 50) {
                printf("...");
                break;
            }
            printf("%d", A[1][i]);
        }
        printf(")\n   %d = number of digits in repeating cycle\n\n", len);
    }

}

3.9 UVa10340--All in All

遍历后者，找前者往后是否有对应的字符。

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

int fun(string& a, string& b) {
    int i, j = 0;
    for (i = 0; i < a.size(); i++, j++) {
        while (j < b.size() && a[i]!=b[j]) j++;
        if (j == b.size()) return 0;
    }
    return 1;
}

int main() {
    string a, b;
    while (cin >> a >> b) {
        if (fun(a,b)) cout << "Yes\n";
        else cout << "No\n";
    }
}

3.10 UVa1587--Box

只要用一堆疯狂的条件分支就能解答此题了：http://blog.csdn.net/u013451221/article/details/37672039。不过这里我更乐意把数据“标准化”，然后用C++构造“Face类”来求解。

首先构造一个宽w一定不小于高h的“面类(Face)”，并且按h为第一级，w为第二级准则从小到大排序。如果是能组成长方体的，边长肯定只有三种值，不妨设从小到大依次为a,b,c。则输入的6个面排序后，一定满足以下分布：

首先每种面肯定都出现了两次，即编号0、1相同，编号2、3相同，编号4、5相同。把这个准则，设计为测试函数test1。

接下来，编号0的h一定与编号2的h相等，编号0的w一定与编号4的h相等，编号2的w一定与编号4的w相等。把这个准则，设计为测试函数test2。

满足上述两个测试，是数据能组合成长方体的充要条件。

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

struct Face{
    int h, w;
    void make(int x, int y) {
        h = min(x,y);
        w = max(x,y);
    }
    bool operator < (const Face& b) const {
        if (h == b.h) return w < b.w;
        else return h < b.h;
    }
    bool operator == (const Face& b) const {
        return (h == b.h) && (w == b.w);
    }
};
vector<Face> A(6);

int test1() {
    for (int i = 0; i < 6; i += 2) if (!(A[i]==A[i+1])) return 0;
    return 1;
}

int test2() {
    if (A[0].h==A[2].h && A[0].w==A[4].h && A[2].w==A[4].w) return 1;
    else return 0;
}

int main() {
    int x, y;
    while (cin >> x >> y) {
        A[0].make(x, y);
        for (int i = 1; i < 6; i++) {
            cin >> x >> y;
            A[i].make(x, y);
        }
        sort(A.begin(), A.end());
        if (test1() && test2()) cout << "POSSIBLE\n";
        else cout << "IMPOSSIBLE\n";
    }
    return 0;

}

3.11 UVa1588--Kickdown

假设固定装置s1，那么装置s2只要初始状态左端与s1左端对齐（该状态用偏移量k=0来标记），然后测试k=0时，两个装置是不是”每一位的和都不会超过3“就行了，如果不行就k++，继续往右边偏移进行测试。可以知道肯定存在着一个k能使其成立的（也就是s2左端接在s1右端时）。用这种方式遍历，找到的第一个可行解就是最佳解。

不过上述讨论还遗漏了一种组合方式，就是s2也可以往左偏移。其实将上述解法写成一个fun函数进行封装，外界（main函数）只要巧妙的利用对称性，就能重复利用上一段的代码了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int len1, len2;
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 UVa11809--Floating-Point Numbers

首先要知道二进制小数的原理：

本题的思路就是先把所有的M、E对应的值算出来，记为矩阵C，其中C[M,E]=尾数M、阶码E对应的最大值。然后对于输入的AeB,找出C中与其相等的值所在的行M、列E即是答案。

不过这里有两个要点。一是这个数值太大，可以达到2^(2^30-1)，远超了double的存储范围。所以我们不妨对数值做一个变换，取以10为底的对数值来存储。二是计算过程的舍尾误差与double本身存在的误差会导致精度问题。所以可以在矩阵C中找与输入值最接近的作为匹配点，也就是差值的绝对值最小。
最后还有M=0，E=1的特殊点，在程序中会出现0.0-0.0<0.0条件为否的错误，导致pi,pj无法更新，这个问题只要把pi、pi分别初始化为0、1就能解决了。

#include <math.h>
#include <stdio.h>
#include <string.h>

double C[10][31];

void init() {
    int i, j, v;
    double f[10] = {0.5}, g[31], t;

    for (i = 1, t = 0.5; i < 10; i++) {
        f[i] = f[i-1] + t/2;
        t /= 2;
    }
    for (i = 0; i < 10; i++) f[i] = log10(f[i]);
    for (i = 1, v = 2; i <= 30; i++) {
        g[i] = (v - 1.0)*log10(2.0);
        v <<= 1;
    }
    for (i = 0; i < 10; i++) for (j = 1; j <= 30; j++)
        C[i][j] = f[i] + g[j];
}

int main() {
    int i, j;
    char s[100], *p;
    double A, B;

    init();

    while (scanf("%s", s), strcmp(s, "0e0")) {
        p = strchr(s, 'e');
        *p = 0;                 // 将'e'所在位置变为'\0'
        sscanf(s, "%lf", &A);
        sscanf(p+1, "%lf", &B);

        int pi = 0, pj = 1;
        B = A = log10(A) + B;   // 接下来A存储表达式值，B记录差值
        for (i = 0; i < 10; i++) for (j = 1; j <= 30; j++)
        if (fabs(A-C[i][j]) < B) pi = i, pj = j, B = fabs(A-C[i][j]);
        printf("%d %d\n", pi, pj);
    }
    return 0;
}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 紫书第三章 数组和字符串

紫书第三章 数组和字符串

1 序