专栏文章

JOISC2019 l 鉱物 (Minerals)

ffangzichang
AT_joisc2019_l题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipl6ilb
此快照首次捕获于
2025/12/03 13:48
3 个月前
此快照最后确认于
2025/12/03 13:48
3 个月前
查看原文
最后的优化稍微不太一样。

题意

2n2n 个带编号带颜色的球，总共 nn 种颜色，每种颜色恰好有两个球。
交互库有一个球的集合 SS，一开始为空。每次交互操作时，选手程序向交互库给出一个编号 xx，交互库改变 xx 这个球在 SS 中的状态：如果原本不存在就放进去，不然就拿出来。然后交互库返回 SS 中的颜色数量。
要求在 10610^6 次操作内求出每一对颜色相同的球的编号。
n≤43000n\le 43000。

解法

一开始容易想到分治。这部分可以参考 DaiRuiChen007 大神的题解。
考虑交互能做什么：如果颜色总数与上一次相比没有变化，说明在操作前和操作后的 SS 中，都存在一个球与询问的 xx 颜色一样；不然就说明这样的球不存在。
这样容易用 2n2n 次操作求出两个集合，满足两个集合里面 nn 种颜色的球恰好各出现一次。
接下来分治，维护两个集合 L,RL,R 满足两个集合大小一样、颜色种类一样，这些颜色的两个球都恰好在 LL 和 RR 中各有一个。过程中保证任意一次分治开始时，LL 里所有的球全都在 SS 中或全都不在 SS 中，并且知道是全都在还是全都不在。
每次把 LL 分成两半 L0L_0 和 L1L_1，对其中某一个集合整个交互一遍，使得 L0L_0 全都在 SS 中而 L1L_1 全都不在，当然反过来也行。
然后把 RR 中每个球拿去交互，返回值拿来判断这个球对应的同色球是在 L0L_0 中还是在 L1L_1 中，把 RR 分成 R0R_0 和 R1R_1。
比如说 L0L_0 全都在 SS 中而 L1L_1 全都不在，则询问一个球 xx 时，如果颜色总数发生变化（不论是增加还是减少都是如此，你乐意的话可以自行仔细分类讨论一下），都说明 xx 对应的同色球不在 L0L_0 中，如果在的话颜色数不会变化。
L0L_0 全都不在 SS 中而 L1L_1 全都在的情况是完全对称的，比较方便的想法是直接交换两个集合。
然后往 L0,R0L_0,R_0 和 L1,R1L_1,R_1 递归分治，容易发现仍旧满足一开始“LL 里所有的球全都在 SS 中或全都不在 SS 中，并且知道是全都在还是全都不在”的要求。
并且很方便的是往这两边递归的过程中操作的球的颜色不同（任意一侧都完全由同色球对组成），所以操作互不干扰，返回时不需要撤销影响。
每次递归交互了半个 LL 和一整个 RR，这样的复杂度是 2n+32nlog⁡2n2n+\frac{3}{2}n\log_2 n，过不去。

优化

考察这个复杂度的形式，不妨设我每次都把整个 L0L_0 交互一遍，考虑不把 L0L_0 设成 LL 的一半，而是稍小一些，复杂度或许可能更优。
具体地，设 L0L_0 的大小为 kk 倍 LL 的大小（当然这个可以记为 nn），则操作次数大概为 T(n)=(1+k)n+T(kn)+T((1−k)n)T(n)=(1+k)n+T(kn)+T((1-k)n)。
DaiRuiChen007 大神说可以动态规划求这个最优大小。
毛估估看一下发现 k=12k=\frac{1}{2} 并没能取到最值。
据称求导或者三分一下，大概取到 0.360.36 最优。
不过实际上打个表就行了，因为式子其实是 T(n)=⌈kn⌉+n+T(⌈kn⌉)+T(n−⌈kn⌉)T(n)=\lceil kn\rceil +n+T(\lceil kn\rceil)+T(n-\lceil kn\rceil)，一看一堆取整就知道精度高了没啥用。比如以 10−410^{-4} 为步长枚举可能的 kk，发现 k=13k=\frac{1}{3} 就足够优秀了。
CPP
int n=43000;
int f[N];
int dfs(int n,db k){
	if(n<=1)return 0;
	if(f[n])return f[n];
	return f[n]=n+ceil(n*k)+dfs(ceil(n*k),k)+dfs(n-ceil(n*k),k);
}
signed main(){
	static const db eps=1e-4;
	pair<int,db>res={inf,inf};
	for(db k=eps;k<0.5;k+=eps){
		int w=dfs(n,k);
		res=min(res,pair<int,db>(w,k));
		fill(f+1,f+n+1,0);
	}
	cout<<res.x<<"  "<<res.y<<endl;
	return 0;
}
所以让这个分治过程右偏，每次取 ⌈0.36n⌉\lceil 0.36n\rceil 作为 L0L_0 的大小，发现还是过不去，需要 86000+96279986000+962799 次交互。
考虑扫描 RR 过程中，如果 R0R_0 与 R1R_1 之一已经填到预期的大小了，就可以直接把剩下部分塞到另一个集合里，不需要额外消耗交互次数。如果不放心，还可以随机打乱 LL 和 RR。
估计一下就会觉得这个常数比较小，实际上跑出来最多的询问次数大概 9.94×1059.94\times 10^5 左右。
CPP
mt19937 rnd(random_device{}());
using bsi=basic_string<int>;
bool q(int x){
	int w=Query(x);
	static int lst=0;
	return lst==w?0:(lst=w,1);
}
void dfs(bsi&L,bsi&R,bool t){
//	for(int x:L)cerr<<x<<" ";
//	cerr<<" | ";
//	for(int y:R)cerr<<y<<" ";
//	cerr<<endl;
	assert(L.size()==R.size());
	int n=L.size(),n0=ceil(n*0.36),n1=n-n0;
	if(L.size()==1)
		return Answer(L[0],R[0]);
	shuffle(all(L),rnd),shuffle(all(R),rnd);
	bsi L0=L.substr(0,n0),L1=L.substr(n0,n),R0,R1;
	for(int x:L0)q(x);
	if(!t){
		for(int y:R){
			if((int)R0.size()!=n0&&(int)R1.size()!=n1)
				(q(y)?R1:R0)+=y;
			else ((int)R0.size()!=n0?R0:R1)+=y;
		}
		dfs(L0,R0,1),dfs(L1,R1,0);
	}
	else{
		for(int y:R){
			if((int)R0.size()!=n0&&(int)R1.size()!=n1)
				(q(y)?R0:R1)+=y;
			else ((int)R0.size()!=n0?R0:R1)+=y;
		}
		dfs(L0,R0,0),dfs(L1,R1,1);
	}
}
void Solve(int n){
	bsi L,R;
	for(int i=1;i<=n*2;i++)
		(q(i)?L:R)+=i;
	dfs(L,R,1);
}
嘛，写动态规划也没有麻烦很多。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...