题解 P5208 【[WC2019]I 君的商店】

BFqwq · 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;
}