1 点燃我，温暖你

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int main()
{
    printf("   *********   *********\n");
    printf("************* *************\n");
    printf("*****************************\n");
    printf("*****************************\n");
    printf("*****************************\n");
    printf(" ***************************\n");
    printf("   ***********************\n");
    printf("     *******************\n");
    printf("       ***************\n");
    printf("         ***********\n");
    printf("           *******\n");
    printf("             ***\n");
    printf("              *");
    return 0;
}

2 changge学长的史密斯架

这个题等之后讲汉诺塔题目后再来写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
int d[20], f[20];

int main() {
    int n;
    scanf("%d", &n);
    d[1] = 1;
    for (int i = 2; i <= 12; i++)
        d[i] = 2 * d[i - 1] + 1;
    for (int i = 0; i < 20; i++)
        f[i] = 1e9;
    f[1] = 1;
    for (int i = 2; i <= 12; i++)
        for (int j = 1; j < i; j++)
            if (f[i] > 2 * f[j] + d[i - j])
                f[i] = 2 * f[j] + d[i - j];
    printf("%d\n", f[n]);
    return 0;
}

3 数字三角形

这个题不要求全部同学都掌握。

考虑从上到下和从下到上的得分都一样，我们从下向上走。

设 $f[i][j]$ 为从最下层到第 i 层第 j 个的最多得分。

可以发现，1 的位置只能从下方的 7 和 4 走过去，即 $f[i][j]$ 的得分由 $f[i+1][j]$ 和 $f[i+1][j+1]$ 决定。

由于我们取最大得分， $f[i][j]=\max(f[i+1][j], f[i+1][j+1])+a[i][j]$。

自下到上的枚举每个位置即可得到总最大得分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
int a[505][505], f[505][505];

int max(int a, int b) { return a > b ? a : b; }

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        f[n][i] = a[n][i];
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
    printf("%d\n", f[1][1]);
    return 0;
}

4 二进制中1的个数

位运算或取模都可以写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int x, s = 0;
        scanf("%d", &x);
        while (x) {
            s += x & 1;
            x >>= 1;
        }
        printf("%d ", s);
    }
    return 0;
}

5 蛇形矩阵

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

int num[109][109];

int main() {
    int n;
    scanf("%d", &n);
    num[1][1] = 1; // 初始为1
    for (int i = 1, j = 1, tot = 1; tot < n * n;) {
        // 向右
        while (j + 1 <= n && !num[i][j + 1])
            num[i][++j] = ++tot;
        // 向下
        while (i + 1 <= n && !num[i + 1][j])
            num[++i][j] = ++tot;
        // 向左
        while (j - 1 >= 1 && !num[i][j - 1])
            num[i][--j] = ++tot;
        // 向上
        while (i - 1 >= 1 && !num[i - 1][j])
            num[--i][j] = ++tot;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; ++j)
            printf("%3d", num[i][j]);
        printf("\n");
    }
    return 0;
}

6 简单矩阵

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

int a[105][105];
int main()
{
    int n;
    scanf("%d", &n);  
    int tot = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i, k = 1; j >= 1; j--, k++)
            a[j][k] = tot++; // 斜着向右上方填充数字
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1 - i; j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }
    return 0;
}

7 编程团体赛

C 版本

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

struct Node {
    int id, score;
};

int s[1005];
struct Node team[1005];

int main() {
    int n, cnt = 0;
    scanf("%d", &n);
  
    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d-%d %d", &a, &b, &c);
        s[a] += c;
    }
    // 统计有多少个队伍，以及得分，放在arr数组里
    for (int i = 0; i <= 1000; i++)
        if (s[i] > 0) {
            team[cnt].id = i;
            team[cnt].score = s[i];
            cnt++;
        }
    // 对结构体进行排序，按照得分的降序
    for (int i = 1; i < cnt; i++)
        for (int j = cnt - 1; j >= i; j--)
            if (team[j - 1].score < team[j].score) {
                struct Node tmp = team[j - 1];
                team[j - 1] = team[j];
                team[j] = tmp;
            }
    printf("%d %d", team[0].id, team[0].score);
}

C++ 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    map<int, int> mp;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        mp[a] += c;
    }
    vector<pair<int, int>> vp(mp.begin(), mp.end());
    sort(vp.begin(), vp.end(), [](const auto &a, const auto &b){
        return a.second > b.second;
    });
    cout << vp[0].first << ' ' << vp[0].second << '\n';
}