2023级算法C2上机赛

2023级算法C2上机赛

Tengpaz Lv3
  2024-09-28 17:52:36 2024-09-28 17:52:36 创建   2024-10-07 11:19:31 2024-10-07 11:19:31 更新      

2023级软院学生第一次上机赛习题讲解

没事，只AC了四道

加油！！！

补题情况

E 2024-矩阵乘法

一个那么easy的矩阵乘法都能TLE???

哒死我叭！！

知识点

  • 矩阵乘法

思路

矩阵乘法

代码

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
#include<bits/stdc++.h>
using namespace std;

long long A[201][201] = {0};
long long B[201][201] = {0};
long long C[201][201] = {0};

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int number;
                scanf("%d", &number);
                A[i][j] = number;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int number;
                scanf("%d", &number);
                B[i][j] = number;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                C[i][j] = 0;
                for (int k = 1; k <= n; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
                printf("%lld ", C[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

F 2024-排序？数数！

知识点

  • 计数

思路

又是排序又要记录小的数的，感觉与快速排序很符合

个人觉得，快速排序之所以快，它的一大特点是极大减少了不必要的比较，每次都是只和哨兵元素比较，哨兵作为中介值，那么就将原本比较时需要将两两分别比较的情况简化为了只需要和两组比较，并且将哨兵元素直接确定最终位置，也就是只有哨兵元素需要比较而且不再会与其它元素重复比较，这种对于已做功的最大化利用使得快速排序整体平均最优，对于差的情况就是哨兵总是那个最小的或者最大的或者类似的情况，使得比较次数没有很大的节省（不难想到最节省的情况就是每次的哨兵元素刚好是最中间的值）

而非常好用的归并排序也就是同样避免了很多不必要的比较，两两元素之间最多比较一次，利用空间复杂换来对于比较节省的最优化。

题目的要求只需要我们在快排过程中顺便记录比较小的数的个数即可

然后TLE

好重整思路，仔细一看数据量不对劲，为什么呢？因为它相当于只认可除读数据外10个指令，快排不是显得太慢了么ww

大道至简，仔细看mod的大小，太宜人了，所以只需要记录下来每种数字的数量，然后每次累加时加上数字*数量*更小数的个数即可

计数注意考虑0

这里总结经验教训

  1. 注意题目的数据范围，考虑清楚再下手，不然会浪费时间和心力
  2. 一般我们之所以需要排序是因为特殊数据无法直接不重叠地利用hash值进行直接排序，否则直接hash显然是非常方便的

代码

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
#include<bits/stdc++.h>
using namespace std;
#define N 5000005

int nextRand() {
    static unsigned int rnd_num = 0x80000001;
    static int mod = 1e5 + 3;

    rnd_num ^= rnd_num >> 10;
    rnd_num ^= rnd_num << 9;
    rnd_num ^= rnd_num >> 25;
    return rnd_num % mod;
}

int a[N];
int number[(unsigned long long)(1e5 + 3)] = {0};

int main() {
    int tt;
    scanf("%d", &tt);
    while (tt--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            a[i] = nextRand();
            number[a[i]]++;
        }
        unsigned long long ans = 0;
        int i = 0;
        int count = 0;
        while (count < n) {
            while (!number[i]) {
                i++;
            }
            ans += (unsigned long long)i * number[i] * (count + 1); // 数字 * 数量 * 位置
            count += number[i];
            i++;
        }
        printf("%lld\n", ans);
        for (int i = 1; i <= n; i++) {
            number[a[i]] = 0;
        }
    }
    return 0;
}

G 待到山花浪漫时

题目好美

知识点

  • 差分

思路

时间复杂度肯定不能够支持暴力求解，所以就想起来了以前程设题目的一次hint

对于一段区间赋相同值的情况，可以不必将区间上每个点的值都求出来，只需要记录每相邻两个值的差值即可，最后求前缀和即为对应值，差分也就是前缀和的逆运算

注意防溢出噢！

代码

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<bits/stdc++.h>
#define MOD 1000000007
#define MAXN 1000000
using namespace std;

long long mountain[MAXN + 1] = {1, -1}; // 山坡之花

int main() {
    int n, k, l, r;
    scanf("%d %d %d %d", &n, &k, &l, &r);
    long long flower = 0;
    long long flower_birth = 0;
    for (int year = 0; year <= n; year++) {
        flower_birth += mountain[year];
        flower_birth %= MOD;
        flower += flower_birth;
        flower %= MOD;
        if (year + l <= n) {
            mountain[year + l] = ((flower_birth * k) % MOD + mountain[year + l]) % MOD;
        }
        if (year + r + 1 <= n) {
            mountain[year + r + 1] = (mountain[year + r + 1] - (flower_birth * k) % MOD) % MOD;
        }
    }
    printf("%lld\n", (flower + MOD) % MOD);
    return 0;
}

H 莫卡的龙

知识点

  • 贪吃蛇的实现原理
  • 模拟

思路

因为以前开发过贪吃蛇游戏，这个其实主要解决的就是如何实现位置的移动并且减少实践复杂度，这个简单，因为描述上确实是每个块都要移到前一个块的位置处，但是其实可以直接中间部分不改变，最后一个块移到头需要到的下一个位置，那么就实现了一次移动，实践复杂度

至于如何实现可以使用双端队列deque，我选择用循环队列加数组实现

代码

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<bits/stdc++.h>
using namespace std;

typedef struct point {
    int x, y;
} Point;

Point dragon[1000001] = {0};
int head = 1, tail;

void init(int N);
void move(char direction, int N);
void find(int position, int N);

int main() {
    int N, Q;
    scanf("%d %d", &N, &Q);
    init(N);
    char direction = 0;
    int position = 0;
    for (int i = 0; i < Q; i++) {
        int op;
        scanf("%d", &op);
        switch (op) {
            case 1:
                scanf(" %c", &direction);
                move(direction, N);
                break;
            case 2:
                scanf("%d", &position);
                find(position, N);
                break;
        }
    }
    return 0;
}

void init(int N) {
    tail = N;
    for (int i = 1; i <= N; i++) {
        dragon[i].x = i;
        dragon[i].y = 0;
    }
}

void move(char direction, int N) {
    int head_follower = head;
    head = (head - 1) == 0 ? N : head - 1;
    tail = (tail - 1) == 0 ? N : tail - 1;
    if (direction == 'R') {
        dragon[head].x = dragon[head_follower].x + 1;
        dragon[head].y = dragon[head_follower].y;
    } else if (direction == 'L') {
        dragon[head].x = dragon[head_follower].x - 1;
        dragon[head].y = dragon[head_follower].y;
    } else if (direction == 'U') {
        dragon[head].x = dragon[head_follower].x;
        dragon[head].y = dragon[head_follower].y + 1;
    } else {
        dragon[head].x = dragon[head_follower].x;
        dragon[head].y = dragon[head_follower].y - 1;
    }
}

void find(int position, int N) {
    position = position + head - 1 > N ? position + head - 1 - N : position + head - 1;
    printf("%d %d\n", dragon[position].x, dragon[position].y);
}

I 2024-矩阵连乘

知识点

  • 矩阵乘法
  • 线性代数
  • 倍增

思路分析

这个时间复杂度，感觉倍增能勉强过，试试，仔细看题目发现时间限制为4ms，稳了，就是直接倍增

首先先算出这个最坏情况为大概差不多满足算法时间复杂度要求

对于上面矩阵乘法的计算结果求m次幂，这里沿用快速幂的思路，对于矩阵进行乘法计算，注意初始化时快速幂最开始那个res初始化为1，但是在矩阵的概念中，单位矩阵不是元素全为1的矩阵，而是对角元素全为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
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
// 快速幂

long long** matrix_build(int n);
long long** matrix_mul(long long** a, long long** b, int n);
long long** matrix_pow(long long** a, int n, int k);
void matrix_free(long long** a, int n);
void matrix_print(long long** a, int n);

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        long long** A = matrix_build(n + 1);
        long long** B = matrix_build(n + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%lld", &A[i][j]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%lld", &B[i][j]);
            }
        }
        long long** C = matrix_mul(A, B, n);
        C = matrix_pow(C, n, m);
        matrix_print(C, n);
        matrix_free(A, n);
        matrix_free(B, n);
        matrix_free(C, n);
    }
    return 0;
}

