题解 [WC2019]I 君的商店

题目链接

有被这道题目人类智慧到，想了好久还是和正解没有挨边，最后还是迫不得已看了题解。 /kk

题目分析

以下记录我想这道题目的思考过程。

先看看可不可以找到一些特殊性质，可以发现可以通过 \(\mathcal O(2n)\) 的时间复杂度找到一个一定是 1 的位置，并且在知道 1 的奇偶性的前提下可以比较两个集合的严格大小关系。

然后观察所有子任务，可以看到子任务 3 特别奇怪，相当于是保证了所有 0 和所有 1 构成了两个连续段（暗示二分，并且由 \(M=100\) 也可以猜到复杂度大概是 \(\mathcal O(\log_2n)\) 级别的）， 1 的位置比较好找，并且题目中一开始还给定了 1 的数量的奇偶性，如果要二分的话需要保证返回的是严格小于或者严格大于，所以可以根据 1 的数量的奇偶性来将相邻两个数字捆绑在一起，这样在询问的时候询问要么就是 1+1 与 1 或者 0+0 与 1 的大小关系，返回的就是严格小于或者严格大于，时间复杂度是 \(\mathcal O(3\log_2n)\) 。

子任务 5 和 6 额外给出了 100 的复杂度，说明正解大概是先将数组进行一些处理让数组满足子任务 3 的限制（相当于是要排序），于是问题的关键转到排序上。

如何将数组排序？我一开始想到的是增量法，已经给 \(0\sim i-1\) 的所有元素排好序了，接下来考虑把 \(i\) 这个元素加入，然后想了很多方法都没有想到简单的判断 \(i\) 这个元素可以插入哪里的方法。最后在这里放弃了。

归并排序是后面想到的，不过这样的时间复杂度是 \(\mathcal O(2n\log_2n)\) 的。

这里是 \(\mathcal O(7n)\) 的做法。

先通过 \(\mathcal O(2n)\) 找到 1 ，然后对于两个数 \(x,y\) ，可以先比较 \(\operatorname{ans}[x]\) 与 \(\operatorname{ans}[y]\) 的关系，通过交换操作使得 \(\operatorname{ans}[x]\le \operatorname{ans}[y]\) ，然后比较 \(\operatorname{ans}[x]+\operatorname{ans}[y]\) 与 1 的关系，如果 \(\operatorname{ans}[x]+\operatorname{ans}[y]\le 1\) 可以得出 \(\operatorname{ans}[x]=0\) ，如果 \(\operatorname{ans}[x]+\operatorname{ans}[y]\ge 1\) 可以得出 \(\operatorname{ans}[y]=1\) ，所以可以通过 \(\mathcal O(5)\) 的时间复杂度确定 \(x,y\) 中的一个元素，确定完 \(n-2\) 个元素后最后一个元素通过给定的 1 的奇偶性确定，总的时间复杂度是 \(\mathcal O(7n)\) 的。

接下来是正解做法。

先考虑子任务 3 ，直接二分 \(\operatorname{mid}\) 通过 \(\operatorname{ans[mid]+ans[mid+1]}\)和 1 的大小关系来判断位置在左边还是在右边，最后仅仅不能确定找到的位置的那个地方是 0 还是 1 ，这个可以通过 1 的奇偶性确定是 0 还是 1 。

然后看子任务 6 ，可以猜出时间复杂度大概是 \(\mathcal O(5n)\) 。先令 \(x=0,z=1\) ，然后从 \(2\) 到 \(N-1\) 枚举 \(y\) ，先比较 \(\operatorname{ans}[x]\) 与 \(\operatorname{ans}[y]\) 的大小关系，然后通过交换 \(x,y\) 使得 \(\operatorname{ans}[x]\le \operatorname{ans}[y]\) ，再比较 \(\operatorname{ans}[x]+\operatorname{ans}[y]\) 与 \(\operatorname{ans}[z]\) 的关系，如果返回结果为 \(\operatorname{ans}[x]+\operatorname{ans}[y]\le \operatorname{ans}[z]\) 说明 \(\operatorname{ans}[x]=0\) ，确定后在把 \(y\) 当作新的 \(x\) ，否则的话说明返回结果为 \(\operatorname{ans}[x]+\operatorname{ans}[y]\ge \operatorname{ans}[z]\) ，可以得出 \(\operatorname{ans}[y]\ge \operatorname{ans}[z]\) ，将 \(z\) 放入一个数组 \(H[]\) 并且将 \(y\) 当作新的 \(z\) 。最后将 \(z\) 继续放入 \(H[]\) ，可以发现得到的 \(H[]\) 是单调递增的，此时无法确定的元素就只剩了 \(H[]\) 和 \(x\) ，用二分的方法可以确定 \(H[]\) 中的大部分元素，不妨设无法确定的元素为 \(H[\operatorname{pos}]\) ，可以通过比较 \(H[]\) 中的最大值和 \(x\) 得到值为 1 的元素，然后通过 \(\mathcal O(5)\) （见 \(\mathcal O(7n)\) 的做法）的时间复杂度确定 \(H[\operatorname{pos}]\) 和 \(x\) 中的一个元素，另一个用给定的 1 的奇偶性确定。总的时间复杂度就是 \(\mathcal O(5n+3\log_2n)\) 的。

参考代码

#include"shop.h"
int S[5],T[5],nS,nT;
int query0(int x,int y){
	nS=1;S[0]=x;nT=1;T[0]=y;
	return query(S,nS,T,nT);
}
int query1(int x,int y,int z){
	nS=2;S[0]=x,S[1]=y;nT=1;T[0]=z;
	return query(S,nS,T,nT);
}
const int maxn=100005;int spe[maxn];
void find_price(int task_id,int N,int K,int ans[]){
	if(N==1)return ans[0]=1,void();
	int x=0,z=1,cnt=0,tp=-1,az=0;
	if(task_id==3){
		if(query0(0,N-1)){
			tp=N-1;
			for(int i=0;i=0;--i)
				spe[cnt++]=i;
		}
		x=-1;z=spe[0];
	}
	else{
		for(int i=2;i>1;
		if(query1(spe[mid],spe[mid+1],tp))l=mid+1;
		else r=mid;
	}
	mid=l=r;
	for(int i=0;i