自动搬运

查看原文

来自洛谷，原作者为

	BFqwq 青く广がった あの空のように、昙りなく笑えたら あなたに会いたい。

搬运于2025-08-24 22:08:16，当前版本为作者最后更新于2020-11-24 18:56:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P5208 【[WC2019]I 君的商店】

第一次过交互题，可能也是我退役之前过的唯一一道交互题了。

为了方便叙述，令物品 $i$ 的价格为 $v_i$。

sub 1,2,4,5

首先，我们可以先得出两个显然的结论：

1. 如果 $v_b\le v_c$ 且 $v_a\ge v_b+v_c$，则我们可以直接推出 $v_b=0$，对于任意 $a,b,c$ 成立（否则 $v_b=v_c=1,v_b+v_c=2>1\ge v_a$，矛盾）。

2. 如果 $v_b\le v_c$ 且 $v_a\le v_b+v_c$，则我们可以直接推出 $v_a\le v_c$，对于任意 $a,b,c$ 成立（否则 $v_a=1,v_b=v_c=0,v_b+v_c=0<1=v_a$，矛盾）。特别的，如果已知 $v_a=1$，则可以据此确定 $v_c=1$。

然后我们发现，如果我们能够确定一个数 $v_x=1$，那么接下来我们每消耗 $5$ 点体力就可以确定一个数的值。

而确定一个 $1$ 这种事情显然很简单。我们可以直接进行 $n-1$ 次比较，每次根据返回的数保留其中较大的那一个，这样我们就可以比出一个最大值（设为 $t$）。

而由于这个物品的价格大于等于所有其他物品的价格，且题目保证一定存在 $1$，所以我们可以确定 $v_t$ 一定为 $1$。

然后我们再根据上述的两个结论，每次任取两个数 $a,b$，先比较出其大小（不妨设 $v_a\le v_b$），然后再加起来和 $v_t$ 比较。

如果 $v_t\ge v_a+v_b$，则根据结论 $1$ 直接推出 $v_a=0$，否则根据结论 $2$ 直接推出 $v_b=1$。

最后我们会发现只剩一个数没法比较。但由于题目给定了奇偶性，所以我们可以根据目前的 $1$ 的个数和奇偶性判断出最后一个数的 $v$ 值。

在找 $t$ 的阶段我们消耗的体力为 $2n$，在确定所有数的阶段我们消耗的体力为 $5n$，共 $7n$，满足条件。

但我们发现如果使用这种做法，想要再减少 $2n$ 的消耗是非常困难的。不过没有关系，我们可以先解决 sub3 的问题。

sub3

在这个子任务中，我们看到了一个很好的性质：价值是单调递增（递减）的。我们可以很显然的想到使用二分。

首先，我们可以通过判断 $v_0$ 和 $v_{n-1}$ 的相对大小来确定价值单调递增还是单调递减。不妨设序列单调递减。

我们依然考虑采用前面的方法，将两个数和 $1$ 作比较。

由于序列一定存在一个 $1$，所以 $v_0=1$。

我们设 $mid=(l+r)\div 2$，显然 $v_{mid}\ge d_{mid+1}$。我们将两者之和与 $v_0$ 比较，那么我么一定可以得到 $v_{mid}=1$ 或 $v_{mid+1}=0$。

二分处那一个 $0$ 和 $1$ 的边界。注意无论如何，中间必然有一个数时我们无法确定的，所以只剩一个数的时候我们要用奇偶性去判定。

应该说思路非常简单，但代码实现却有一点难度，稍有不慎就会写错。

我的写法是设 $l$ 为我们目前所能确定的最后一个 $1$，$r+2$ 为我们目前所能确定的最后一个 $0$。

