一只小菜鸡的Blog

2024牛客寒假营5||补题

DODOLA 发布于 2024-02-21 更新于 2025-02-22, 收录于类别在学算法的日子里和系列题解记录

A-mutsumi的质数合数

题意

一个由$n$个正整数组成的数组，求其中质数和合数共有几个。

数据范围

$n(1\leq n\leq 100)$

$a_i(1\leq a_i\leq 100)$

思路

1不是质数也不是合数。

参考代码

1
2
3
4
5
6
7
8
9
void solve() {
    int n;cin >> n;
    int ans = 0;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        if (x>1)ans++;
    }
    cout << ans << '\n';
}

C-anon的私货

题意

给一个数组中一些位置插入$0$，要求插入后任意不是全$0$子段的平均值大于等于$1$，询问最多插入多少个$0$

数据范围

$n(1\leq n\leq 10^5)$

$a_i(1\leq a_i\leq 10^9)$

思路

从第一位开始贪，统计在每一位前最多可以插入多少个0，考虑两数之间的0的数目不能大于这2位之间允许的最大值。

参考代码

 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
void solve() {
    int n;cin >> n;
    vector<ll>a(n + 2);
    vector<ll>b(n + 2);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        b[i] = a[i] - 1;
    }
    b[0] = 1e9 + 50;
    b[n + 1] = 1e9 + 50;
    ll ans = 0;

    for (int i = 0;i <= n;i++) {
        // for (int j = 0;j <= n + 1;j++)cout << b[j] << ' ';cout << endl;
        if (b[i] >= b[i + 1]) {
            ans += b[i + 1];
            ll tmp = b[i + 1];
            b[i + 1] = 0;
            b[i] -= tmp;
        }
        else {
            ans += b[i];
            ll tmp = b[i];
            b[i] = 0;
            b[i + 1] -= tmp;
        }
    }

    cout << ans << endl;
}

E-soyorin的数组操作（easy）

题意

有一个长为$n$的数组$a$

2024牛客寒假营3||补题

DODOLA 发布于 2024-02-13 更新于 2025-02-22, 收录于类别在学算法的日子里和系列题解记录

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

题意

在不考虑单词词性的前提下，只要求两个单词的首字母忽略大小写相同时就认为它们可能是一组ubuntu代号，请你编写程序判断给定的两个单词是否可能是一个ubuntu代号。

数据范围

$T(1\leq T \leq 10^5)$

$S,T(1\leq |S|,|T|\leq 50)$

思路

按题意判断即可

参考代码

1
2
3
4
5
6
7
void solve() {
    string s, t;cin >> s >> t;
    if (s[0] == t[0] || abs(s[0] - t[0]) == abs('a' - 'A')) {
        cout << "Yes\n";
    }
    else cout << "No\n";
}

B-智乃的数字手串

题意

一个首尾相连的数组，若相邻的两个数之和为偶数选择拿走一个然后可以随意交换一对数，轮流操作，不能再操作的一方输。清楚姐姐先手。

数据范围

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

$N(1\leq N\leq 26)$

$a_i(0\leq a_i \leq 10^9)$

思路

只有1个数时直接取走，先手赢。

2个数时：奇偶/奇奇/偶偶，都是后手赢。

3个数时：奇偶奇/偶奇偶/奇奇奇/偶偶偶，都是先手赢。

2024牛客寒假营2||补题

DODOLA 发布于 2024-02-09 更新于 2025-02-22, 收录于类别在学算法的日子里和系列题解记录

A-Tokitsukaze and Bracelet

题意

根据手环的三个属性值判断手环的等级。

对攻击百分比来说，+0为100%，+1为150%，+2为200%
对体力和精神来说，+0在${29,30,31,32}$里选择，+1在${34,36,38,40}$里选择，+2固定为45

数据范围

$n(1≤n≤100)$

2024牛客寒假营1||补题

DODOLA 发布于 2024-02-02 更新于 2025-02-22, 收录于类别在学算法的日子里和系列题解记录

A-DFS搜索

题意

给一个字符串，判断其中是否包含dfs子序列和DFS子序列。

数据范围

$T(1≤T≤100)$

$n(1≤n≤50)$

思路

直接搜。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int f1 = 1, f2 = 1;
    int p = s.find('D');
    if (p != -1) {
        p = s.find('F', p);
        if (p != -1) {
            p = s.find('S', p);
            if (p == -1) { f1 = 0; }
        } else { f1 = 0; }
    }
    else { f1 = 0; }
    p = s.find('d');
    if (p != -1) {
        p = s.find('f', p);
        if (p != -1) {
            p = s.find('s', p);
            if (p == -1) { f2 = 0; }
        } else { f2 = 0; }
    }
    else { f2 = 0; }
    cout << f1 << " " << f2 << endl;
}

B-关鸡

题意

https://uploadfiles.nowcoder.com/images/20240121/0_1705849989132/3C73FD698696250B894A2646C4440896

线段树模板

DODOLA 发布于 2024-01-06 更新于 2025-02-22, 收录于类别在学算法的日子里和系列算法模板笔记

线段树(segment tree)

线段树主要用于维护区间信息，与传统的树状数组相比，可以实现O(log n)的区间修改，还可以同时支持多种操作(加、乘)，更具通用性。

图论基础||存储图||DFS、BFS(图论)

DODOLA 发布于 2024-01-06 更新于 2025-02-22, 收录于类别在学算法的日子里和系列算法模板笔记

1.1图的定义

上课讲过一大堆这里不再赘述，直接学习代码实现。

1.2图的存储

例图展示：

graph LR
v1((v1))--4-->v2((v2))
v1((v1))--9-->v6((v6))
v3((v3))--19-->v2((v2))
v3((v3))--22-->v1((v1))
v4((v4))--17-->v3((v3))
v5((v5))--29-->v8((v8))
v6((v6))--12-->v1((v1))
v6((v6))--9-->v5((v5))
v6((v6))--4-->v7((v7))
v7((v7))--25-->v4((v4))
v8((v8))--7-->v7((v7))
v8((v8))--11-->v3((v3))

设n个点，m条边

上图的数据（按照起点-终点-权值）：

邻接矩阵

遍历效率低、不能存重边、初始化效率低初始化O(n^2)时间，建图O(m)时间、空间开销大O(n^2)
对于稀疏图来说大部分是INF，空间利用效率也不高

前向星

前向星涉及排序，所以其时间复杂度和排序算法有关，一般情况下时间复杂度为O(mlog m)，空间上需要两个数组（记录边的边数组、记录各点在边数组中起始位置的head数组），空间复杂度为O(m+n)