2021-2022-2 ACM集训队每周程序设计竞赛（13）题解

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

#include
using namespace std ;
const int N = 1e6 + 10 ;

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

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

#include
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 ;
}

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

#include
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 ;
}

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

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

#include
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 Ai Ai点伤害当做物品的体积, B i Bi Bi点魔力值当做物品的价值
N N N个技能等价于 n n n个物品,并且每件物品可以重复使用
题目等价于求背包体积为 [ H , ∞ ] [H,infty] [H,∞]的最小价值
(其血量小于等于0即为死亡)所以背包体积为 [ H , ∞ ] [H,infty] [H,∞]

回忆一下背包体积为 m m m的求法
我们假设 f [ j ] f[j] f[j]表示体积为 j 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 , ∞ ] [H,infty] [H,∞]的最小价值
只需要

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 Onm Onm

#include
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 ;
}

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

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

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

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

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

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

#include
using namespace std ;
#define x first
#define y second 
#define pll pair
#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 q ;
int tr[N] ;
vector 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 ;
}