题解：CF2035E Monster

Shunpower · 2024-11-06 22:17:39 · 题解

这是一篇使用爬山的题解。

This is a solution using the Hill-Climbing algorithm.

考虑先写出答案的式子。

Consider representing the answer as an expression first.

容易想到枚举最终武器的攻击力 d。此时贪心地发现，假设不存在每 k 次增加就需要攻击的限制，那么我们一定是先增加完再攻击，因为如果把增加放在后面，那么交换顺序就可以使攻击造成的伤害更大，并且花费相等。

It is easy to think of enumerating the final weapon's damage d. And we can realise that greedily, assuming there is no restriction on the need to attack every k increase, we must finish increasing before attacking, because if we put the increase after it, just swapping the order allows the attacks to do more damage and cost equally.

即便存在每 k 次就需要攻击的限制，这个想法显然也是正确的，只不过是多了一些强制攻击造成的影响。

Even if there exists a restriction of needing to attack every k times, the idea is clearly correct and can hold on, considering the effects caused by the forced attacks every k times.

显然，我们需要增加攻击力 d 次，产生 dx 的花费。这 d 次增加又会发起强制攻击 \left\lfloor\frac{d}{k}\right\rfloor 次，产生 \left\lfloor\frac{d}{k}\right\rfloor y 的花费，应用等差数列求和可以发现这部分攻击会造成 r=k+2k+\cdots \left\lfloor\frac{d}{k}\right\rfloor k=\frac{(\left\lfloor\frac{d}{k}\right\rfloor k+k)\left\lfloor\frac{d}{k}\right\rfloor }{2} 的伤害，而剩下的 z-r 的部分还需要 \left\lceil\frac{z-r}{d}\right\rceil 次攻击，产生 \left\lceil\frac{z-r}{d}\right\rceil y 的花费。

Obviously, we need to increase the damage of the weapon d times, causing dx cost. This d times increase will lead to the forced attack \left\lfloor\frac{d}{k}\right\rfloor times, causing \left\lfloor\frac{d}{k}\right\rfloor y cost. By calculating the sum of Arithmetic Progression we can realise this portion of attack causes damage r=k+2k+\cdots \left\lfloor\frac{d}{k}\right\rfloor k=\frac{(\left\lfloor\frac{d}{k}\right\rfloor k+k)\left\lfloor\frac{d}{k}\right\rfloor }{2} , and the remaining z-r portion also requires \left\lceil\frac{z-r}{d}\right\rceil times, causing \left\lceil\frac{z-r}{d}\right\rceil y cost.

所以，每个 d 对应的最小花费，也就是答案可以用一个公式直接写出：

Therefore, the minimum cost corresponding to each d, i.e., the answer, can be expressed directly in a formula:

我们可以使用一个函数 f(d) 表示 d 对应的答案。那么实际上我们的任务就是计算 \min\limits_{d=1}^z f(d)。（d 的上界显然是 z）。

We can use a function f(d) to represent the answer corresponding to d. Then in fact, our task is to calculate \min\limits_{d=1}^z f(d). (The upper bound on d is obviously z).

我们可以注意到，f(d) 大约是一个单谷函数，这让我们想到尝试随机化算法。

We can notice that f(d) approximately is a single-valley function, which makes us think of trying a randomisation algorithm.

考虑直接爬山或者模拟退火。不妨初始时设置答案位于 d=\frac{z}{2} 处，设置温度 T 为 z，每次直接将 d 随机向两侧移动随机小于等于 T 的长度，如果可以得到更优秀的 f(d) 则接纳并将答案挪动过去。显然，当 T<1 时将无法产生有效移动，所以设置阈值为 eps=1。设置降温系数 t=0.9999 表现较好。

Consider directly applying Hill-Climbing or Simulated Annealing algorithm. It is better to initially set the answer to be located at d=\frac{z}{2}, and set the temperature T to z. Each time, we directly move d randomly to either side by a length randomly less than or equal to T, and then accept and move the d over if a better f(d) can be obtained. Obviously, when T<1 no effective move will be produced, so set the threshold to eps=1.

Setting the cooling factor t=0.9999 performs fine.

为了让解的质量更好，我们可以一边做一边将答案取 \min。最后还可以暴力计算解的左右 10^5 位的答案，避免微小的偏差。

To make the quality of the solution better, we can take \min of the answer while moving d. Finally we can also calculate the answer in the left and right 10^5 of the solution brutally to avoid small deviations.

不知道为啥我写的模拟退火在这题里面表现不如爬山。

I haven't known why my Simulated Annealing algorithm does not perform as well as Hill-Climbing within this problem.

下面的代码可以在 1.4 秒的时间通过本题。

The following code will pass the problem in 1.4 seconds.

int tc;
ll x,y,z,k;
ll calc(ll d){
    return d*x+(d/k)*y+(z-(d/k*k+k)*(d/k)/2+(d-1))/d*y;
}
double rd(){
    return (double)rand()/RAND_MAX;
}
void solve(){
    cin>>x>>y>>z>>k;
    ll ans=1e18;
    ll L=1,R=z;
    int x=max(1ll,z/2);
    double T=z,eps=1,t=0.9999;
    while(T>=eps){
        ll del=T*(rd()*2-1);
        ll nx=x+del;
        nx=min(nx,R);
        nx=max(nx,L);
        ans=min(ans,calc(x));
        double delta=calc(nx)-calc(x);
        if(delta<0) x=nx;
       // else if(rd()<=exp(-delta/calc(max(1.0,T)))) x=nx;
        T*=t;
    }
    fr1(i,max(1,x-100000),x+100000) ans=min(ans,calc(i));
    cout<<ans<<'\n';
}