long long** matrix_build(int n) {
    long long** a = new long long*[n];
    for (int i = 0; i < n; i++) {
        a[i] = new long long[n];
        for (int j = 0; j < n; j++) {
            a[i][j] = 0;
        }
    }
    return a;
}

long long** matrix_mul(long long** a, long long** b, int n) {
    long long** c = matrix_build(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            c[i][j] = 0;
            for (int k = 1; k <= n; k++) {
                c[i][j] += (a[i][k] * b[k][j]) % MOD;
                c[i][j] %= MOD;
            }
        }
    }
    return c;
}

long long** matrix_pow(long long** a, int n, int k) {
    long long**res = matrix_build(n + 1);
    for (int i = 1; i <= n; i++) {
        res[i][i] = 1;
    }
    while (k) {
        if (k & 1) {
            res = matrix_mul(res, a, n);
        }
        a = matrix_mul(a, a, n);
        k >>= 1;
    }
    return res;
}

void matrix_free(long long** a, int n) {
    for (int i = 0; i < n; i++) {
        delete[] a[i];
    }
    delete[] a;
}

void matrix_print(long long** a, int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%lld ", a[i][j]);
        }
        printf("\n");
    }
}

J 2024-三叉卡特兰数

知识点

  • 卡特兰数

思路

三叉卡特兰数，先试试动态规划，通过给出的递归式依次计算出从1到n的三叉卡特兰数值，时间复杂度，出界，可以尝试

