算法练习专栏——牛客练习——牛客小白月赛92

A:获得木头

链接

题目描述

​ 伐木是MC生存中必须做的事情，因为大多数合成物品都必须在 工作台 上才能制作。
由于生存开始时都是用手去采集木头，所以这个过程又被叫做 “撸树”。 由此，就衍生出了一句经典的话——“要致富，先撸树”。

​ 一个橡木原木可以合成四个橡木木板，两个橡木木板可以合成四根木棍。

这一天你撸到了 x 个橡木原木，请问你最多能得到多少根木棍？

输入描述:

1
2
一个正整数 x
1≤x≤1000

输出描述:

1
你所能得到的木棍的最多数量

示例1

输入

复制

1
8

输出

复制

1
64

说明

1
2
3
8个橡木原木可以合成出 32 个橡木木板，
32 个橡木木板可以合成出 64 个木棍，
此时橡木原木和橡木木板全部用完，得到的 64 即为木棍最多的数量。

备注:

1

思路

​ ……

代码

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
int main()
{
    int x;
    cin >> x;
    cout << x * 8;
}

B:采矿时间到！

链接

题目描述

你已经获得了木头，通过工作台制作了木镐，获得了圆石和石镐，现在你已经可以采掘铁矿石了。
这一天你挖了一条长度为 n，宽度为 1的矿道，你最多只能在这条矿道向左/右正方向拓宽 2 格，并且你只能垂直于矿道挖掘。

1
2
3
4
5
##*#############**##
#########*##########
....................
#####*######**######
#*##################

如上图所示，’.’ 表示矿道，’#’ 表示的是圆石，’*’ 表示的是矿石。
本题固定第三行为矿道，第一/二行 为你的左侧，第四/五行 为你的右侧。
因为你只能站在矿道上，至多向左/右正方向拓宽 2 格，所以本题只给出 5xn 的俯视图。

每拓宽一格，需要花费 1 11 点体力。现在您有 h点体力，问你最多能得到多少矿石？

​

以下是合法的两种挖法

1
2
3
4
5
###    .##  ###    ..#  
###    .##  ###    ..#
... -> ...  ... -> ...
###    ###  ###    ###
###    ###  ###    ###

以下是不合法的两种挖法

1
2
3
4
5
###    ..#  ###    ...
###    .##  ###    #.#
... -> ...  ... -> ...
###    ###  ###    ###
###    ###  ###    ###

输入描述:

1
2
3
4
第一行 两个正整数 n 和 h，n 为 矿道的长度，h 为体力大小。
接下来五行 每行一个长度为 n 的只含有'#'，'*' 和 '.' 的字符串，'#' 表示圆石，'*' 表示矿石，'.' 表示矿道。五行中的第三行一定全为 '.' 。 
1≤n≤1000
10000≤h≤40000

输出描述:

1
一个整数，表示你最多能得到的矿石数量。

示例1

输入

复制

1
2
3
4
5
6
20 7
##*#######**########
#########*##########
....................
#####*######**######
####################

输出

复制

1
5

说明

1
2
3
4
5
6
7
8
##*#######.*########
#########..#########
....................
#####.######..######
####################


如上，刚好采掘 666 格，花费 666 点体力，得到 555 个矿石。

备注:

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
#include <iostream>
using namespace std;
const int N = 1010;
char a[N][N];

int main()
{
    int n, h, ans = 0;
    cin >> n >> h;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[2][i] == '*' && h) {
            ans++;
            h--;
            if (a[1][i] == '*' && h) {
                ans++;
                h--;
            } 
        } 
        
        if (a[4][i] == '*' && h) {
            ans ++;
            h--;
            if (a[5][i] == '*' && h) {
                ans ++;
                h--;
            }
        }
        
        if (!h) break;
    }
    
    if (!h) {
        cout << ans;
        return 0;
    } else {
       for (int i = 1; i <= n; i++) {
            if (a[2][i] == '#' && a[1][i] == '*' && h >= 2) {
                h -= 2;
                ans ++;
            } 

            if (a[4][i] == '#' && a[5][i] == '*' && h >= 2) {
                h -= 2;
                ans ++;
            }

            if (h <= 1) break;
        }
        cout << ans;
    }
    return 0; 
}

C:耕种时间到！

链接

题目描述

挖完矿石之后你累了，你回到了大地上，你的肚子有点饿，你决定种植一些小麦……

​ 定义等级为 x 的小麦，收割后可以得到 2 枚 等级为 ⌈x/3⌉ 的小麦种子。

​ 现在你有 n 枚小麦种子，第 i 枚种子的等级为 ai，你可以全部种下，也可以选择全部都不种下。小麦成熟以后，你可以进行收割，收割必须收割所有种下的小麦。现在你想知道，在任意时刻(收割前或收割后)最多能拥有多少枚等级为 x的小麦种子？

