洛谷-P10786 [NOI2024] 百万富翁 题解

Subtask 1

直接每对 $(i,j)$ 均询问一次，然后找出比其他数都大的一个即可。

Subtask 2

不难想到每次请求把候选点集合二等分并对应连边，每条边必然排除一个数。于是每次请求排除一半候选点。可以做到 $t=20,s=10^6$，期望得分 $11$。

题目要求 $t\le 8,s\le 1099944$。我们需要用查询次数换请求次数。$1099944$ 这样的奇怪限制启发我们 dp。设 $f_{k,i}$ 为用 $k$ 次请求，把 $i$ 个候选点缩减到 $1$ 个的最少查询次数，答案即为 $f_{8,N}$。转移为：

$$f_{k,i}=\min_{1\le j$$

其中 $w(j,i)$ 为一次请求把 $i$ 个候选点缩减到 $j$ 个的最小查询次数。现在问题变成如何计算 $w$。

对于每次请求，我们不妨把查询视作无向图 $G$ 的边。那么交互库会把图定向成 DAG（大指向小），有入度的点一定会被排除，只保留入度为 $0$ 的点。

因此在一次请求中留下来的点集中两两无边，是 $G$ 的独立集。反过来，任意独立集（或其超集）都能取到：将独立集安排在拓扑序最前面，然后按照拓扑序给边定向就能给出构造。

因此，如果我们希望一次请求后最多剩下 $j$ 个候选点，必须保证

$$\alpha(G)\le j$$

其中 $\alpha(G)$ 是 $G$ 的最大独立集大小。因此 $w(j,i)$ 就转化为有 $i$ 个点且满足 $\alpha(G)\le j$ 的图 $G$ 的最小边数。

手模小样例，发现一个比较优秀的构造：把 $i$ 个点平均分成 $j$ 组，每组连成完全图，总边数为

$$w(j,i)=(i\bmod j)\cdot\binom{\left\lfloor i/j\right\rfloor+1}{2}+\left(j-(i\bmod j)\right)\cdot\binom{\left\lfloor i/j\right\rfloor}{2}$$

事实上，可以证明这是最优构造：

注意到，$G$ 的独立集和补图 $\overline{G}$ 中的团一一对应。因此

$$\alpha(G)\le j\Longleftrightarrow K_{j+1}\notin\overline{G}$$

而 $G$ 的边数最少等价于 $\overline{G}$ 的边数最多。

这正是图兰定理：

在所有 $i$ 个点且不包含 $K_{j+1}$ 的图中，边数最多的图是具有 $i$ 个点的完全 $j$ 分图（即上面构造的图的补图）。

现在还有一个问题：朴素 dp 是 $O(tn^2)$ 的，会 T。暴力枚举发现 $w$ 满足四边形不等式。这一点可以证明：

往证 $\forall j$ 有

$$w(j,i)+w(j+1,i+1)\le w(j+1,i)+w(j,i+1)$$

移项，得

$$w(j+1,i+1)-w(j+1,i)\le w(j,i+1)-w(j,i)$$

而

$$w(j,i+1)-w(j,i)= \binom{\left\lfloor i/j\right\rfloor+1}{2}-\binom{\left\lfloor i/j\right\rfloor}{2}$$

代入原式，得

$$\binom{\left\lfloor i/(j+1)\right\rfloor+1}{2}-\binom{\left\lfloor i/(j+1)\right\rfloor}{2} \le \binom{\left\lfloor i/j\right\rfloor+1}{2}-\binom{\left\lfloor i/j\right\rfloor}{2}$$

即

$$\left\lfloor i/(j+1)\right\rfloor\le \left\lfloor i/j\right\rfloor$$

该式恒成立，因此原式成立。证毕。

于是决策单调性成立，可以用分治算法优化到 $O(tn\log n)$。发现 $f_{8,N}=1099944$，恰好满足限制，从而通过本题。

Code

#include "richest.h"
#include 
#include 
#define rep(i,a,b) for(int i(a);i
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
#define ll long long
#define il inline
using namespace std;
namespace{
    constexpr ll INF=1e16;
    int N,T,S;
    bool INITED;
}
namespace Case1{
    constexpr int MAXN=1000;
    bitset mk;
    vector<int> A,B,C;
    int solve(){
        if(!INITED){
            A.reserve(499500);
            B.reserve(499500);
            C.reserve(499500);
            INITED=true;
        }
        mk.reset();
        A.clear(),B.clear();
        rep(i,0,N-1) rep(j,i+1,N) A.eb(i),B.eb(j);
        C=ask(A,B);
        rep(i,0,499500) mk.set(C[i]==A[i]?B[i]:A[i]);
        rep(i,0,N) if(!mk[i]) return i;
        return 0;
    }
}
namespace Case2{
    constexpr int MAXN=1e6+1;
    ll f[9][MAXN];
    int g[9][MAXN];
    bitset mk;
    vector<int> A,B,C,D;
    il ll comb(ll x){
        return x*(x-1)/2;
    }
    il ll w(int m,int n){
        int a=n/m,b=n%m;
        return (m-b)*comb(a)+b*comb(a+1);
    }
    void calc(int k,int l,int r,int opt_l,int opt_r){
        int i=l+r>>1;
        g[k][i]=opt_l;
        rept(j,opt_l,min(opt_r,i-1)){
            if(f[k-1][j]+w(j,i)
                f[k][i]=f[k-1][j]+w(j,i);
                g[k][i]=j;
            }
        }
        if(lcalc(k,l,i-1,opt_l,g[k][i]);
        if(r>i) calc(k,i+1,r,g[k][i],opt_r);
    }
    int solve(){
        mk.reset();
        if(!INITED){  // 仅在初始时运行一次dp
            fill(f[0]+2,f[0]+N+1,INF);
            rept(k,1,8){
                fill(f[k]+1,f[k]+N+1,INF);
                calc(k,1,N,1,N);
            }
            A.reserve(f[8][N]),B.reserve(f[8][N]);
            C.reserve(f[8][N]),D.reserve(f[8][N]);
            INITED=true;
        }
        int k=8,n=N;
        while(n>1){
            int m=g[k][n];
            int len=w(m,n),a=n/m,b=n%m,p=0;
            A.clear(),B.clear(),D.clear();
            rep(_,0,m-b){
                while(D.size()
                    if(!mk[p]) D.eb(p);
                    ++p;
                }
                rep(i,0,D.size()-1){
                    rep(j,i+1,D.size()){
                        A.eb(D[i]),B.eb(D[j]);
                    }
                }
                D.clear();
            }
            rep(_,0,b){
                while(D.size()1){
                    if(!mk[p]) D.eb(p);
                    ++p;
                }
                rep(i,0,D.size()-1){
                    rep(j,i+1,D.size()){
                        A.eb(D[i]),B.eb(D[j]);
                    }
                }
                D.clear();
            }
            C=ask(A,B);
            rep(i,0,len){
                int u=C[i]==A[i]?B[i]:A[i];
                if(!mk[u]) mk.set(u),--n;
            }
            --k;
        }
        rep(i,0,N) if(!mk[i]) return i;
        return 0;
    }
}
int richest(int _N,int _T,int _S){
    N=_N,T=_T,S=_S;
    return N==1000?Case1::solve():Case2::solve();
}