玖的数学&算法录
0%

2024牛客寒假算法训练营3

发表于 更新于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

A.智乃与瞩目狸猫、幸运水母、月宫龙虾

题意：

给你两个字符串，问其首字母在忽略大小写的情况下是否相等。

数据范围

$$1 \leq T \leq 10^5 , 1 \leq |S|,|T| \leq 50$$

题解：模拟

略

代码

1
2
3
4
5
6
7
8
9
10
void JiuCherish(){
    std::string s,t;
    std::cin >> s >> t;
    char x,y;
    x = s[0];
    y = t[0];
    x = tolower(x);
    y = tolower(y);
    std::cout << ((x == y) ? "Yes" : "No") << endl;
}

B.智乃的数字手串

题意：

给你一串首尾相连的数字，两个玩家轮流操作，当且仅当相邻22个数字之和为偶数时，可以消除其中一个， 然后可以交换剩下的数字中任意两个数字的位置（也可以不交换）。 特别的，如果只有 1 个数字，可以直接消除。 最先无法操作的玩家输。 问对于给定的数字串，qcjj（先手）和zn（后手）谁会赢。

数据范围：

$$1 \leq T \leq 10^4$$

$$ 1 \leq N \leq 26 $$

$$0 \leq a_i \leq 10^9$$​

题解：结论，博弈

奇数先手必胜，偶数后手必胜。由于最后的结局一定是 [奇偶] 组合排列，能操作的也只有相邻数字相加之和为偶数，因此取走一个数之后会有两种情况：奇数+偶数或者和为偶数，奇数+偶数即我们最终需要的，偶数+偶数则是可以继续迭代操作的（一轮操作（双方玩家都是偶数+偶数的情况）后实际上就是经历了一个周期T=2），因此只需计算相邻两个元素是否为偶数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int ans = 0;
    a[n + 1] = a[1];
    for(int i=1;i<=n;i++) {
        if((a[i] + a[i + 1]) % 2 == 0) ans++;
    }
    if((ans & 1)) {
        std::cout << "qcjj" << endl;
    } else {
        std::cout << "zn" << endl;
    }
}


C.智乃的前缀、后缀、回文

D.chino’s bubble sort and maximum subarray sum(easy version)

题意：

先交换相邻元素 k 次，然后求最大子段和。

题解：暴力、dp

代码

1

E.chino’s bubble sort and maximum subarray sum(hard version)

F chino’s bubble sort and maximum subarray sum(very hard version)

J.智乃的比较函数(easy version)

K.智乃的比较函数(normal version)

L.chino’s infinite infinite strings without xyz

G. 智乃的相亲活动

H.智乃的“黑红树”

I. 智乃的36倍数(easy version)

J.智乃的36倍数(normal version)