​ ⌈a/b⌉ 表示 a 除以 b 向上取整，如 ⌈5/3⌉=2，⌈6/3⌉=2，⌈7/3⌉=3。

输入描述:

1
2
3
4
5
6
共三行，第一行 一个正整数 n，表示现在拥有的小麦种子数量。
第二行 n 个由空格隔开的正整数 ai 表示第 i 枚小麦种子的等级。
第三行 一个正整数 x，代表问题查询的小麦种子的等级。
1≤n≤105
1≤ai≤109
2≤x≤109

输出描述:

1
一个正整数，表示等级为 x 的小麦种子的最多数量。

示例1

输入

复制

1
2
3
6
12 13 14 36 35 34
4

输出

复制

1
12

说明

1
2
3
4
5
6
7
8
以 (x,y)(x,y)(x,y) 的形式表示 等级 x 的小麦种子有 y 枚。
第一轮收割前，有 (12,1),(13,1),(14,1),(34,1),(35,1),(36,1)(12,1),(13,1),(14,1),(34,1),(35,1),(36,1)(12,1),(13,1),(14,1),(34,1),(35,1),(36,1)
没有等级为 4 的小麦种子但是有更高等级的小麦种子，所以收割后可能有等级为 4  的小麦种子。
第一轮收割后，有 (4,2),(5,4),(12,6)(4,2),(5,4),(12,6)(4,2),(5,4),(12,6)
此时有 2  枚等级为 4 的小麦种子。
第二轮收割后，有 (2,12),(4,12)(2,12),(4,12)(2,12),(4,12)
此时有 12  枚等级为 4 的小麦种子。 本轮收割后再种植就没有产生等级为 4 的小麦种子的可能了，所以之后的种植与收割都对答案没有贡献。
所以答案为 12

备注:

1

思路

​ 这道题目思路很简单：本人代码还是有点粗糙，还可以优化，还需谅解，就是预先处理一下所有的麦子变成等级x需要经历的时间，当然也有麦子是可能到达不了的，这种情况可以将其次数设置为-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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef pair<long long, long long> PII;
const int N = 1e5 + 10;
int n, x;
PII a[N];
long long ans;

bool cmp(PII A, PII B){
    return A.second < B.second;
}

int main()
{
//     x -> [x / 3]
//     
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].first;
    }
    cin >> x;
    
    for (int i = 1; i <= n; i++) {
        long long k = 1;
        while (a[i].first > x) {
            a[i].first = ceil(a[i].first / 3.0);
            k *= 2;
        }
//         cout << a[i].first << '\n';
        if (a[i].first == x) a[i].second = k;
        else a[i].second = -1;
    }
    sort(a + 1, a + n + 1, cmp);
//     for (int i = 1; i <= n; i++) {
//         cout << a[i].second << '\n';
//     }
    long long kk = a[1].second;
    for (int i = 2; i <= n; i++) {
        if (a[i].second == a[i - 1].second && a[i].second != -1) {
            kk += a[i].second;
        } else {
            ans = max(ans, kk);
            kk = a[i].second;
        }
    }
    
    ans = max(kk, ans);
    cout << ans;
    return 0;
}

D:探索的时光

链接

题目描述

​ 生物群系是 Minecraft 世界中形态各异的地区，有着多样的地理特征、植物群、海拔高度、温度、湿度及天空、水域和植被颜色。
生物群系将生成的世界划分为一个个不同的自然环境，譬如森林、丛林、沙漠和针叶林。

​ 在耕种完作物后，你想要去探索世界。目前你已知 n 个生物群系的位置(从 1 到 n 编号)，你需要去探索，第 i 个生物群系的危险系数为 ai。

​ 定义第 i 个生物群系的危险度为 f(i)=(x−i)^2∗ai，x 为庇护所 所在生物群系的编号。

​ 现在你可以选择一个生物群系作为自己的庇护所，你想要知道所有可能情况下危险度之和的最小值是多少？

输入描述:

1
2
3
4
第一行 一个正整数 n，表示生物群系的个数
第二行 n 个由空格隔开的正整数 ai 表示生物群系 i 的危险系数。
1≤n≤105
0≤ai≤104

输出描述:

1
一个非负数，表示所有可能情况的危险度之和的最小值。

示例1

输入

复制

1
2
5
3 2 1 2 3

输出

复制

1
28

说明

1
2
当选择第 3 个生物群系作为庇护所时，危险度之和最小，此时 x=3x=3x=3。
sum=(1−3)2∗3+(2−3)2∗2+(3−3)2∗1+(4−3)2∗2+(5−3)2∗3=12+2+0+2+12=28=12+2+0+2+12=28=12+2+0+2+12=28

备注:

1

思路

