Algorithm in ACM Mode
#C#algorithm 2024-02-11

Some exercise in the basic algorithm focuses on getting familiar with the ACM mode.

题目网址：https://kamacoder.com

编程语言：C

  1. A+B问题I
1
2
3
4
5
6
7
8
9
#include<stdio.h>

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) == 2) {
        printf("%d\n", a+b);
    }
    return 0;
}
  1. A+B问题II
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>

int main() {
    int n, a, b;
    while(scanf("%d", &n) == 1){
        while(n > 0){
            scanf("%d %d", &a, &b);
            printf("%d\n", a+b);
            n--;
        }
    }
    return 0;
}
  1. A+B问题III
1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>

int main() {
    int a, b;
    while(1){
        scanf("%d %d", &a, &b);
        if (a == b && a == 0) break;
        printf("%d\n", a+b);
    }
    return 0;
}
  1. A+B问题IV
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
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main() {
    int n, i;
    char letter;
    char input[100];

    scanf("%d", &n);
    getchar();
    for (i = 0; i < n; i++) {
        fgets(input, sizeof(input), stdin);

        char* ptr = input;
        while(*ptr != '\n' && *ptr != '\0') {
            sscanf(ptr, "%c", &letter);
            printf("%c", letter - 32);
            while(*ptr&&!isspace(*ptr)) ++ptr;
            while(*ptr&&isspace(*ptr)) ++ptr;
        }

        printf("\n");
    }
    return 0;
}
  1. A+B问题VII(不知道题号怎么跳了)
1
2
3
4
5
6
7
8
9
10
#include<stdio.h>

int main() {
    int a, b;
    while (1) {
        if (scanf("%d %d", &a, &b) != 2) break;
        printf("%d\n\n", a+b);
    }
    return 0;
}
  1. A+B问题VIII
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>

int main() {
    int n, m, num, sum;
    while(1) {
        if (scanf("%d", &n) != 1) break;
        while (n > 0) {     // n组数字
            scanf("%d", &m);

            sum = 0;
            while(m > 0) {  // m个数字求和
                scanf("%d", &num);
                sum += num;
                m--;
            }
            printf("%d\n", sum);

            if (n > 1) printf("\n");
            n--;
        }
    }
    return 0;
}
  1. 平均绩点(出现错误，暂未发现原因：“潜在的数组或指针越界，请检查代码。”)
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<ctype.h>

int main() {
    char level;
    float sum, n;
    int flag;

    while(1) {
        flag = 1;
        sum = 0;
        n = 0;
        level = getchar();
        while (level != '\n') {
            if (!isspace(level)) {  // 判断是否为空格
                switch (level)
                {
                case 'A':
                    sum += 4;
                    n += 1;
                    break;
                case 'B':
                    sum += 3; 
                    n += 1;
                    break;
                case 'C':
                    sum += 2;
                    n += 1;
                    break;
                case 'D':
                    sum += 1;
                    n += 1;
                    break;
                case 'F':
                    sum += 0;
                    n += 1;
                    break;
                default:    // 有除A/B/C/D/F以外的字母出现
                    printf("Unknown\n");
                    flag = 0;
                    break;
                }
            }
            level = getchar();
        }
        if (flag == 1)  printf("%.2f\n", sum / n);
    }
    return 0;
}
  1. 摆平积木
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>

int main() {
    int n, sum, num, res, i, ave;
    int nums[50];
    while(scanf("%d", &n) == 1){
        if (n == 0) break;
        for(i = 0, sum = 0; i < n; i++) {
            scanf("%d", &num);
            sum += num;
            nums[i] = num;
        }
        ave = sum / n;
        for (i = 0, res = 0; i < n; i++) {
            if (nums[i] > ave) res += nums[i] - ave;
        }
        printf("%d\n\n", res);
    }
    return 0;
}
  1. 奇怪的信
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>

int main() {
    int n, num, sum;
    while(scanf("%d", &n) == 1) {
        sum = 0;
        while (n != 0) {
            num = n % 10;
            n /= 10;
            if (num % 2 == 0) {
                sum += num;
            }
        }
        printf("%d\n\n", sum);
    }
    return 0;
}
  1. 运营商活动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>

int main() {
    int m, k, div, mod, sum;
    while(scanf("%d %d", &m, &k) == 2) {
        if (m == 0 && k == 0) break;

        sum = m;
        while(m / k != 0){
            div = m / k;
            mod = m % k;
            
            sum += div;
            m = div + mod;
        }
        printf("%d\n", sum);

    }
}
  1. 共同祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>

