百万富翁 NOI2024

[NOI2024] 百万富翁

神仙题目。

写完后看题解发现没有一个用试图优化 DP 的，全都是注意力惊人。

题目链接： [NOI2024] 百万富翁 。

题目描述：

小 W 有一个长度为 nn 的序列 ww 。你可以经行多组询问。每一组询问里包含若干个普通询问。每一个普通询问为形如 (i,j)(i,j) 的二元组，小 W 会对于每一组询问，一次性告诉你这一组里每一个普通询问 (i,j)(i,j) 中 wiw_i 和 wjw_j 谁要更大。

你需要在不超过 TT 组询问，一共不超过 SS 个普通询问内找出数组的最大值。

有两个子任务：

子任务编号 TT SS nn
11 11 499500499500 10001000
22 88 10999441099944 10000001000000

交互库是自适应的。

子任务一直接两两枚举即可。

交互库自适应这一点可以告诉我们，对于一组点，如果我只能询问一组的话，一定需要两两枚举询问。因为如果我们哪怕少询问了一个点，交互库也可以直接将那个点作为最优解。

所以我们必须把这些点分开，分多组求解。

也就是说，我们的策略应该是，先将这些点随意的划分为若干组，每组通过两两枚举求出一个最大值，然后让所有的最大值递归这一过程。

那么我们的问题就有两部分：如何划分最优，以及每次应该划分多少组。

先看第一个问题，如何划分。

由二次函数的性质，有 (a+b)2>a2+b2(a+b)^2>a^2+b^2 ，所以说，为了消耗更少，我们应该尽量平均的划分。

具体来说，如果我们要将 nn 个点划分为 mm 组，设最小代价为 G(n,m)G(n,m) ，且将 kk 个点划分为一组的代价为 F(k)F(k) ，那么就有：

G(n,m)=(m−n mod m)F(⌊nm⌋)+(n mod m)F(1+⌊nm⌋)G(n,m)=(m-n\bmod m)F(\lfloor\frac{n}{m}\rfloor)+(n\bmod m)F(1+\lfloor\frac{n}{m}\rfloor)

于是这一部分搞定了。

然后就是第二个问题，每次划分多少组。

你可以直接模拟退火或者搜索。

这里没有什么好方法，你可以直接 DP 做。

设 fi,jf_{i,j} 为第 ii 次分组询问，且这次分完前剩下 jj 组的情况下的最小代价。

转移挺显然的，边界条件 f0,1=0,f0,i=∞f_{0,1}=0,f_{0,i}=\infty 。

但是直接做的话复杂度 O(n2)\mathcal{O}(n^2) 。

你可以直接抄别人构造好的或打表。

然后，注意到这个转移式子具有决策单调性（挺显然的，理由和刚才的二次函数一样）。

于是直接做一个决策单调性就行了。复杂度 O(nlog⁡n)\mathcal{O}(n\log n) 。

然而你 TLE 了，原因是每次要决策单调性 88 次，题目有 1010 组询问，却只开 6s6s 。

注意到这个题目的子任务二的 nn 是固定的，而我们的决策单调性的做法只依赖于 nn 。

也就是说我们可以提前打表打出 ff 的转移。所以最终还是用了打表。

代码：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
#include "richest.h"
using V=vector<int>;
const int N=1000010;
using ll=long long;
const int inf=1e9;
int p[9][N],up,f[9][N];
ll F(ll x){return x*(x-1)/2;}
ll G(int a,int b){return (b-a%b)*F(a/b)+a%b*F(a/b+1);}
void upd(int j,int i,int K){
    ll t=G(i,j)+f[K-1][j];
    if(t<f[K][i])f[K][i]=t,p[K][i]=j;
}
void cdq(int l,int r,int K){
    if(l+1>=r)return ;
    int mid=(l+r)>>1;
    for(int i=p[K][l];i<=p[K][r];i++)upd(i,mid,K);
    cdq(l,mid,K);
    for(int i=l+1;i<=mid;i++)upd(i,r,K);
    cdq(mid,r,K);
}
V query(V tmp,int m){
    int n=tmp.size();
    int cnt1=m-n%m,cnt2=n%m;
    int A=n/m,B=n/m+1;
    V u,v,res;
    for(int i=0;i<cnt1;i++){
        int st=i*A,ed=(i+1)*A;
        for(int j=st;j<ed;j++)for(int k=j+1;k<ed;k++)
            u.push_back(tmp[j]),v.push_back(tmp[k]);
    }
    for(int i=0;i<cnt2;i++){
        int st=cnt1*A+i*B,ed=cnt1*A+(i+1)*B;
        for(int j=st;j<ed;j++)for(int k=j+1;k<ed;k++)
            u.push_back(tmp[j]),v.push_back(tmp[k]);
    }
    V ans=ask(u,v),rd(n,0);
    int kid=0;
    for(int i=0;i<cnt1;i++){
        int st=i*A,ed=(i+1)*A;
        for(int j=st;j<ed;j++)for(int k=j+1;k<ed;k++,kid++)
            rd[ans[kid]==tmp[j]?k:j]++;
        for(int j=st;j<ed;j++)if(!rd[j]){res.push_back(tmp[j]);break;}
    }
    for(int i=0;i<cnt2;i++){
        int st=cnt1*A+i*B,ed=cnt1*A+(i+1)*B;
        for(int j=st;j<ed;j++)for(int k=j+1;k<ed;k++,kid++)
            rd[ans[kid]==tmp[j]?k:j]++;
        for(int j=st;j<ed;j++)if(!rd[j]){res.push_back(tmp[j]);break;}
    }
    return res;
}
int P[9]={
    0,
    500000,
    250000,
    125000,
    62496,
    20832,
    3472,
    183,
    1
};
int richest(int n,int T,int S){
    up=min({T,n,8});
    if(n==1000){
        for(int i=2;i<=n;i++)f[0][i]=inf;
        for(int i=1;i<=up;i++){
            for(int j=1;j<=n;j++)f[i][j]=inf,p[i][j]=1;
            f[i][1]=0;
            upd(1,n,i);
            cdq(1,n,i);
        }    
        int K=n;
        V tmp(n);
        for(int i=0;i<n;i++)tmp[i]=i;
        for(int i=up;i>=1&&K>=1;i--){
            tmp=query(tmp,p[i][K]);
            K=p[i][K];
        }
        return tmp[0];
    }
    int K=n;
    V tmp(n);
    for(int i=0;i<n;i++)tmp[i]=i;
    for(int i=1;i<=up&&K>=1;i++){
        tmp=query(tmp,P[i]);
        K=P[i];
    }
    return tmp[0];
}