CF573E 题解

E1_de5truct0r · 2023-07-20 11:54:03 · 个人记录

由于我实在是不太会这些算法也没有思维能力，所以我直接退火解决了此题。

退火思路

首先有一个显然的结论，就是所有正数都选。这个比较显然。

那么我们考虑把每个数的状态，即 选/不选 表示成 0/1，这样就得到了一个二进制串。初始的二进制串我们就设定为每个正数选、负数不选。我们记这个二进制串为 c 数组。

考虑一次随机扰动我们怎么维护他的 \sum b_i \times i。显然我们可以预处理出来一开始的 \sum b_i \times i。

考虑每次如果添加了一个 j，他自身有一个贡献，他后面的所有数也有一个贡献，加起来就是 \sum\limits_{i<j}[c_i=1]a_j+\sum\limits_{i>j}a_i。

因此，对于每次扰动，我们只需要维护一个单点插入 / 删除、区间求值打的东西即可做到 O(\log n)。显然这个插入 / 删除和修改没啥区别，所以我们考虑使用树状数组，因为它常数小速度快。

但是这样并不是最优，因为模拟退火的关键在于每次的随机扰动要尽可能快速且有效。所以我们每次扰动的时候应该忽略正数，仅仅考虑负数。

这样就得到了一个正确性比较高的东西了。

一些调参

我自己调参是随机了一些 n=5 \times 10^6 的数据，退火设置成 1s，然后每次随机种子进行试验，找到一个平均大小较大的参数。然后我再固定参数调试不同种子，最后发现选 19260817 还是不错的。开到 6s 试一下发现所有的都过了（我也不知道是不是对的，但是和我退火 30s 出来的结果一样，就暂且这么认为。）

这是我生成数据的代码：

#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(time(0));

int main(){
    freopen("Dtest.in","w",stdout);
    int n=5000000; cout<<n<<'\n';
    for(int i=1;i<=n;i++){
        int op=rnd()%3;
        if(op!=0) cout<<rnd()%n+1<<' ';
        else cout<<-((int)rnd()%100+1)<<' '; 
    }
    return 0;
}

Code & Submission

改完之后我交了一发就过了，所以不太确定是不是每发都能过，总之正确率不低。