这场总体难度不算大（感觉C，D，E的难度居然出奇的一致）
如果码力再强点，也许是能AK的，可惜只切了四题。不过一下子rk涨了100多，还是有点出乎我的意料hh
假设一个单位有H点生命值，你拥有一个技能能修改该单位的生命值H。
若在某一时刻t发动该技能，效果如下：首先，在t时刻对该单位在造成a点伤害；然后在t+1,t+2,t+3,...,t+c时刻治疗该单位，每次均治疗b点生命值
技能的冷却时间为d，也就是说，若在时刻t发动技能，则在t+d时刻才能继续使用该技能
0时刻单位的初始生命值为H，H>0。若某一时刻该单位生命值≤0，则该单位被击杀
若要使该单位被击杀，H的最大值为多少？若无解则输出-1。
数据范围
共有T组数据(1≤t≤50)，输入为a,b,c,d，其中1≤a,b,c,d≤106
要求输出一个整数，即满足条件H的最大值。
题解
拿到这种题，首先应分析一下隐藏的性质：
- 若a>b×c，则H无最大值，答案必为-1。故接下来只需讨论a≤b×c的情况
- 应该在冷却时间结束之后马上继续释放技能
- 当t≤c后，那么前面释放过的已经作用完的技能其实是为该单位增加了b∗c−a点的生命值，故只需要考虑t<c的情况
- 该单位的生命值最低的时刻应该是刚好造成伤害的时刻，即0,d,2d,...,kd
于是乎，对于每一个在t=0,d,2d,...,kd中且满足t<c的时刻，找出最优时刻计算答案即可
同时，由于H是关于t的凸函数，故可以用三分来找答案
O（1）做法
先推式子，然后求导得到生命值最低的时刻再计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,d;
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a>b*c)printf("-1\n");
else {
ll k=a/(b*d),ans=0;
ans=max(ans,(k+1)*a-(1+k)*k/2*b*d);
k++;
ans=max(ans,(k+1)*a-(1+k)*k/2*b*d);
printf("%lld\n",ans);
}
}
return 0;
}
|
三分
说实话都能求导找k的最优解了，还用三分就挺zz的
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,d,ans;
ll get_num(ll k){
return (k+1)*a-(1+k)*k/2*b*d;
}
void solve(ll l,ll r){
while(l<r-1){
ll lm=l+(r-l)/3,rm=r-(r-l)/3;
if(get_num(lm)>=get_num(rm)){
ans=max(get_num(rm),ans);
r=rm-1;
}
else {
ans=max(get_num(lm),ans);
l=lm+1;
}
}
ans=max(ans,max(get_num(l),get_num(r)));
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(a>b*c)printf("-1\n");
else {
ans=0;
ll k=c/d;
solve(0,k);
printf("%lld\n",ans);
}
}
return 0;
}
|
