题解：P10786 [NOI2024] 百万富翁

markding · 2024-07-29 18:50:24 · 题解

对于测试点 1 直接做一个大的循环赛即可，对于测试点 2 我们考虑 dp。

设 f_{i,j} 代表仅用 i 次请求，此时还剩 j 个人的最少查询总数。

最后一个式子中 a=\lfloor\frac{i}{p}\rfloor,b=i\bmod p，因此可以 O(n^2) 递推。

在第一个等号处，我们将 i 个人分成了 p 组，第 j 组有 a_j 个人，对每一组人进行循环赛（最后只剩下了 p 人），一共需要 \sum_{j=1}^p\frac{a_j(a_j-1)}{2} 次查询。对所有可能的分组方式取 \min 即可。

第二个等号处我们首先枚举 p，也就是分的组数，然后再枚举具体的分组方式。

关于最后一个等号的成立，有引理：C_n^2+C_{n+a}^2>C_{n+1}^2+C_{n+a-1}^2(a\ge2)，可以证明按上述方法贪心，序列最后会变为 p-b 个数字 a，以及 b 个数字 a+1（感性理解一下：因为最终序列的极差 <2，所以只能这样分）。

直接递推是非常缓慢的，我们可以利用多线程的方式来进行计算。

附如下多线程加速循环的代码（M 线程，代码中 M=15，可根据实际情况调整）：

#include<vector>
#include<thread>
#include<cstring>
#include<fstream>
#include<functional>
using namespace std;const int N=1000005,M=15;
long long f[9][N];int g[9][N];
int main()
{
    ofstream fout("D1T2.txt");
    memset(f,0x3f,sizeof f),f[0][1]=0;
    for(int k=1;k<=8;k++)
    {
        function<void(int)> func=[&](int i){
            for (int p=1;p<=i;p++)
            {
                long long ord=f[k-1][p]+1ll*(p-i%p)*(i/p)*(i/p-1)/2+1ll*(i%p)*(i/p)*(i/p+1)/2;
                if(f[k][i]>ord)f[k][i]=ord,g[k][i]=p;
            }};
        vector<thread> threads;
        threads.reserve(M);
        for(int i=0;i<M;i++)
        {
            threads.emplace_back([=,&func]()
                {for(int t=i;t<N;t+=M)func(t);});
        }
        for(int i=0;i<M;i++)threads[i].join();
        fout<<k<<" Complete"<<endl;
    }
    int pos=1000000;fout<<f[8][pos]<<endl;
    for(int i=8;i;i--)fout<<g[i][pos]<<' ',pos=g[i][pos];
    return 0;
}

该程序创建的文本 D1T2.txt 最后两行为：

1099944
500000 250000 125000 62496 20832 3472 183 1

代码略，按照上述分组方式构造即可。

程序实测本地运行时间 \sim 4h（本地 CPU 采用 Intel(R) Core(TM) i7-13700H）。

当然考场上不需要搞出最优，爆搜一下即可。

不过，我们也可以在本地提前跑一些小的数据并观察最优解，发现前几次都是直接两两分组。可以根据这个性质加速 dp。从 7 次开始，不断缩小两两分组的次数，直到找到最优解。实测代码经过优化后时间 <2h（代码略）。

附表：N=1000000 时不同 T 的所对应的 f_{T,N}: