[数据结构与算法] 2021-2022-2 ACM集训队每周程序设计竞赛（13）题解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021-2022-2 ACM集训队每周程序设计竞赛（13）题解 -> 正文阅读

[数据结构与算法]2021-2022-2 ACM集训队每周程序设计竞赛（13）题解

A: 打怪兽version-1

题意：
有一只怪兽的血量为H
你每回合可以对其造成A点伤害
问多少回合可以杀死怪兽(其血量小于等于0即为死亡)
思路：
输出 $\lceil H/A \rceil$ 即可
上取整和下取整之间的转换：
$\lceil H/A \rceil$ = $\lfloor (H+A-1)/A \rfloor$
时间复杂度： $O 1$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;

int main()
{
    int h , a ;
    cin >> h >> a ;
    cout << (h + a - 1) / a ;
    return 0 ;
}

B: 打怪兽version-2

题意：
有一只怪兽的血量为H
你需要在N回合之内杀死它
第i个回合你可以对其造成点伤害
问是否可以杀死怪兽(其血量小于等于0即为死亡)
可以输出Yes
否则输出No
思路：
只需要判断所有伤害总和是否大于等于H
时间复杂度： $O n$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;
int a[N] , n , s ;

int main()
{
    cin >> s >> n ;
    int res = 0 ;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i] , res += a[i] ;
    puts((res >= s ? "Yes" : "No")) ;
    return 0 ;
}

C: 打怪兽version-3

题意：
有N只怪兽的血量为Hi
你现在有2个技能
技能1:选择一个怪兽i,使其血量降低1点
技能2:选择一个怪兽i,使其血量变为0
问你需要使用多少个1技能可以杀死所有怪兽(其血量小于等于0即为死亡)
特别的,技能2只能使用K次
思路：
我们只需要对血量最大的K只怪兽使用技能2
其余怪兽使用技能1
所以答案为最小的N-K只怪兽的血量之和
时间复杂度： $O n l o g n$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;
int n , k ;
int a[N] ;

int main()
{
    cin >> n >> k ;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
    sort(a + 1 , a + 1 + n) ;
    long long res = 0 ;
    for(int i = 1 ; i <= n - k ; i ++) res += a[i] ;
    cout << res ;
    return 0 ;
}

D: 打怪兽version-4

题意：
有1只怪兽的血量为H
你现在有一个技能
你可以选择一个怪兽，假设它当前生命值为x
对其造成伤害之后，该怪兽会分裂成2个生命值为 $\lfloor x/2 \rfloor$ 的怪兽
问你需要使用多少次技能可以杀死所有怪兽
思路：
每次对一个生命值为x的怪兽造成伤害
怪兽会分裂成2个生命值为 $\lfloor x/2 \rfloor$ 的怪兽
可以列一个表格如下

生命值	数量
$x$	1
$\lfloor x/2 \rfloor$	2
$\lfloor {\lfloor x/2 \rfloor}/2 \rfloor$	4
…
1	$2^k$

答案即为 $1 + 2 + 4 + ..... + 2^k$
时间复杂度： $O l o g H$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;
long long h ;

int main()
{
    cin >> h ;
    long long res = 0 , k = 0 ;
    while(h)
    {
        res += (1ll << k) ; // (1ll << k)=2的k次方
        h /= 2 , k ++ ;
    }
    cout << res ;
    return 0 ;
}

题意：
有一只怪兽的血量为H
你现在有N个技能
技能i可以对怪兽造成Ai点伤害,但是需要Bi点魔力值
问你最少需要多少点魔力值,可以杀死该怪兽(其血量小于等于0即为死亡)
每个技能可以重复使用
思路：
我们可以把 $A i$ 点伤害当做物品的体积, $B i$ 点魔力值当做物品的价值
$N$ 个技能等价于 $n$ 个物品,并且每件物品可以重复使用
题目等价于求背包体积为 $[H,\infty]$ 的最小价值
(其血量小于等于0即为死亡)所以背包体积为 $[H,\infty]$

回忆一下背包体积为 $m$ 的求法
我们假设 $f [j]$ 表示体积为 $j$ 的情况下的最大价值