​ 思路一：一般我们看这道题目第一个想法肯定就是枚举每个点，然后依次比较最佳情况，但是非常明显，这种思路会TLE的，时间复杂度O(n^2);

​ 思路二： 先说结论，如果我们将每个位置x的危险度看成一个函数f(x)，那么我们就会形成一个函数，这个函数应该是一个v字形的函数图象，这样的话我们就可以选择使用三分的办法求解中间的那个顶点坐标即可。当然看完证明了也可以直接使用公式法来求解。

​ 现在我们来证明一下这个结论：（如有错误请佬指正）
$$
\begin{flalign}
&我们直接将f(x)化简一下就ok了：\\
&f(x)\\
& =(x-1)^2*a_1\ +\ (x - 2) * a_2\ +\ …\ + (x-n)*an\\
& =(x^2-2x+1)*a_1\ +\ (x^2-4x+4)*a_2 + \ …\ + (x^2-2nx+n^2)*a_n\\
& =(a_1+a_2+…+a_n)x^2-(2a_1+4a_2+…+2^na_n)x+(a_1+4a_2+…+n^2a_n)\\
& 这里的x^2和x系数都是还有常数部分都是固定数值，因此最后的f(x)就是一个经典的二次函数。
&
\end{flalign}
$$
​ 思路三：代码就不写了，看看就行。

image-20240428222001123

代码一（暴力，铁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
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
long long ans = 1e18;
long long f(int x) {
    long long res = 0;
    for (int i = 1; i <= n; i++) {
        res += pow(abs(x - i), 2) * a[i];
    }
    return res;
}

long long min(long long x, long long y) {
    return (x < y ? x : y);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        ans = min(f(i), ans);
    }
    
    cout << ans;
}

代码二（三分）

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1e5 + 10;
int n;
long long a[N];

long long f(int x) {
    long long res = 0;
    for (int i = 1; i <= n; i++) {
        res +=(long long)(pow(abs(x - i), 2) * a[i]);
    }
    return res;
}

long long max(long long x, long long y){
    return (x < y ? y : x);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = n + 1;
    while (l < r)
    {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (f(lmid) > f(rmid))l = lmid + 1;
        else r = rmid - 1;
    }
//     cout << r << '\n' << l << '\n';
    cout << f(r);
    return 0;
}

代码三（公式法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
typedef long long int ll;
const int N=1e5+10;
int n;
ll a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    ll x=0,y=0,z=0;
    for(ll i=1;i<=n;++i){
        x+=a[i];
        y+=2*i*a[i];
        z+=i*i*a[i];
    }
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(ll i=1;i<=n;++i){
        ans=min(ans,i*i*x-i*y+z);
    }
    cout<<ans<<endl;
}

E:来硬的

链接

题目描述

你厌倦了探索的日子，在之前你采掘了许多矿石，现在你需要烧炼矿石。

​ 一枚煤炭可以在熔炉内燃烧 y 秒融化至多 x 单位的铁矿石。

​ 而一枚暗物质可以在熔炉内燃烧 y/2秒融化至多 2x 单位的铁矿石。

​ 同一时刻，熔炉只能燃烧一枚燃料。燃料均不可重复利用。燃料燃烧完之前，你不可以获取熔炉中的矿物。

​ 你有一个神奇的魔法，可以将一枚煤炭升级成暗物质，这个魔法至多只能使用一次。

现在你有 1 个熔炉， n 枚煤炭和 m 单位铁矿石，问烧炼 m 单位铁矿石至少需要多长时间？

输入描述:

1
2
3
4
5
6
7
第一行 两个正整数 n 和 m，n 表示有 n 枚煤炭，m 表示有 m 个单位的铁矿石。
接下来 n 行，每行两个正整数 xi 和 yi，代表第 i 枚煤炭可以在熔炉内燃烧 yi 秒融化 xi 单位的铁矿石。
1≤n∗m≤106
1≤xi≤109
2≤yi≤109
保证 ∑x≥m
yi 一定为偶数。

输出描述:

1
一个正整数，表示烧炼m 单位铁矿石至少需要多长时间。

示例1

输入

复制

1
2
3
4
5
6
5 28
6 8
5 4
6 10
5 2
6 4

输出

复制

1
14

说明

1
2
选择第 1,2,4,5 煤炭，其中对第 1 枚煤炭使用魔法。
这样能融化 28 个单位的铁矿石，并且总燃烧时间最短，即 14。

备注:

1

思路

​ 经典的DP类型题目，直接看代码吧。

