Codeforces Round #803 (Div. 2) (A-D) D：二分+交互题

写在前面

比赛链接：Dashboard - Codeforces Round #803 (Div. 2) - Codeforces
这场是手速场，提前回寝室睡觉，然后起床打比赛状态贼好，一开始本来打算放弃D的，但是突然有了灵感！
小号加了121分，准备先把小号打上蓝，然后不分大小号了，每次拿分最低的打。

A. XOR Mixup（位运算）

题意

给你一个长度为n的数组，告诉你其中有一个数字是由其他三个异或构成的，问你是哪一个被其他构成。例如：

4
4 3 2 5

这样来看4 xor 2 xor 5 = 3，所以输出3

思路

利用异或性质a ^ b = c可以推出a ^ b ^ c = c ^ c = 0，原因就是两边同时异或一个数不变，并且a ^ a = 0。
这样来看其实数组里面每一个数字都可以，前提是满足条件，题目保证都满足，所以我选择输出a[n]

代码

inline void Case_Test()
{
    x = 0;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>k;
    cout<<k<<endl;
}

B. Rising Sand（思维）

题意

给你一个n,k以及一个长度为n的数组，你可以选择一个连续k个区间全部+1，问最多有多少堆（堆的定义是 $1\leq i\leq n$ 满足 $a_i>a_{i-1}+a_{i+1}$ ）

思路

这样来看，我需要满足拉大堆与两侧的距离，我想让更多的 $i$ 的 $a_i-a_{i-1}-a_{i+1}>0$ 也就是拉大 $a_i-a_{i-1}-a_{i+1}$ ，所以——当 $2\leq k$ 的时候，是无论如何都不能使得这个值增加的，因为你总是与两侧有关系。

所以如果是 $2\leq k$ 的时候只需要输出读入的时候有多少个那就是多少个；否则就可以构造堆为 $2,4,6,...,$

代码

inline void Case_Test()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    ans = 0;
    for (int i=2;i<n;i++)
        if (a[i]>a[i-1]+a[i+1])
            ans++;
    if (k>=2) cout<<ans<<endl;
    else cout<<(n-1)/2<<endl;
}

C. 3SUM Closure（思维） 1300

题意

定义一个SUM-closed，如果这个数列里面存在三个不同的数字，加起来的数也在数列中，那么这个就是"YES"

思路

假设有3个正数（负数同理）a、b、c，a+b+c肯定会大于max(a,b,c)，如果也在数列中，那么就一直这么递增下去，可以看出，是必定不会满足的。所以"3SUM-closed"最多只能有两个正数，和两个负数。
如果有0的话，就加入一个vector中，这个vector还有其他不等于0的，所以这个一定不大，因为0最多1个，正数负数最多加起来四个。
然后对这些进行for循环暴力查找即可

代码

map<int,bool> mp;
inline void Case_Test()
{
    cin>>n;
    mp.clear();
    vector<int> b,z,f;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]] = true;
        if (a[i]!=0) b.push_back(a[i]);
        if (a[i]<0) f.push_back(a[i]);
        if (a[i]>0) z.push_back(a[i]);
    }
    if (f.size()>=3||z.size()>=3)
    {
        cout<<"NO"<<endl;
        return;
    }
    if (mp.find(0)!=mp.end())
        b.push_back(0);
    cnt = b.size();
    for (int i=0;i<cnt;i++)
        for (int j=i+1;j<cnt;j++)
            for (int k=j+1;k<cnt;k++)
                if (mp.find(b[i]+b[j]+b[k])==mp.end())
                {
                    cout<<"NO"<<endl;
                    return;
                }

    cout<<"YES"<<endl;
}

D. Fixed Point Guessing（交互题，二分） 1600

题意

给你一个长度n（一开始只知道n），本来是一个长度为n（ $1\leq n \leq 10^4$ ）的数组，数组是保证是奇数，里面只能两两交换，并且每个数只能交换一次，这样就只有一个数不能交换。题目用交换后的数组，让你不超过 $15$ 次询问，猜出这个数字是哪个。

你可以猜? x y，题目会告诉你区间 $[x,y]$ 中的从小到大排序是多少。例如5,4,3,2,1，你询问? 1 3，这个时候就会告诉你3 4 5。
最后需要返回! x，告诉程序x是不变的。

思路

我觉得这种题主要是看数据范围，这个15告诉你，肯定就是log2级别的了，所以大概率需要二分或者倍增的区间询问。这个题准备放弃的，但是突然发现那个答案那个数所在的区间有一个特征：

对于一个区间 $[x,y]$ ，查询里面的数字，如果发现应该在 $[x,y]$ 其中的是奇数个，那么能确定不变的就是在这个区间里，这个聊天记录是赛中的，因为就是“成双成对”的概念。

所以就可以一直这么二分下去，我一发过了，真爽，我写的dfs，不过20行。

代码

void dfs(int l,int r)
{
    if (l==r) {cout<<"! "<<l<<endl;return;}
    int mid = (l+r)>>1;
    int m = mid-l+1;
    cout<<"? "<<l<<" "<<mid<<endl;
    cnt = 0;
    for (int i=l;i<=mid;i++)
    {
        cin>>a[i];
        if (a[i]>=l&&a[i]<=mid) cnt++;
    }
    if (cnt%2==1) dfs(l,mid);
    else dfs(mid+1,r);
}
inline void Case_Test()
{
    cin>>n;
    dfs(1,n);
}