if(n<=2||sub==3){
	for(int i=0;i<n;i++){
		o[i]=i;
	}
	if(leq(0,n-1)){
		reverse(o,o+n);
	}
	int l=0,r=n-1;
	while(l<r){
		int mid=l+r+1>>1;
		if(mid<n-1&&leq(o[0],o[mid],o[mid+1])){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	ans[o[l+1]]=(l+1^k)&1;
	for(int i=0;i<=l;i++){
			ans[o[i]]=1;
	}
	return;
}

sub6

受到 sub3 的做法的启发，我们可以考虑构造一个单调递增的序列，然后用这个在这个序列上进行二分。恰好数据范围多给了 $100$ 点体力，足够我们进行二分。

每次，我们选取 $a,b,c$ 三个数进行比较，其中 $a$ 是单个的数，要和 $b,c$两者的价值之和比较。

每次先比较 $b,c$ 的大小。不妨设 $v_b\le v_c$。

如果 $v_a\ge v_b+v_c$，则直接推出 $v_b=0$，换一个 $v_b$ 继续比。

否则我们可以推出 $v_a\le v_c$。接着，我们把 $a$ 放到一个数组中，然后用 $c$ 来作新的 $a$，换一个 $c$ 继续比。

举个例子，$v_2\le v_3$，$v_1\le v_2+v_3$，则我们得到 $v_1\le v_3$。我们将 $1$ 放到数新组中，这时数组中只有一个元素 $1$，然后 $a=3$，即 $3$ 成为单个的数。

然后 $v_2\le v_4$，$v_3\ge v_2+v_4$，则 $v_2=0$。

然后 $v_4\le v_5$，$v_3\le v_4+v_5$，则 $v_3\le v_5$，把 $v_3$ 放入数组中，然后 $a=5$，即 $5$ 成为单个的数。

接着我们发现，数组中的上一个数正好是 $1$，这时被 $3$ 比下去的数。

然后接下来如果有数进来，那一定是 $5$，然后 $3$ 刚好又是被 $5$ 比下去的。

于是我们就发现这个数组是按照价值单调递增的。

最后我们会剩下两个数，其中一个是 $a$。

由于此时的 $a$ 已经大于等于数组中的所有数，而除了剩下的两个数之外的数要么在数组中，要么是 $0$，所以显然可以知道，所有数中的最大者一定在剩下的两个数中。

然后我们比一次，就能比出一个较大者（设为 $t$），$v_t=1$。另一个数设为 $s$。

然后我们仿照 sub3 二分，直到数组中只剩一个数（设为 $q$）未被确定。

然后我们就只剩 $s,q$ 两者未被确定了。我们还是按比大小，然后价值求和与 $v_t$ 比的方法确定其中的一个，然后依据奇偶性确定另一个即可。

好像思路还挺简单的

贴个代码，调了半天的（

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+6;
int tmp[2][2];
int o[maxn],cnt;
int query(int *S,int nS,int *T,int nT);
bool leq(int a,int b){
	tmp[0][0]=a;tmp[1][0]=b;
	return query(tmp[0],1,tmp[1],1);
}//return a<b
bool leq(int a,int b,int c){
	tmp[0][0]=a;tmp[1][0]=b;tmp[1][1]=c;
	return query(tmp[0],1,tmp[1],2);
}//return a<b+c
void find_price(int sub,int n,int k,int ans[]){
	cnt=0;
	if(n<=2||sub==3){
		for(int i=0;i<n;i++){
			o[i]=i;
		}
		if(leq(0,n-1)){
			reverse(o,o+n);
		}
		int l=0,r=n-1;
		while(l<r){
			int mid=l+r+1>>1;
			if(mid<n-1&&leq(o[0],o[mid],o[mid+1])){
				l=mid;
			}
			else{
				r=mid-1;
			}
		}
		ans[o[l+1]]=(l+1^k)&1;
		for(int i=0;i<=l;i++){
			ans[o[i]]=1;
		}
		return;
	}
	int a,b,c;
	a=0,c=1;
	for(int i=2;i<n;i++){
		b=i;
		if(leq(c,b)){
			swap(b,c);
		}
		if(leq(a,b,c)){
			o[cnt++]=a;
			a=c;c=b;
		}
		else{
			ans[b]=0;
		}
	}
	if(leq(c,a)){
		swap(a,c);
	}
	ans[c]=1;
	if(!cnt){
		ans[a]=k^1;
		return;
	}
	o[cnt++]=c;
	int l=0,r=cnt-1;
	reverse(o,o+cnt);
	while(l<r){
		int mid=l+r+1>>1;
		if(mid<cnt-1&&leq(o[0],o[mid],o[mid+1])){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	for(int i=0;i<=l;i++){
		ans[o[i]]=1;
	}//o[l+1] 和 a 未知
	c=o[l+1];
	if(leq(c,a)){
		swap(a,c);
	}
	if(leq(o[0],c,a)){
		ans[c]=1;
		l++;
	}
	else{
		ans[a]=0;
		a=c;
	}
	ans[a]=(l+1^k)&1;
	return;
}