【题解】[LOJ #2985 / 洛谷 P5208]「WC2019」 I 君的商店【二分】

题意

有一 01 序列，已知其 1 的个数的奇偶性。你一次询问可以给出两个下标集合 (S,T)（同一集合内部元素不能重复），花费 (|S|+|T|)，若 (S) 对应位置的和大于 (T)，交互库返回 (0)；若小于，返回 (1)；若等于，返回 (0) 或 (1)。用至多 (5n+3log n+O(1)) 的代价确定序列。

题解

操作 1：任选 (a,x,y)，确定一些信息：

询问 ({x},{y})，假设 (xleq y)；
询问 ({x,y},{a})：
- ({x,y}leq{a})：(x=0)；
- ({x,y}geq{a})：(ygeq a)，依靠这些信息得到一条单调不减的链；

这样会剩下一个数既没有确定是 (0)，又不在链上。(5n+O(1)) 的代价。

操作 2：已知一条长为 (m) 的单调不减的链，二分确定其 (m-1) 个值：

二分第一次出现 ({c_i,c_{i+1}}geq 1) 的位置；
有可能 (c_i=0,c_{i+1}=1) 或 (c_i=1,c_{i+1}=1)；在前面的数都为 (0)，后面的数都为 (1)，(c_i) 不确定。

这样会只剩两个位置不确定。(3log n+O(1)) 的代价。

操作 3：已知 (xoplus y)，有一个 (1)，(O(1)) 得到 (x,y)：

若 (xoplus y=0)，询问 ({x,y},{1})；
若 (xoplus y=1)，询问 ({x},{y})。

于是问题解决。

总代价 (5n+3log n+O(1))。

#include<bits/stdc++.h>
#include "shop.h"
using namespace std;
namespace Wallbreaker5th{

stack<int>unknown;
vector<int>v;
bool query(vector<int>s,vector<int>t){
    return ::query(s.data(),s.size(),t.data(),t.size());
}
vector<int>getchain(int n){
    vector<int>c;
    int b=unknown.top();
    c.push_back(b);
    unknown.pop();
    while(unknown.size()>=2){
        int x=unknown.top();unknown.pop();
        int y=unknown.top();unknown.pop();
        int a=c.back();
        if(query({y},{x}))swap(x,y);
        if(query({x,y},{a})){
            v[x]=0;
            unknown.push(y);
        }else{
            c.push_back(y);
            unknown.push(x);
        }
    }
    return c;
}
void bs(int n,int k,vector<int>c){
    int m=c.size();
    int one=c[m-1];
    int l=0,r=m-2,ans=m-1;
    while(l<=r){
        int mid=l+r>>1;
        if(query({one},{c[mid],c[mid+1]}))ans=mid,r=mid-1;
        else l=mid+1;
    }
    for(int i=0;i<ans;i++)v[c[i]]=0;
    for(int i=ans+1;i<m;i++)v[c[i]]=1;
    for(int i=0;i<n;i++)if(~v[i])k^=v[i];
    if(unknown.size()){
        int t=unknown.top(),r=c[ans];
        if(k)
            v[t]=!(v[r]=query({t},{r}));
        else
            v[t]=v[r]=query({one},{t,r});
    }else v[c[ans]]=k;
}

}

void find_price(int task_id, int n, int k, int ans[]){
    using namespace Wallbreaker5th;
    if(n==1){
        ans[0]=1;
        return;
    }
    if(n==2){
        if(!k)ans[0]=ans[1]=1;
        else ans[1-query({0},{1})]=1;
        return;
    }
    v=vector<int>(n,-1);
    while(unknown.size())unknown.pop();
    if(task_id==3){
        vector<int>c;
        for(int i=0;i<n;i++)c.push_back(i);
        if(query({n-1},{0}))reverse(c.begin(),c.end());
        bs(n,k,c);
        for(int i=0;i<n;i++)ans[i]=v[i];
        return;
    }
    for(int i=0;i<n;i++)unknown.push(i),ans[i]=0;
    vector<int>c=getchain(n);
    bs(n,k,c);
    for(int i=0;i<n;i++)ans[i]=v[i];
}

【题解】[LOJ #2985 / 洛谷 P5208]「WC2019」 I 君的商店【二分】

题意

题解

相关推荐