题解：CF2156D Find the Last Number

· · 题解

喜提 8 个 WA！

我们很显然有一个 n (\lfloor \log n \rfloor+1) 次查询的做法，设 f_k(x) 表示 x 的第 k 位的值，显然我们只需要求 p_n 的所有第 k(0 \le k \le \lfloor \log n \rfloor) 就能知道 p_n 的值，求出 p_n 第 k 位的方法很简单，根据简单原理得出：

f_k(p_n)=\sum_{i = 1}^n f_k(i)-\sum_{i = 1}^{n-1} f_k(p_i)

然后仔细观察，发现可以用一种神奇的方法给等式右边同时减去那些 1 \sim i-1 位有和 p_n 不相同的的数，你就会得到这个：

f_k(p_n) = \sum_{i \in S_{k-1}} f_k(i)-\sum_{i \in P_{k-1}} f_k(p_i)

这里 S_x 指的是 1 \sim x-1 都和 p_n 相同的数所构成的集合，P_x 指的是 1 \sim x-1 都和 p_n 相同的 p_i(1 \le i \le n-1) 的下标 i 所构成的集合。

然后你就会发现，这个东西的询问次数其实是：

\sum_{k = 0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n-1}{2^k} \right\rceil = (n-1)+\sum_{k = 1}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n-1}{2^k} \right\rceil \le (n-1)+\sum_{k = 1}^{\lfloor \log_2 n \rfloor} \frac{n-1}{2^k}+1 \le (n-1)+(n-1)\sum_{k = 1}^{\lfloor \log_2 n \rfloor} \frac{1}{2^k}+\sum_{k = 1}^{\lfloor \log_2 n \rfloor}1 \le (n-1)+(n-1)(1-\frac{1}{2^{\lfloor \log_2 n \rfloor}})+\lfloor \log_2 n \rfloor \le (n-1)+(n-1)(1-\frac{1}{2^{\lfloor \log_2 n \rfloor}})+\lfloor \log_2 n \rfloor \le (n-1)+(n-1)(1-\frac{1}{n})+\lfloor \log_2 n \rfloor(\operatorname{beacause} 2^{\lfloor \log_2 n \rfloor} \le n) \le (n-1)+(n-1)-\frac{n-1}{n}+\lfloor \log_2 n \rfloor \le 2n-2-\frac{n-1}{n}+\lfloor \log_2 n \rfloor \le 2n-2-(1-\frac{1}{n})+\lfloor \log_2 n \rfloor \le 2n-3+\frac{1}{n}+\lfloor \log_2 n \rfloor

虽然这玩意看似在 n 比较极限的时候会超出 2n 一点点，但这只是很粗略的上界，实际明显低于这个。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
const int mx = 2e4;
int a[N];
int b[N];
int bx[N];
int by[N];
int P[N];
int hou[N];
int dian[N];
int NP[N][2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 1;i<=mx;++i)
    {
        int s = (i&1);
        b[i] = b[i-1]+s;
        bx[i] = bx[i-1];
        by[i] = by[i-1];
        if(s)
        {
            bx[i]+=((i&2)>0);
        }
        else
        {   
            by[i]+=((i&2)>0);
        }
    }
    int _;
    cin >> _;
    while(_--)
    {
        int n;
        cin >> n;
        int cnt = 0,numx = 0;
        for(int i = 1;i<n;++i)
        {
            cout << "? " << i << " 1" << endl;
            cin >> dian[i];
            cnt+=dian[i];
        }
        int w = b[n]-cnt;
        hou[0] = w;
        for(int i = 1;i<n;++i)
        {
            if(dian[i] == w)
            {
                P[++numx] = i;
            }
        }
        int ans = w;
        int s = 31-__builtin_clz(n);
        int num1 = 0,num2 = (w == 0?by[n]:bx[n]);
        int nx = 0,ny = 0;
        for(int i = 1;i<=numx;++i)
        {
            cout << "? " << P[i] << " 2" << endl;
            int x;
            cin >> x;
            num1+=(x>0);
            if(!x)
            {
                NP[++nx][0] = P[i];
            }
            else
            {
                NP[++ny][1] = P[i];
            }
        }
        for(int i = 1;i<=s;++i)
        {
            ans+=(1<<i)*(num2-num1);
            if(i == s)
            {
                continue;
            }
            w = num2-num1;
            hou[i] = w;
            for(int j = 1;j<=(w?ny:nx);++j)
            {
                P[j] = NP[j][w];
            }
            numx = (w?ny:nx);
            nx = 0,ny = 0;
            num1 = 0;
            for(int j = 1;j<=numx;++j)
            {
                cout << "? " << P[j] << ' ' << (1<<i+1) << endl;
                int x;
                cin >> x;
                num1+=(x>0);
                if(!x)
                {
                    NP[++nx][0] = P[j];
                }
                else
                {
                    NP[++ny][1] = P[j];
                }
            }
            num2 = 0;
            for(int j = 1;j<=n;++j)
            {
                int dui = 1;
                for(int k = 0;k<=i;++k)
                {
                    int flag = ((j&(1<<k))>0);
                    if(flag!=hou[k])
                    {
                        dui = 0;
                        break;
                    }
                }
                if(dui)
                {
                    num2+=((j&(1<<i+1))>0);
                }
            }
        }
        cout << "! " << ans << endl;
    }
    return 0;
}