题解：P17115 [Algo Beat 009 & MROI-R1] ANDOR

· · 题解

题解：P17115 [Algo Beat 009 & MROI-R1] ANDOR

传送门

思路

首先 (a \operatorname{and} b) + (a \operatorname{or} b) = a + b。

::::success[证明]{open} 设 x,y\in\{0,1\}，求证：

(x\operatorname{and} y)+(x\operatorname{or} y)=x+y

枚举四种组合：

  1. x=0,y=0$：$(x\operatorname{and} y)+(x\operatorname{or} y)=0+0=x+y
  2. x=0,y=1$：$(x\operatorname{and} y)+(x\operatorname{or} y)=0+1=x+y
  3. x=1,y=0$：$(x\operatorname{and} y)+(x\operatorname{or} y)=0+1=x+y
  4. x=1,y=1$：$(x\operatorname{and} y)+(x\operatorname{or} y)=1+1=x+y

把要求证的式子展开：

a\operatorname{and} b = \sum_{k=0} (x_k\operatorname{and} y_k) 2^k a\operatorname{or} b = \sum_{k=0} (x_k\operatorname{or} y_k) 2^k

左边：

\begin{aligned} (a\operatorname{and} b)+(a\operatorname{or} b) &= \sum_{k=0} (x_k\operatorname{and} y_k)2^k + \sum_{k=0} (x_k\operatorname{or} y_k)2^k \\ &= \sum_{k=0} \big[(x_k\operatorname{and} y_k)+(x_k\operatorname{or} y_k)\big]2^k \end{aligned}

由上面的结论 (x_k\operatorname{and} y_k)+(x_k\operatorname{or} y_k)=x_k+y_k，代入得：

\begin{aligned} (a\operatorname{and} b)+(a\operatorname{or} b) &= \sum_{k=0} (x_k + y_k)2^k \\ &= \sum_{k=0} x_k 2^k + \sum_{k=0} y_k 2^k \\ \end{aligned}

将整数 a，b 展开：

a = \sum_{k=0} x_k 2^k b = \sum_{k=0} y_k 2^k

其中 x_k,y_k\in\{0,1\} 为 a，b 的第 k 个二进制位。

右边：

a+b =\sum_{k=0} x_k 2^k+\sum_{k=0} y_k 2^k

左边等于右边，所以对任意非负整数 a,b，有

(a \operatorname{and} b) + (a \operatorname{or} b) = a + b

::::

于是我们可以先求出 p_1 + p_2，p_1 + p_3，p_2 + p_3 的值，然后联立三个方程，解出 p_1， p_2， p_3，并用 p_1 + p_i 的值求出 p_i。

又因为 p 是一个排列，所以在求 p_n 时并不需要询问。

总询问次数为 2\times (3 + n-3-1)=2n-2。

代码

int main()
{
    int n = rd(), k = rd();
    int a, b;
    cout << "? and 1 2" << endl;
    a = rd();
    cout << "? or 1 2" << endl;
    b = rd();
    ll s12 = a + b;

    cout << "? and 1 3" << endl;
    a = rd();
    cout << "? or 1 3" << endl;
    b = rd();
    ll s13 = a + b;

    cout << "? and 2 3" << endl;
    a = rd();
    cout << "? or 2 3" << endl;
    b = rd();
    ll s23 = a + b;

    p[1] = (s12 + s13 - s23) / 2;
    p[2] = s12 - p[1];
    p[3] = s13 - p[1];

    ll sum = p[1] + p[2] + p[3];
    for (int i = 4; i <= n - 1; i++)
    {
        cout << "? and 1 " << i << endl;
        a = rd();
        cout << "? or 1 " << i << endl;
        b = rd();
        p[i] = a + b - p[1];
        sum += p[i];
    }
    p[n] = (ll)n * (n - 1) / 2 - sum;

    cout << "! ";
    for (int i = 1; i <= n; i++)
        cout << p[i] << ' ';
    cout << endl;
    return 0;
}