int main() {
    int n, a, b, i, gen1, gen2;
    int tree[21] = {-1};
    while(scanf("%d", &n) == 1) {
        for (i = 0; i < n; i++) {
            scanf("%d %d", &a, &b);
            tree[a] = b;
        }

        for (i = 1, gen1 = 0; i != -1; gen1++) i = tree[i];
        for (i = 2, gen2 = 0; i != -1; gen2++) i = tree[i];
        if (gen1 > gen2) printf("You are my elder\n");
        else if (gen1 < gen2) printf("You are my younger\n");
        else printf("You are my brother\n");
    }
    return 0;
}
  1. 打印数字图形
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

int main() {
    int n, i, j;
    while(scanf("%d", &n) == 1) {
            for (i = 0; i < n; i++) {
            for (j = 0; j < n - i - 1; j++) printf(" ");
            for (j = 0; j < i + 1; j++) printf("%d", j + 1);
            for (j = i; j > 0; j--) printf("%d", j);
            printf("\n");
        }
        for (i = n - 2; i >= 0; i--) {
            for (j = 0; j < n - i - 1; j++) printf(" ");
            for (j = 0; j < i + 1; j++) printf("%d", j + 1);
            for (j = i; j > 0; j--) printf("%d", j);
            printf("\n");
        }
    }
    return 0;

}
  1. 镂空图形
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
#include<stdio.h>

int main() {
    char c;
    int n, i, j;
    while(1) {
        scanf("%c", &c);
        if (c == '@') break;
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            for (j = 0; j < n - i - 1; j++) printf(" ");
            if (i == 0) printf("%c", c);
            else if (i == n - 1)
                for (j = 0; j < 2 * n - 1; j ++) printf("%c", c);
            else {
                printf("%c", c);
                for (j = 0; j < 2 * i - 1; j++) printf(" ");
                printf("%c", c);
            }
            printf("\n");
        }
        getchar();		// Absorb the '\n'
        printf("\n");
    }
    return 0;
}
  1. 句子缩写
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
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main() {
    int n, i;
    char letter;
    char input[1000];		// Avoid the length too small.

    scanf("%d", &n);
    getchar();
    for (i = 0; i < n; i++) {
        fgets(input, sizeof(input), stdin);

        char* ptr = input;
        while(*ptr != '\n' && *ptr != '\0') {
            sscanf(ptr, "%c", &letter);		
            if (letter < 91) printf("%c", letter);	// Switch to Capital letter.
            else printf("%c", letter - 32);						
            while(*ptr&&!isspace(*ptr)) ++ptr;
            while(*ptr&&isspace(*ptr)) ++ptr;
        }

        printf("\n");
    }
    return 0;
}
  1. 神秘字符
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
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main() {
    int n, i, len;
    scanf("%d", &n);
    while(n > 0) {
        char A[100];
        char B[50];
        memset(A, '\0', sizeof(A));		// reset the array "A" ⭐️⭐️⭐️
        memset(B, '\0', sizeof(B));

        scanf("%s", A);
        scanf("%s", B); 
        
        len = strlen(A);
        for (i = len - 1; i > (len - 1) / 2; i--) 
            A[i + strlen(B)] = A[i];

        for (i = 0; i < strlen(B); i++) 
            A[i + len / 2] = B[i];

        printf("%s\n", A);
        n--;
    }
    return 0;
}
  1. 位置互换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<string.h>

int main() {
    int n, i;
    scanf("%d", &n);
    while(n > 0) {
        char A[50];
        char tmp;
        scanf("%s", A);
        for (i = 0; i < strlen(A); i += 2) {
            tmp = A[i];
            A[i] = A[i + 1];
            A[i + 1] = tmp;
        }
        printf("%s\n", A);
        n--;
    }
    return 0;
}
  1. 出栈合法性

普通方法

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
#include<stdio.h>

int main() {
    int n, i, j, k, flag;
    int nums[100];
    while(1) {
        scanf("%d", &n);
        if (n == 0) break;

        for (i = 0; i < n; i++) scanf("%d", &nums[i]);
        
        flag = 1;		// 出栈合法性标志位

        for (i = 0; i < n; i++) {
            for (j = i; j < n; j++) {
                if (flag == 1 && nums[i] > nums[j]) {
                    for (k = j + 1; k < n; k++) {
                        if (nums[k] < nums[i] && nums[k] > nums[j]) flag = 0;
                    }
                }
            }
        }

        if (flag == 1) printf("Yes\n");
        else printf("No\n");
    }
}