代码

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 <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
long long Time;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    // f[i][j][k]表示对于前i个煤炭，已经烧了j个单位，k为1的时候表示当前的第i个煤炭施加魔法，0表示不做操作。
    vector<vector<vector<long long>>> f(n + 10, vector<vector<long long>>(m + 10, vector<long long> (2, 1e18)));
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    
    f[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j][0] = f[i - 1][j][0];
            // 注意，我们烧一个煤炭要烧完，必须算整个时间，不可以烧一部分因为达到了时间而直接结算最终时间。
            f[i][j][0] = min(f[i - 1][max(int(0), j - a[i])][0] + b[i], f[i][j][0]);
            f[i][j][1] = f[i - 1][j][1];
            // 如果k=1,那么代表有两种情况，一种是我们之前已经进行过施法，还有一种就是第i个位置我们进行了施法，我们也只需要比较一下这两种情况即可。
            f[i][j][1] = min(f[i - 1][max(int(0), j - a[i])][1] + b[i], f[i][j][1]);
            f[i][j][1] = min(f[i - 1][max(int(0), j - 2 * a[i])][0] + b[i] / 2, f[i][j][1]);
        }
        
    }
    cout << f[n][m][1];

    return 0;
}

F：快快乐乐剪羊毛

链接

题目描述

干(肝)完了许多东西之后，你发现你的羊场还没剪羊毛，于是你准备去羊场剪羊毛。

​ 羊场的设计是由 n 块长度相等宽度不定的矩形草皮从左至右依次拼接而成的，第 iii 块草皮的宽度为 wiw_iwi，其富含的营养价值为 vi。vi可以为负数，负数代表不仅没有营养还危害健康。

​ 第 1 块草皮所在的区间为 (0,w1]，则第 2 块草皮所在区间为 (w1,w1+w2]，第 3 块草皮所在区间为 (w1+w2,w1+w2+w3]以此类推……

你一共 m只绵羊，第 iii 只绵羊在点 xi 所在的竖线上。
绵羊的羊毛的价值等于所在草皮富含的营养价值，你觉得现在的布局不能让你最大程度上的薅羊毛，但是绵羊们都不愿意移动，既然你不动，那我就动这个世界，你现在可以水平向左或向右任意挪动整个羊场的草皮，若绵羊脚下没有草皮，则羊毛的价值为0。
现在你想计算你所能得到的羊毛价值之和的取值有多少种。

输入描述:

1
2
3
4
5
6
7
8
第一行 两个正整数 n 和 m，表示草皮的数量和绵羊的数量
接下来 一行 n 个由空格隔开的正整数wi，表示第 i 块草皮的宽度。
接下来 一行 n 个由空格隔开的整数 vi，表示第 i 块草皮的营养价值。
再接下来 一行 m 个由空格隔开的非负整数 xi，表示第 i 只绵羊所在的横坐标为 xi
1≤n∗m≤105
1≤wi≤1051
−109≤vi≤109
0≤xi<∑i=1nwi

输出描述:

1
一个正整数，表示羊毛价值之和的取值的种数。

示例1

输入

复制

1
2
3
4
3 3
1 2 3
2 -1 3
2 3 4

输出

复制

1
7

说明

1
2
价值和去重排序后有 0,1,2,3,5,6,9。
所以一共有 7 种。

备注:

1

思路

​ 首先用每块草的宽度前缀和求一下每块草皮右端点的位置

先根据每只羊的位置确定当前在第id块草皮上，记录该羊的初始价值，然后用字典差分地记录移动的距离对应的总价值变化,la表示上一个位置的价值，la初始化为v[id]

1.羊从id相对草皮向左移动，羊的价值每次变化是在刚到第i块草皮的右端点，即羊移动了w[i] - id，差分地记录总价值改变量v[i] - la，并更新la为v[i]。注意移动到最左侧草皮后还要继续向左移动到没有草的部分即位置为0。

2.羊从id相对草皮向右移动，羊的价值每次变化是在刚到第i块草皮的左端点 + 1(左闭右开区间)，即羊移动了w[i - 1] + 1 - id，差分地记录总价值改变量v[i] - la，并更新la为v[i]。注意移动到最右侧草皮后还要继续向右移动到没有草的部分即位置为w[n] + 1。

最后将对总价值做出改变的向左和向右的移动距离分开，因为之前是以差分的方式记录的总价值变化量，所以现在初始化res为草皮没有移动时的总价值，然后分别向左右两侧对记录下的总价值的变化量求和，每次求和结果放入set中去重，答案为set的长度。

代码

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
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...) (void)0
#endif
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int n, m;
  cin >> n >> m;
  vector<i64> w(n), v(n);
  for (i64& wi : w) cin >> wi;
  for (i64& vi : v) cin >> vi;
  map<i64, i64> mp;
  for (int i = 0, x; i < m; i += 1) {
    cin >> x;
    i64 sw = 0;
    for (int j = 0; j < n; j += 1) {
      mp[sw - x] += v[j];
      mp[(sw += w[j]) - x] -= v[j];
    }
  }
  set<i64> s;
  i64 sum = 0;
  for (auto [_, v] : mp) s.insert(sum += v);
  cout << s.size();
}