Subtask 2
不难想到每次请求把候选点集合二等分并对应连边，每条边必然排除一个数。于是每次请求排除一半候选点。可以做到 t=20,s=106t=20,s=106，期望得分 1111。
题目要求 t≤8,s≤1099944t≤8,s≤1099944。我们需要用查询次数换请求次数。10999441099944 这样的奇怪限制启发我们 dp。设 fk,ifk,i 为用 kk 次请求，把 ii 个候选点缩减到 11 个的最少查询次数，答案即为 f8,Nf8,N。转移为：
fk,i=min1≤j<i(fk−1,j+w(j,i))fk,i=1≤j<imin(fk−1,j+w(j,i))
其中 w(j,i)w(j,i) 为一次请求把 ii 个候选点缩减到 jj 个的最小查询次数。现在问题变成如何计算 ww。
对于每次请求，我们不妨把查询视作无向图 GG 的边。那么交互库会把图定向成 DAG（大指向小），有入度的点一定会被排除，只保留入度为 00 的点。
因此在一次请求中留下来的点集中两两无边，是 GG 的独立集。反过来，任意独立集（或其超集）都能取到：将独立集安排在拓扑序最前面，然后按照拓扑序给边定向就能给出构造。
因此，如果我们希望一次请求后最多剩下 jj 个候选点，必须保证
α(G)≤jα(G)≤j
其中 α(G)α(G) 是 GG 的最大独立集大小。因此 w(j,i)w(j,i) 就转化为有 ii 个点且满足 α(G)≤jα(G)≤j 的图 GG 的最小边数。
手模小样例，发现一个比较优秀的构造：把 ii 个点平均分成 jj 组，每组连成完全图，总边数为
w(j,i)=(imodj)⋅(⌊i/j⌋+12)+(j−(imodj))⋅(⌊i/j⌋2)w(j,i)=(imodj)⋅(2⌊i/j⌋+1)+(j−(imodj))⋅(2⌊i/j⌋)
事实上，可以证明这是最优构造：
注意到，GG 的独立集和补图 G‾G 中的团一一对应。因此
α(G)≤j⟺Kj+1∉G‾α(G)≤j⟺Kj+1∈/G
而 GG 的边数最少等价于 G‾G 的边数最多。
这正是图兰定理：
在所有 ii 个点且不包含 Kj+1Kj+1 的图中，边数最多的图是具有 ii 个点的完全 jj 分图（即上面构造的图的补图）。
现在还有一个问题：朴素 dp 是 O(tn2)O(tn2) 的，会 T。暴力枚举发现 ww 满足四边形不等式。这一点可以证明：
往证 ∀j<i∀j<i 有
w(j,i)+w(j+1,i+1)≤w(j+1,i)+w(j,i+1)w(j,i)+w(j+1,i+1)≤w(j+1,i)+w(j,i+1)
移项，得
w(j+1,i+1)−w(j+1,i)≤w(j,i+1)−w(j,i)w(j+1,i+1)−w(j+1,i)≤w(j,i+1)−w(j,i)
而
w(j,i+1)−w(j,i)=(⌊i/j⌋+12)−(⌊i/j⌋2)w(j,i+1)−w(j,i)=(2⌊i/j⌋+1)−(2⌊i/j⌋)
代入原式，得
(⌊i/(j+1)⌋+12)−(⌊i/(j+1)⌋2)≤(⌊i/j⌋+12)−(⌊i/j⌋2)(2⌊i/(j+1)⌋+1)−(2⌊i/(j+1)⌋)≤(2⌊i/j⌋+1)−(2⌊i/j⌋)
即
⌊i/(j+1)⌋≤⌊i/j⌋⌊i/(j+1)⌋≤⌊i/j⌋
该式恒成立，因此原式成立。证毕。
于是决策单调性成立，可以用分治算法优化到 O(tnlogn)O(tnlogn)。发现 f8,N=1099944f8,N=1099944，恰好满足限制，从而通过本题。
Code
#include "richest.h" |
#include <vector> |
#include <bitset> |
#define rep(i,a,b) for(int i(a);i<b;++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<MAXN> 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<MAXN> 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][i]=f[k-1][j]+w(j,i); |
g[k][i]=j; |
} |
} |
if(l<i) calc(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()<a){ |
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()<a+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(); |
} |
分类: 题解
免责声明：本内容来自平台创作者，博客园系信息发布平台，仅提供信息存储空间服务。
好文要顶 关注我 收藏该文 微信分享
xiaoniu142857
粉丝 - 1 关注 - 0
+加关注
0
0
升级成为会员
« 上一篇： 洛谷-P7998 [WFOI - 01] 猜数 题解
» 下一篇： 洛谷-P11942 [KTSC 2025] 重塑矩阵 题解
posted @ 2026-05-16 22:41 xiaoniu142857 阅读(80) 评论(1) 收藏 举报
