专栏文章

题解：CF2156D Find the Last Number

llinjinkun
CF2156D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8z8aq
此快照首次捕获于
2025/12/01 22:31
3 个月前
此快照最后确认于
2025/12/01 22:31
3 个月前
查看原文
喜提 88 个 WA！
我们很显然有一个 n(⌊log⁡n⌋+1)n (\lfloor \log n \rfloor+1) 次查询的做法，设 fk(x)f_k(x) 表示 xx 的第 kk 位的值，显然我们只需要求 pnp_n 的所有第 k(0≤k≤⌊log⁡n⌋)k(0 \le k \le \lfloor \log n \rfloor) 就能知道 pnp_n 的值，求出 pnp_n 第 kk 位的方法很简单，根据简单原理得出：
fk(pn)=∑i=1nfk(i)−∑i=1n−1fk(pi)f_k(p_n)=\sum_{i = 1}^n f_k(i)-\sum_{i = 1}^{n-1} f_k(p_i)
然后仔细观察，发现可以用一种神奇的方法给等式右边同时减去那些 1∼i−11 \sim i-1 位有和 pnp_n 不相同的的数，你就会得到这个：
fk(pn)=∑i∈Sk−1fk(i)−∑i∈Pk−1fk(pi)f_k(p_n) = \sum_{i \in S_{k-1}} f_k(i)-\sum_{i \in P_{k-1}} f_k(p_i)
这里 SxS_x 指的是 1∼x−11 \sim x-1 都和 pnp_n 相同的数所构成的集合，PxP_x 指的是 1∼x−11 \sim x-1 都和 pnp_n 相同的 pi(1≤i≤n−1)p_i(1 \le i \le n-1) 的下标 ii 所构成的集合。
然后你就会发现，这个东西的询问次数其实是：
∑k=0⌊log⁡2n⌋⌈n−12k⌉\sum_{k = 0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n-1}{2^k} \right\rceil =(n−1)+∑k=1⌊log⁡2n⌋⌈n−12k⌉= (n-1)+\sum_{k = 1}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n-1}{2^k} \right\rceil ≤(n−1)+∑k=1⌊log⁡2n⌋n−12k+1\le (n-1)+\sum_{k = 1}^{\lfloor \log_2 n \rfloor} \frac{n-1}{2^k}+1 ≤(n−1)+(n−1)∑k=1⌊log⁡2n⌋12k+∑k=1⌊log⁡2n⌋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 ≤(n−1)+(n−1)(1−12⌊log⁡2n⌋)+⌊log⁡2n⌋\le (n-1)+(n-1)(1-\frac{1}{2^{\lfloor \log_2 n \rfloor}})+\lfloor \log_2 n \rfloor ≤(n−1)+(n−1)(1−12⌊log⁡2n⌋)+⌊log⁡2n⌋\le (n-1)+(n-1)(1-\frac{1}{2^{\lfloor \log_2 n \rfloor}})+\lfloor \log_2 n \rfloor ≤(n−1)+(n−1)(1−1n)+⌊log⁡2n⌋(beacause⁡2⌊log⁡2n⌋≤n)\le (n-1)+(n-1)(1-\frac{1}{n})+\lfloor \log_2 n \rfloor(\operatorname{beacause} 2^{\lfloor \log_2 n \rfloor} \le n) ≤(n−1)+(n−1)−n−1n+⌊log⁡2n⌋\le (n-1)+(n-1)-\frac{n-1}{n}+\lfloor \log_2 n \rfloor ≤2n−2−n−1n+⌊log⁡2n⌋\le 2n-2-\frac{n-1}{n}+\lfloor \log_2 n \rfloor ≤2n−2−(1−1n)+⌊log⁡2n⌋\le 2n-2-(1-\frac{1}{n})+\lfloor \log_2 n \rfloor ≤2n−3+1n+⌊log⁡2n⌋\le 2n-3+\frac{1}{n}+\lfloor \log_2 n \rfloor
虽然这玩意看似在 nn 比较极限的时候会超出 2n2n 一点点，但这只是很粗略的上界，实际明显低于这个。
代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...