但其实对于每组数据后面分析发现不需要重新求，只需要求一遍n=5000全部的三叉卡特兰数的项值，对于多组数据只需要取值即可，虽然但是还是时间复杂度高了，实在不行甚至可以打表，时间复杂度降为

打表过了，找不打表的方法

对于每次计算三叉卡特兰数，其实二项乘的和是有部分可重复使用的，可以降低复杂度

K 序列询问

知识点

  • 异或
  • 前缀和
  • 离散化

思路

对于求一列数里是否出现数刚好为奇数次，首先可以考虑异或，不过由于可能有多个整数出现奇数次的情况，需要另外考虑一下

不考虑特殊情况后，由于只使用异或涉及遍历一段区间，这个时间复杂度为，过大，所以可以结合前缀和的思想，使用前缀异或

但是这种方法有个非常大的缺陷就是，不知道内部多个出现奇数次的整数的异或是否会直接相抵消结果为0了

于是还是觉得可以暴力一点点

使用莫队算法试试

进行离线处理，读取全部的询问，对于询问按照先按l排序，再按r排序的原则排序，那么第一个询问l与r均最左，对于后面的询问可以通过前面的询问推理得到，进行区间移动，最后得到所有询问的结果。

如何发现也TEL了，再试试莫队加前缀异或

TLE

发现奇数个数组成的数列必然存在整数恰好出现了奇数次，再剪枝试试

TLE

后面试过了各种莫队阴间卡常办法，都没通过，估计这题防了莫队

根据最后给的标程

这题考的是离散化和前缀异或

如果按它原来给的数字由于数据过于密集可能导致多个不同的数异或后抵消了，所以就可以考虑让数字之间不那么密集，减小抵消概率，答案给了在longlong范围取随机数的方法，由于这里涉及到离散化，使用c++的map是更为方便的，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
36
#include<bits/stdc++.h>
using namespace std;

long long rnd() {
    static long long x = 19260817;
    return x = x * 233 % 1000000007;
}

map<int, long long> m;
long long a[100005] = {0};

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        m.clear();
        int n;
        scanf("%d", &n);
        int q;
        scanf("%d", &q);
        for (int i = 1; i <= n; i++) {
            int v;
            scanf("%d", &v);
            if (m[v] == 0) {
                m[v] = rnd();
            }
            a[i] = a[i - 1] ^ m[v];
        }
        while (q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf(a[r] ^ a[l - 1] ? "YES\n" : "NO\n");
        }
    }
    return 0;
}
  • 标题: 2023级算法C2上机赛
  • 作者: Tengpaz
  • 创建于 : 2024-09-28 17:52:36
  • 更新于 : 2024-10-07 11:19:31
  • 链接: https://qinaida.cn/tengpaz/2024/09/28/2023级算法C2上机赛/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
2023级算法C2上机赛
  1. 2023级软院学生第一次上机赛习题讲解
    1. 补题情况
    2. E 2024-矩阵乘法
      1. 知识点
      2. 思路
      3. 代码
    3. F 2024-排序？数数！
      1. 知识点
      2. 思路
      3. 代码
    4. G 待到山花浪漫时
      1. 知识点
      2. 思路
      3. 代码
    5. H 莫卡的龙
      1. 知识点
      2. 思路
      3. 代码
    6. I 2024-矩阵连乘
      1. 知识点
      2. 思路分析
      3. 代码
    7. J 2024-三叉卡特兰数
      1. 知识点
      2. 思路
    8. K 序列询问
      1. 知识点
      2. 思路
      3. 代码