首先有个很显然的 \(\mathcal O(nk^2)\) 的做法，即二分答案，然后 trie 树上判断。
对于 trie 树上一颗子树内的判定，考虑当前二分的 \(\text{mid}\) 这一位是 \(1\) 还是 \(0\) 以及 \(x\) 这一位填什么。
-
对于 \(1\) 的情况，如果填 \(0\)，那么右儿子仍然合法，左儿子中的数必须要放到集合 \(S\) 中。预处理出一个子树内 \(a\) 的最小值以及 \(b\) 的和，递归到右儿子继续求解。填 \(1\) 的情况类似。
-
对于 \(0\) 的情况，如果填 \(0\)，那么右儿子已经满足异或值 \(>\text{mid}\)，递归到左儿子继续求解。填 \(1\) 的情况类似。
发现这种做法每个点只会被遍历一次，可以获得云斗 \(92\) & CCF \(72\) 分的好成绩。
优化的部分就简单了。
考虑怎么优化。发现可以把二分去掉，在子树内贪心考虑如果答案的当前位填 \(1\)，剩下的位全填 \(0\) 是否有解，如果有解就填 \(1\)，否则填 \(0\)。
发现判定可以用之前预处理出来的东西 \(\mathcal O(1)\) 做，每个点只会被遍历一次。所以时间复杂度 \(\mathcal O(nk)\)，可以通过此题。
参考代码：
#include<bits/stdc++.h>
#define mxn 100003
#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 drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
inline __int128 read1(){
__int128 x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
inline void print(__int128 a){
if(a>9)print(a/10);
putchar(a%10+'0');
}
int c,T,n,m,k,b,sm,tot,f[mxn*120],t[mxn*120][2];
__int128 a,mn,pw[123],A[mxn],s[mxn*120];
void ins(){
int p=0;
drep(i,k-1,0){
if(!t[p][(a>>i)&1])t[p][(a>>i)&1]=++tot,f[tot]=0,s[tot]=a;
p=t[p][(a>>i)&1],f[p]=min(f[p]+b,m+1),s[p]=min(s[p],a);
}
}
__int128 solve(__int128 mid,int x,int d,__int128 now,__int128 mn,int sum,bool fl){
if(sum>m)return 0;
if(d<0)return mid;
__int128 ans=0;
if(pw[d]-1+(fl&&t[x][1]?min(mn,s[t[x][1]]):mn)+now>=mid){
ans=max(ans,solve(mid+pw[d],fl?t[x][0]:0,d-1,now+pw[d],fl&&t[x][1]?min(mn,s[t[x][1]]):mn,min(sum+(fl?f[t[x][1]]:0),m+1),fl&&t[x][0]));
}
if(pw[d]-1+(fl&&t[x][0]?min(mn,s[t[x][0]]):mn)+now>=mid+pw[d]){
ans=max(ans,solve(mid+pw[d],fl?t[x][1]:0,d-1,now,fl&&t[x][0]?min(mn,s[t[x][0]]):mn,min(sum+(fl?f[t[x][0]]:0),m+1),fl&&t[x][1]));
}
if(ans)return ans;
if(pw[d]-1+mn+now>=mid){
ans=max(ans,solve(mid,fl?t[x][0]:0,d-1,now,mn,sum,fl&&t[x][0]));
}
if(pw[d+1]-1+mn+now>=mid){
ans=max(ans,solve(mid,fl?t[x][1]:0,d-1,now+pw[d],mn,sum,fl&&t[x][1]));
}
return ans;
}
signed main(){
c=read(),T=read();
pw[0]=1;
rep(i,1,120)pw[i]=pw[i-1]*2;
while(T--){
n=read(),m=read(),k=read();
rep(i,0,tot)t[i][0]=t[i][1]=0;
tot=0;
sm=0,mn=pw[k];
rep(i,1,n)A[i]=read1();
rep(i,1,n){
b=read(),a=A[i];
ins();
sm=min(sm+b,m+1),mn=min(mn,a);
}
if(sm<=m){
print(mn+pw[k]-1);
puts("");
continue;
}
print(solve(0,0,k-1,0,pw[k],0,1));
puts("");
}
return 0;
}