for(int i = 1 ; i <= n ; i ++)
	for(int j = v[i] ; j <= m ; j ++)
		f[j] = max(f[j] , f[j - v[i]] + w[i])

现在考虑背包体积为 $[H,\infty]$ 的最小价值
只需要

memset(f,0x3f,sizeof f) // 初始化为正无穷,因为要求最小值
f[0] = 0 // 体积为0的情况下的最小价值为0
for(int i = 1 ; i <= n ; i ++)
	for(int j = 0 ; j <= m ; j ++)
		f[j] = min(f[j] , f[max(0,j - v[i])] + w[i])

时间复杂度： $O n m$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6 + 10 ;
int m , n ;
int f[N] ;

int main()
{
    cin >> m >> n ;
    memset(f , 0x3f , sizeof f) ;
    f[0] = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int v , w ;
        cin >> v >> w ;
        for(int j = 0 ; j <= m ; j ++)
            f[j] = min(f[max(j - v , 0)] + w  , f[j]);
    }
    cout << f[m] ;
    return 0 ;
}

F: 打怪兽version-6

题意：
有N只怪兽,每只怪兽都有一个坐标Xi,和其血量Hi
你有一个技能
每次技能你可以选择一个坐标x
对区间[x-D,x+D]的所有怪兽造成伤害A点
问你最少需要使用多少次技能可以杀死所有怪兽(其血量小于等于0即为死亡)
思路：
简单的贪心策略是:
首先对怪兽所再的位置进行排序
排序之后从左往右遍历
依次杀死每只怪兽即可

从左往右遍历的时候,假设遍历到的这只怪兽
所再的坐标为X,血量为H
我们需要对其造成大于等于H点的伤害
所以需要使用技能的次数为 $\lceil H/A \rceil$

因为每次需要选一个区间
这只怪兽左边的怪兽都被杀死了,所以我们可以把这只怪兽所再的位置作为区间起点
那么即对区间 $[X, X + 2 ? D]$ 的所有怪兽造成了 $\lceil H/A \rceil*A$ 的伤害

因此在每次遍历到这只怪兽的伤害,我们需要判断它是否已经死亡了
所以我们需要查询单点位置加了多少

动态区间加,单点查询
可以使用树状数组/分块/线段树

考虑 $[X, X + 2 ? D]$ 的范围太大,无法作为数组下标,因此我们需要对其离散化
时间复杂度： $O n l o g n$

#include<bits/stdc++.h>
using namespace std ;
#define x first
#define y second 
#define pll pair<int,int>
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int N = 1e6 + 10 ;
#define int long long
int n , d , a ;
vector<pll> q ;
int tr[N] ;
vector<int> v ;

int get(int x)
{
    return lower_bound(v.begin() , v.end() , x) - v.begin() + 1 ;
}
int lowbit(int x)
{
    return x & -x ;
}
int sum(int x)
{
    long long res = 0 ;
    for(int i = x ; i ; i -= lowbit(i)) res += tr[i] ;
    return res;
}
void add(int x , int c)
{
    for(int i = x ; i <= N - 10 ; i += lowbit(i)) tr[i] += c ;  
}

signed main()
{
    cin >> n >> d >> a ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int l , r ;
        scanf("%lld %lld",&l , &r) ;
        q.pb({l , r}) ;
        v.pb(l) , v.pb(l + 2 * d + 1);
    }
    sort(all(q)) , sort(all(v)) ;  // 排序
    v.erase( unique(all(v)) , v.end() ) ; // 去重
    int res = 0 ;
    for(auto i : q)
    {
        int l = i.x , r = i.y ;
        r = r + sum(get(i.x)) ; // 本身的生命值加上单点查询的值
        if(r <= 0) continue ; // 如果已经死亡了,跳过这只怪兽
        int k = (r + a - 1) / a ; // 需要使用的技能次数
        res += k ; 
        add(get(i.x) , - k * a) , add(get(i.x + 2 * d + 1) , k * a) ;
        // 区间加上造成的伤害值
    }
    cout << res ;
    
    return 0 ;
}