题解：P10786 [NOI2024] 百万富翁
MoLing_qwq
·
·
题解
场外围观者来写一下 NOI 2024 D1T2 的题解。
话说为什么 D1T2 出交互题？为了让选手心态崩溃吗？
题目大意
一个长为 N 的数组 W_i，你可以发起 T 组共不超过 S 个询问，形如 W_i 与 W_j 哪个更大。求出最大数。（原题面中的请求就是一组询问，下同）
测试点 1
询问组数只有 1，但个数有 \dfrac{N(N-1)}{2}，那么对任意 1\le i\lt j\le N 做 (i,j) 询问即可。比 N-1 个数大的那个数就是最大数。
测试点 2
思路
如果没有 $T$ 的限制，那么询问 $N-1$ 次就能得到最大数。
有了询问**组数**的限制后，应当确定一个思路：每组询问将**可能的最大数集合** $S$ **缩小**。初始 $S=\{1,2,\dots,N\}$，目标是在 $8$ 组询问后**将 $|S|$ 缩小至 $1$**。
由于交互库自适应，只有将一个集合中的数**两两做询问**，才能在**一组询问**中确定这个集合的最大数。
如果**一组询问中**希望将 $S$ 的大小除以 $2$，那么应当将 $S$ 分为 $\dfrac{|S|}{2}$ 组（关于可能的 $2\nmid|S|$ 情况暂不详细讨论），每组 $2$ 个数，之间做 $1$ 个询问。一共做 $\dfrac{|S|}{2}$ **个**询问。
类似地，如果希望将 $S$ 的大小除以 $k$，那么应当将 $S$ 分为 $\dfrac{|S|}{k}$ 组（关于可能的 $k\nmid|S|$ 情况也暂不讨论），每组 $k$ 个数，之间做 $\dfrac{k(k-1)}{2}$ 个询问。一共做 $\dfrac{|S|(k-1)}{2}$ 个询问。
可以将询问的**个数**当作**一组询问的代价**，那么为了让 $|S|$ 缩小更多，代价就更大。本题就是要在询问组数与代价之间**做出平衡**。
### 求一个较好的代价与方案
注意到 $1099944$ 略大于 $N=10^6$，因此每次当然可以大胆地让 $|S|$ 除以 $2$，这样总询问次数为 $\dfrac{|S|}{2}+\dfrac{|S|}{4}+\dfrac{|S|}{8}+\dots$，在 $|S|$ 也就是 $N$ 左右。当然这是远远不够的。
手玩可以发现，前几组询问只能使 $|S|$ 除以 $2$；当 $|S|$ 缩小到 $10^4$ 级别时，多出的 $99944$ 个询问，就允许将 $|S|$ 除以更大的数（例如 $3,4,5,6$）；并且，$|S|$ 大幅下降后，接下来每组询问的代价也会下降。
考虑设计 DP 求最小代价。采用倒推，设 $dp_{i,j}$ 表示**剩余 $j$ 次询问**，$|S|=i$ 时，将 $|S|$ 缩小为 $1$ 的代价（**其实这时不一定是最小代价，只是一种可行代价，让它尽量小**）。
初始 $dp_{i,1}=\dfrac{i(i-1)}{2}$。
枚举 $j=2,\dots,8$，枚举 $i$，再枚举 $k$ 表示希望让 $|S|$ 除以 $k$。此时钦定 $dp_{i,j}$ 从 $dp_{i',j-1}$ 转移，其中 $i'=\lceil\dfrac{i}{k}\rceil$。转移方程为 $dp_{i,j}=\min\{dp_{i,j},dp_{i',j-1}+\operatorname{calc}(i,k)\}$，其中 $\operatorname{calc}(i,k)$ 表示将 $S$ 分为 $i'=\lceil\dfrac{i}{k}\rceil$ 组，**每组之间两两询问**所需代价。
时间复杂度是 $O(N^2)$（因为 $i,k$ 均为从 $1$ 到 $N$）。其实可以优化，后面再说。
计算 $\operatorname{calc}(i,k)$ 时，设 $i=qk+r$，$0\le r\lt k$。
若 $r=0$ 则就是将 $S$ 的 $i$ 个元素分成 $q$ 组，一组 $k$ 个，代价 $\dfrac{qk(k-1)}{2}$。
若 $r\neq 0$，则 $i'=q+1$。考虑假想有 $i'$ 组，每组 $k$ 个数，则共有 $i'k=(q+1)k$ 个数，代价 $\dfrac{(q+1)k(k-1)}{2}$。但这样多了 $k-r$ 个数。若 $i'\ge k-r$，则从 $k-r$ 组中去除一个数即可，代价减少了 $(k-r)(k-1)$（因为每个多余的数和组内其余 $k-1$ 个数均不用询问了）。
若 $i'\lt k-r$ 怎么办？事实上，根本不需要担心，因为这种情况**可以忽略**。
手玩时还可以发现，第 $7$ 组询问之前，$|S|$ 很难下降到 $1000$ 及以下，那么第 $7$ 次询问的目标是将 $|S|$ 除以 $k_7$，$k_7$ 不会太大，一般 $k_7\le 30$。
于是，$i'\ge\dfrac{i}{k}=\dfrac{|S|}{k_7}\gt 33\gt k_7=k\gt k-r$。
实现时就是在 DP 中枚举 $i=1001,1002,\dots,N$，$j=2,3,\dots,30$。时间复杂度的问题也解决了，变成了 $O(N)$（常数巨大）。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
#define INF 0x3f3f3f3f3f3f3fll
#define ll long long
ll dp[N+1][10],pre[N+1][10],v;
inline ll calc(ll n,ll k){
static ll q,r;q=n/k,r=n%k;
if(r==0)return q*(k*(k-1)/2);
if(q+1>=k-r)return (q+1)*(k*(k-1)/2)-(k-r)*(k-1);
return 0;
}
int main(){
for(ll i=1;i<=N;++i)dp[i][1]=i*(i-1)/2;
for(ll i=2;i<=8;++i){
for(int j=1;j<=N;++j)dp[j][i]=INF;
for(ll j=1001;j<=N;++j){
for(ll k=2;k<=30;++k){
v=dp[(j-1)/k+1][i-1]+calc(j,k);
if(v<dp[j][i])dp[j][i]=v,pre[j][i]=k;
}
}
}
printf("%lld\n",dp[N][8]);
int pos=N;
for(int i=8;i>=2;--i){
printf("%d %lld (%lld)\n",pos,pre[pos][i],calc(pos,pre[pos][i]));
pos=(pos-1)/pre[pos][i]+1;
}
printf("%d %d (%lld)\n",pos,pos,pos*(pos-1)/2);
return 0;
}
```
### 优化方案
看一下 DP 的输出：
```text
1099947
1000000 2 (500000)
500000 2 (250000)
250000 2 (125000)
125000 2 (62500)
62500 3 (62498)
20834 6 (52075)
3473 19 (31221)
183 183 (16653)
```
第一行是 $8$ 组询问的代价和，后面每一行为 $i,k,c$，代表 $S$ 集合的大小原本是 $i$，这组询问后它的大小除以了 $k$（上取整），代价为 $c$。
现在的总代价是 $1099947$，与目标 $1099944$ 只差了 $3$，接近正解了！
考察一下每组询问对 $|S|$ 的分法：
前四组，$|S|$ 除以了 $2$，分组时没有出现多余，不好优化。
第五组询问时，分法为 $62500=20832\times 3+2\times 2$。
第六组询问时，分法为 $20834=3469\times 6+4\times 5$。
第七组询问时，分法为 $3473=179\times 19+4\times 18$。
第八组询问只分了一组 $183=1\times 183$。
将第五组询问的 $2\times 2$ 合并为一组 $4$，代价增加了 $6-1-1=4$。
然而这样**第六组询问时 $|S|$ 减少了 $1$**，变为 $20833$。
将 $20833$ 分为 $3471\times 6+1\times 7$。这样的代价是 $52086$，比原来的 $52075$ 增加了 $11$。
但是这样**第七组询问的 $|S|$ 就减少了 $1$**。可以从大小为 $19$ 的组中减少一个数，这个数不再与组内的其余 $18$ 个数询问，代价减少了整整 $18$！
总代价变化为 $4+11-18=-3$，也就是减少了 $3$。这就得到了正解！
```cpp
#include<bits/stdc++.h>
#include "richest.h" //delete this in luogu.com.cn?
#define n 1000009
int richest(int N,int T,int S);
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
int siz[n];
std::vector<int> res,a,b,ret;
std::vector<int> shrinker(std::vector<int> strategy,std::vector<int> lst){
a.clear();b.clear();
static int pos;pos=0;
for(int i:strategy){
for(int j=pos;j<pos+i;++j)for(int k=pos;k<j;++k)
a.push_back(lst[j]),b.push_back(lst[k]);
pos+=i;
}
res=ask(a,b);
for(int i:lst)siz[i]=0;
ret.clear();
static int cnt;cnt=0;pos=0;
for(int i:strategy){
for(int j=pos;j<pos+i;++j)for(int k=pos;k<j;++k)++siz[res[cnt]],++cnt;
for(int j=pos;j<pos+i;++j)if(siz[lst[j]]==i-1)ret.push_back(lst[j]);
pos+=i;
}
return ret;
}
std::vector<int> s,l;
int richest(int N,int T,int S){
if(N==1000){
s.clear();s.push_back(N);
l.clear();for(int i=0;i<N;++i)l.push_back(i);
return shrinker(s,l)[0];
}
else{//N==1000000
s.clear();for(int i=0;i<500000;++i)s.push_back(2);
l.clear();for(int i=0;i<N;++i)l.push_back(i);
l=shrinker(s,l);
s.clear();for(int i=0;i<250000;++i)s.push_back(2);
l=shrinker(s,l);
s.clear();for(int i=0;i<125000;++i)s.push_back(2);
l=shrinker(s,l);
s.clear();for(int i=0;i<62500;++i)s.push_back(2);
l=shrinker(s,l);
s.clear();for(int i=0;i<20832;++i)s.push_back(3);s.push_back(4);
l=shrinker(s,l);
s.clear();for(int i=0;i<3471;++i)s.push_back(6);s.push_back(7);
l=shrinker(s,l);
s.clear();for(int i=0;i<178;++i)s.push_back(19);for(int i=0;i<5;++i)s.push_back(18);
l=shrinker(s,l);
s.clear();s.push_back(183);
return shrinker(s,l)[0];
}
}
```
另外，以上的代码是在本题数据仍未上传时写的。为了验证正确性，我写了一个非适应性的 grader：
```cpp
#include<bits/stdc++.h>
int richest(int N,int T,int S);
std::vector<int> ask(std::vector<int> a, std::vector<int> b);
static int testid;
static int N,T,S,W[1000009],ans,ret;
static std::mt19937 mt(time(0));
inline int ri(int a,int b){return mt()%(b-a+1)+a;}
static int m,t,s;
static std::vector<int> res;
std::vector<int> ask(std::vector<int> a, std::vector<int> b){
m=a.size();
if(m!=b.size()){
printf("#%d WA: Length of a and b are not the same.\n",testid);
exit(1);
}
++t;if(t>T){
printf("#%d WA: Too many requirements, get already %d/%d.\n",testid,t,T);
exit(1);
}
s+=m;if(s>S){
printf("#%d WA: Too many queries, get already %d/%d.\n",testid,s,S);
exit(1);
}
res.clear();
for(int i=0;i<m;++i){
if(W[a[i]]>W[b[i]])res.push_back(a[i]);
else res.push_back(b[i]);
}
return res;
}
int main(){
std::scanf("%d%d%d",&N,&T,&S);
for(testid=1;testid<=10;++testid){
t=s=0;
for(int i=0;i<N;++i)W[i]=i;
for(int i=0;i<N;++i)std::swap(W[i],W[ri(i,N-1)]);
for(int i=0;i<N;++i)if(W[i]==N-1)ans=i;
ret=richest(N,T,S);
if(ret!=ans){
printf("#%d WA: Answer is %d, you returned %d.\n",testid,ans,ret);
return 1;
}
printf("#%d AC: Correct.\n",testid);
}
return 0;
}
```