我做的交互题少,所以不是很清楚自适应在通常情况下究竟意味着什么。
现在我明白了,它大概就是不能用随机化算法的意思吧,并且有时候可以直接推出自适应下的最优决策点,从而突破常规算法理论上界(比如某道CF的二分交互题,忘了是哪道了)
但是这题更怪,它不给你一个范围让你构造,而是直接告诉你:范围保证有解,意思是你可能需要用理论上的最优决策才能通过这个范围。
这就是为什么这题的标签不是构造,我们需要克服看到交互题后直接开始构造的惯性,而思考理论最优解。
其实想明白这一点过后,问题就比较简单了。我们知道一个常用的二进制分组的科技,给 n n n 瓶药编上 0 ∼ 2 m − 1 0\sim 2^m-1 0∼2m−1 的标号,标号的二进制就表示这瓶药要喂给的老鼠的集合,然后一轮实验下来,就可以根据死掉的老鼠的集合判断哪一瓶是毒药了。容易发现此题中二进制分组是理论最优的解法。
但是由于
m
m
m 不保证足够大,并且要求最后还要存活
k
k
k 只老鼠,合法的标号数量为
∑
i
=
0
m
−
k
(
m
i
)
\sum_{i=0}^{m-k}{m\choose i}
∑i=0m−k(im),可能会
<
n
方法确定了,还剩下怎么给药分组的问题。我们可以先处理出一个DP树组 f ( t , m ) f(t,m) f(t,m) 表示当前剩下 t t t 轮实验,存活的老鼠数量为 m m m,要求最后存活至少 k k k 只,并且保证能够确定毒药的情况下,药水总数的最大值。
显然
f
(
0
,
m
)
=
1
f(0,m)=1
f(0,m)=1。转移也很简单,只需要把合法标号对应的状态的DP值求和:
f
(
t
,
m
)
=
∑
s
=
0
2
m
−
1
[
m
−
c
n
t
s
≥
k
]
f
(
t
−
1
,
m
−
c
n
t
s
)
f(t,m)=\sum_{s=0}^{2^m-1}[m-cnt_s\ge k]f(t-1,m-cnt_s)
f(t,m)=s=0∑2m−1[m−cnts≥k]f(t−1,m−cnts)分组时直接按照DP值大小分即可。
#include"poison.h"
#include //JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=114514;
const ll INF=1e17;
int f[20][20],l,r,n,m,k,t,b[20],cnt[1<<16],pr[1<<16];
int solve(int N,int M,int K,int T){
n=N,m=M,k=K,t=T,l=0,r=n-1;
if(n==1)return 0;
for(int i=k;i<=m;i++)f[0][i]=1;
for(int s=1;s<(1<<m);s++)cnt[s]=cnt[s>>1]+(s&1);
for(int i=1;i<=t;i++)for(int j=k;j<=m;j++)
for(int s=0;s<(1<<j);s++)f[i][j]+=f[i-1][j-cnt[s]];
for(int i=0;i<m;i++)b[i]=i;
while(l<r&&t--){
pr[0]=f[t][m];
for(int s=1;s<(1<<m);s++)pr[s]=pr[s-1]+f[t][m-cnt[s]];
for(int i=l,j=0;i<=r;i++){
while(pr[j]<=i-l)j++;
for(int l=0;l<m;l++)if((j>>l)&1)feed(i,b[l]);
}
int ps=~done(),s=0;
for(int i=0;i<m;i++)if((ps>>b[i])&1)s|=(1<<i);
r=min(r,l+pr[s]-1),l+=pr[s]-f[t][m-cnt[s]];
m-=cnt[s];
for(int i=0,j=0;i<m;i++){
while((ps>>j)&1)j++;
b[i]=j++;
}
}return l;
}