CF835E The penguin's game

Codeforces

Luogu

交互题。

有一个序列,其中有恰好 $2$ 个数是 $y$ ,剩下的 $n-2$ 个数是 $x$ 。

你每次可以询问一个集合的异或和。

你需要用不超过 $19$ 次询问找到两个为 $y$ 的数的下标。

分析

神仙交互题?

为了方便,下面把为 $y$ 的数称为特殊数


首先我们可以通过一次询问得到某个集合内的特殊数的个数的奇偶性。

  • 如果询问的集合大小是偶数,且特殊数的个数为偶数,那么返回值为 $0$ 。
  • 如果询问的集合大小是偶数,且特殊数的个数为奇数,那么返回值为 $y$ 。
  • 如果询问的集合大小是奇数,且特殊数的个数为偶数,那么返回值为 $x$ 。
  • 如果询问的集合大小是奇数,且特殊数的个数为奇数,那么返回值为 $x\oplus y$ 。

因为 $0,x,y,x\oplus y$ 是互不相同的,所以很好判断奇偶性了。


我们从小到大枚举每个二进制位,然后把所有下标分成两组:这一位为 $1$ 的,这一位为 $0$ 的。

我们查询一下这一位为 $1$ 的下标的集合,如果特殊数的个数为奇数,那么两个特殊数的下标在该二进制位是不同的。

那么我们只需要至多 $10$ 次询问就可以得到两个特殊数的下标的异或值了,也就是说只要知道了一个就可以知道另一个。


然后我们把所有下标划分成两组,保证每组中各有一个特殊数。

那么只需要在其中一组中二分即可求出一个特殊数的下标。如果在小的那组中二分的话这一部分只需要至多 $9$ 次询问。

这样子就得到了一个特殊数的下标,再异或之前求出的那个东西就可以得到另一个特殊数的下标了。


具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int query(vector<int> a) {
    if (!a.size()) return 0;
    cout<<"? "<<a.size();
    for (re int i:a) cout<<" "<<i;
    cout<<endl; fflush(stdout);
    int res; cin>>res; return res;
}

int main() {
    int n,x,y,diff=0,lbit; cin>>n>>x>>y;
    for (re int i=0;i<=9;++i) {
        vector<int> a; a.clear();
        for (re int j=1;j<=n;++j)
            if (j&(1<<i)) a.push_back(j);
        int res=query(a);
        if (res==y||res==(x^y)) diff|=(1<<i),lbit=i;
    }
    vector<int> a,b; a.clear(),b.clear();
    for (re int i=1;i<=n;++i) {
        if (i&(1<<lbit)) a.push_back(i);
        else b.push_back(i);
    }
    if (a.size()>b.size()) swap(a,b);
    int L=0,R=a.size()-1;
    while (L<R) {
        int mid=(L+R)>>1;
        vector<int> c; c.clear();
        for (re int i=L;i<=mid;++i) c.push_back(a[i]);
        int res=query(c);
        if (res==y||res==(x^y)) R=mid;
        else L=mid+1;
    }
    int ans1=a[L],ans2=ans1^diff; if (ans1>ans2) swap(ans1,ans2);
    cout<<"! "<<ans1<<" "<<ans2<<endl; fflush(stdout);
    return 0;
}
最后修改:2019 年 11 月 01 日 07 : 40 PM

3 条评论

  1. Peter0701

    资瓷|´・ω・)ノ

  2. smy

    催更NOI2019 I君的探险

    1. M_sea
      @smy

      不会做,告辞

发表评论 取消回复