《算法竞赛入门经典》 第3章 数组和字符串

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 3.1 逆序输出
#define maxn 105
int a[maxn];

    int x, n = 0;
    while (scanf("%d", &x) == 1) {
        a[n++] = x;
    }
    for (int i = n - 1; i >= 1; i--) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[0]);


//测试的时候可以改为这样，方便中断程序
    while (scanf("%d", &x) == 1 && x != -1) 

1 2 3 4 5 6 -1
6 5 4 3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 3.2 开灯问题
#define maxn 1010
int a[maxn];

    int n, k, first = 1;
    memset(a, 0, sizeof(a));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (j % i == 0) a[j] = !a[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i]) {
            if (first) first = 0;
            else printf(" "); 
            printf("%d", i);
        }
    }
    printf("\n");

7 3
1 5 6 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 蛇形填数
    int a[20][20];
    int n, x, y, tot = 0;
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    tot = a[x = 0][y = n - 1] = 1;
    while (tot < n * n) {
        while (x + 1< n && !a[x + 1][y]) a[++x][y] = ++tot;
        while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++tot;
        while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++tot;
        while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++tot;
    }
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++) 
            printf("%3d", a[x][y]);
        printf("\n");
    }

4
 10 11 12  1
  9 16 13  2
  8 15 14  3
  7  6  5  4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 3.4 竖式问题
    int cnt = 0;
    char s[20], buf[99];
    scanf("%s", s);
    for (int abc = 111; abc <= 999; abc++) {
        for (int de = 11; de <= 99; de++) {
            int x = abc * (de % 10), y = abc * (de / 10), z = abc * de;
            sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);
            int ok = 1;
            for (int i = 0; i < strlen(buf); i++) {
                if (strchr(s, buf[i]) == NULL) ok = 0;
            }
            if (ok) {
                printf("<%d>\n", ++cnt);
                printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z);
            }
        }
    }
    printf("The number of solution = %d\n", cnt);


2357
<1>
  775
X  33
-----
 2325
2325
-----
25575

The number of solution = 1

竞赛题目选讲

3-1 UVa272 Tex Quotes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
    int c, q = 1;
    while ((c = getchar()) != EOF) {
        if (c == '"') {
            printf("%s", q ? "``" : "''");
            q = !q;
        } else {
            printf("%c", c);
        }
    }

    return 0;
}

"To be or not to be," quoth the Bard, "that is the question".
``To be or not to be,'' quoth the Bard, ``that is the question''.

3-2 UVa10082 WERTYU

1
2
3
4
5
6
7
8
9
10
11
12
13
char s[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

int main() {
    int i, c;
    while ((c = getchar()) != EOF) {
        for (i = 1; s[i] && s[i] != c; i++);
        if (s[i]) putchar(s[i - 1]);
        else putchar(c);
    }
}

O S, GOMR YPFSU/
I AM FINE TODAY.

for (i = 1; s[i] && s[i] != c; i++);

c是键盘上打不出的字符（c不在s字符数组里）,直接输出c。

else putchar(c);

如果c = s[i],找出c在键盘中的位置,s的下标,然后输出前一个字符.

if (s[i]) putchar(s[i - 1]);

3-3 UVa401 Palindromes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const char* res = "A   3  HIL JM O   2TUVWXY51SE Z  8 ";
const char* msg[] =  {"not a palindrome","a regular palindrome","a mirrored string","a mirrored palindrome"};
char r(char ch) {
    if (isalpha(ch)) return res[ch - 'A'];
    return res[ch - '0' + 25];
}

int main() {
    char s[300];
    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        int p = 1, m = 1;
        for (int i = 0; i < (len + 1 / 2); i++) {
            if (s[i] != s[len - i - 1]) p = 0; // 不是回文串
            if (r(s[i]) != s[len - i - 1]) m = 0; // 不是镜像串
        }
        printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);
    }
}

NOTAPALINDROME
NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI
ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS
2A3MEAS -- is a mirrored string.

ATOYOTA
ATOYOTA -- is a mirrored palindrome.

3-4 UVa340 Master-Mind Hints

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define maxn 1010

int main() {
    int n, a[maxn], b[maxn];
    int kase = 0;
    while (scanf("%d", &n) == 1 && n) {
        printf("Game %d:\n", ++kase);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        for (; ;) {
            int A = 0, B = 0;
            for (int i = 0; i < n; i++) {
                scanf("%d", &b[i]);
                if (a[i] == b[i]) A++;
            }
            if (b[0] == 0) break;
            for (int d = 1; d <= 9; d++) {
                int c1 = 0, c2 = 0;
                for (int i = 0; i < n; i++) {
                    if (a[i] == d) c1++;
                    if (b[i] == d) c2++;
                }
                if (c1 < c2) B += c1;
                else         B += c2;
            }
            printf("    (%d,%d)\n", A, B - A);
        }
    }
    return 0;
}

3-5 UVa1583 Digit Generator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define maxn 100005
int ans[maxn];

int main() {
    int T, n;
    memset(ans, 0, sizeof(ans));
    for (int m = 1; m < maxn; m++) {
        int x = m, y = m;
        while (x > 0) {
            y = y + x % 10;
            x = x / 10;
        }
        if (ans[y] == 0 || m < ans[y]) ans[y] = m;
    }
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
}

3-6 UVa1584 Circular Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define maxn 105

int Less(const char* s, int p, int q) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (s[(p + i) % n] != s[(q + i) % n]) {
            return s[(p + i) % n] < s[(q + i) % n];
        }
    }
    return 0;
}

int main() {
    int T;
    char s[maxn];
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        int ans = 0;
        int n = strlen(s);
        for (int i = 1; i < n; i++) {
            if (Less(s, i, ans)) ans = i;
        }
        for (int j = 0; j < n; j++) {
            putchar(s[(j + ans) % n]);
        }
        putchar('\n');
    }
}