数据结构 — 栈

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<stdio.h>

#define MAXSIZE 100

typedef struct {
    int items[MAXSIZE];
    int top;
} Stack;

int push(Stack* stack, int item) {
    if (stack->top == MAXSIZE - 1) return 0;    // 栈满
    stack->top += 1;
    stack->items[stack->top] = item;
    return 1;
}

int pop(Stack* stack) {
    if (stack->top == -1) return 0;     // 栈空
    stack->top -= 1;
    return stack->items[stack->top + 1];
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int isPopSequenceValid(int* inSeq, int* outSeq, int n) {
    Stack stack;
    stack.top = -1;
    int Index = 0, outIndex = 0;

    while(outIndex < n) {
        while(Index < n && (isEmpty(&stack) || stack.items[stack.top] != outSeq[outIndex])) {
            push(&stack, inSeq[Index++]);
        }

        if (stack.items[stack.top] == outSeq[outIndex]) {
            pop(&stack);
            outIndex++;
        } else {
            break;
        }
    }

    return isEmpty(&stack) && outIndex == n;
}

int main() {
    int inSeq[MAXSIZE];
    int outSeq[MAXSIZE];
    int n, i;

    while(1) {
        scanf("%d", &n);
        if (n == 0) break;

        for (i = 0; i < n; i++) inSeq[i] = i + 1;
        for (i = 0; i < n; i++) scanf("%d", &outSeq[i]);

        if (isPopSequenceValid(inSeq, outSeq, n)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}
  1. 链表的基本操作
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct lNode {
    int val;
    struct lNode *next;
};

int main() {
    int n, i, m, a, b;
    scanf("%d", &n);    // 单链表的初始节点数目为n
    struct lNode* head = malloc(sizeof(struct lNode));
    if (head == NULL) return 1;     // 内存申请失败
    head->next = NULL;              // 初始末尾节点为空
    

    for (i = 0; i < n; i++) {
        struct lNode* node = malloc(sizeof(struct lNode));
        scanf("%d", &node->val);
        node->next = head->next;       // 头插法
        head->next = node;
    }

    scanf("%d", &m);        // 命令数目
    while (m > 0) {
        char ins[10];
        scanf("%s", ins);
        if (strcmp(ins, "get") == 0) {
            if (scanf("%d", &a) == 1) {
                struct lNode* node = head;  // 遍历
                for (i = 0; i < a; i++) {
                    if (node == NULL) {
                        printf("get fail\n");
                        break;
                    }
                    node = node->next;
                }
                if (node != NULL) printf("%d\n", node->val);    // 获取成功
            }

            else printf("get fail\n");
        }

        else if (strcmp(ins, "insert") == 0) {
            if (scanf("%d %d", &a, &b) == 2) {
                struct lNode* node = head;
                for (i = 0; i < a - 1; i++) {   // 遍历
                    if (node == NULL) {
                        printf("insert fail\n");
                        break;
                    }
                    node = node->next;
                }

                if (node != NULL) {
                    struct lNode* newNode = malloc(sizeof(struct lNode));   // 插入成功
                    if (newNode != NULL) {
                        newNode->val = b;
                        newNode->next = node->next;
                        node->next = newNode;
                        printf("insert OK\n");
                    }
                    else return 1; // 内存申请失败

                }
                else printf("insert fail\n");
            }

            else printf("insert fail\n");
        }

        else if (strcmp(ins, "delete") == 0) {
            if (scanf("%d", &a) == 1) {
                struct lNode* node = head;

                if (node->next != NULL) {
                    i = 0;
                    while(node->next != NULL && i != a - 1) {
                        node = node->next;
                        i++;
                    }

                    if (node->next != NULL && i == a - 1) {
                        node->next = node->next->next;
                        printf("delete OK\n");
                    }
                    else printf("delete fail\n");
                }
                
                else printf("delete fail\n");
            }

            else printf("delete fail\n");
        }

        else if (strcmp(ins, "show") == 0) {
            struct lNode* node = head->next; 
            if (node == NULL)  
                printf("Link list is empty\n");

            else {
                while(node != NULL) {
                    printf("%d", node->val);
                    node = node->next;
                    if (node != NULL) printf(" ");
                }
                printf("\n");
            }
        }

        else printf("Wrong key");

        m--;
    }

    return 0;
}
  1. 单链表反转(没有通过测试，未知原因)
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#include<stdlib.h>


struct lNode
{
    int val;
    struct lNode* next;
};

int linkTrans(struct lNode* head, int n) {
    if (head == NULL || head->next == NULL) return 0;

    int i;
    struct lNode* node = head->next;
    for (i = 0; i < n; i++) {
        if (node == NULL) break;

        printf("%d", node->val);
        if (i < n - 1) printf(" ");
        node = node->next;
    }
    printf("\n");
    
    return 1;
}

void revLink(struct lNode* head) {
    struct lNode* pre = NULL;
    struct lNode* cur = head->next;
    struct lNode* tmp;

    while(cur != NULL) {
        tmp = cur->next;
        cur->next = pre;  // reverse the current part of link
        pre = cur;
        cur = tmp;
    }
    head->next = pre;
}

int main() {
    int n, i, num;
    while(1) {
        scanf("%d", &n);
        if (n == 0) {
            printf("list is empty\n");
            continue;
        }
        struct lNode* head = malloc(sizeof(struct lNode));
        head->next = NULL;
        
        struct lNode* pre = head;

        for (i = 0; i < n; i++) {       // 单链表赋值
            struct lNode* node = malloc(sizeof(struct lNode));

            node->next = NULL;
            scanf("%d", &node->val);

            pre->next = node;
            pre = node;            
        }

        linkTrans(head, n);     // 遍历打印

        revLink(head);

        linkTrans(head, n);     // 遍历打印
        
    }
    return 0;
}
  1. 删除重复元素(未知错误)
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<stdio.h>
#include<stdlib.h>


struct lNode {
    int val;
    struct lNode* next;
};

void linkTrav(struct lNode* head) {
    if (head == NULL || head->next == NULL) return ;

    struct lNode* node = head->next;
    while(node != NULL) {
        printf("%d", node->val);
        node = node->next;
        if (node != NULL) printf(" ");
    }
    printf("\n");
}

void rmvRItem(struct lNode* head) {
    if (head == NULL || head->next == NULL) return ;
    struct lNode* pre = head->next;
    struct lNode* cur = pre->next;
    struct lNode* tmp;

    while(cur != NULL) {
        tmp = cur->next;

        if (pre->val != cur->val) {
            pre->next = cur;
            pre = cur;
        }

        cur = tmp;        
    }
    pre->next = NULL;
}

int main() {
    int n, num;

    while(1) {
        scanf("%d", &n);
        if (n == 0) {
            printf("link is empty\n");
            break;;
        }

        struct lNode* head = malloc(sizeof(struct lNode));
        struct lNode* pre = head;
        head->next = NULL;

        while(n > 0) {
            struct lNode* node = malloc(sizeof(struct lNode));
            scanf("%d", &node->val);

            pre->next = node;
            pre = node;
            n--;
        }

        linkTrav(head);    // Traverse and print

        rmvRItem(head);     // Remove the repeat items

        linkTrav(head);

    }
    return 0;
}
  1. 构造二叉树
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct BiTree {
    char val;
    struct BiTree* lchild;
    struct BiTree* rchild;
};

char* slice(const char arr[], int a, int b) {
    char* res = malloc(b - a + 1);
    int i;
    for (i = 0; i < b - a; i++) {
        res[i] = arr[i + a];
    }
    res[i] = '\0'; // Null-terminate the string
    return res;
}

struct BiTree* buildTree(char pre[], char in[], int size) {
    if (size <= 0) {
        return NULL;
    }
    
    struct BiTree* root = malloc(sizeof(struct BiTree));
    root->val = pre[0];
    int rootPos;
    for (rootPos = 0; rootPos < size; rootPos++) {
        if (in[rootPos] == pre[0]) break;
    }
    
    char* leftPre = slice(pre, 1, rootPos + 1);
    char* leftIn = slice(in, 0, rootPos);
    char* rightPre = slice(pre, rootPos + 1, size);
    char* rightIn = slice(in, rootPos + 1, size);

    root->lchild = buildTree(leftPre, leftIn, rootPos);
    root->rchild = buildTree(rightPre, rightIn, size - rootPos - 1);

    free(leftPre);
    free(leftIn);
    free(rightPre);
    free(rightIn);

    return root;
}

void posTrav(struct BiTree* root) {
    if (root != NULL) {
        posTrav(root->lchild);
        posTrav(root->rchild);
        printf("%c", root->val);
        free(root);
    }
}

int main() {
    while(1) {
        char pre[50];
        char in[50];
        scanf("%s", pre);
        scanf("%s", in);

        int size = strlen(pre);
        struct BiTree* tree = buildTree(pre, in, size);

        posTrav(tree);
        printf("\n");
    }
    return 0;
}