牛客多校8.D.OR 二进制+思维

Problem Analysis

题目给给定数组 b [ ] 、 c [ ] b[]、c[] b[]、c[]​​各具有 n − 1 n - 1 n−1​个元素，求满足 b [ i ] = a [ i ]   o r   a [ i − 1 ] ∧ c [ i ] = a [ i ] + a [ i − 1 ] b[i] = a[i]\ or\ a[i - 1] \wedge c[i] = a[i] + a[i - 1] b[i]=a[i] or a[i−1]∧c[i]=a[i]+a[i−1]条件的的具有 n n n个元素的 a a a​​序列的个数。

拿到题目没啥思路，和队友讨论只需要确定 a a a​​序列的首个元素，后面元素即可唯一确定，发现确实是正确的，但对于首元素的枚举方法如果纯暴力肯定会T，遂向学长求救，得知了神奇的结论： a + b = ( a ∨ b ) + ( a ∧ b ) a + b = (a \vee b)+(a \wedge b) a+b=(a∨b)+(a∧b) 附赠一个证明过程： a + b = ∑ k ( p k + q k ) 2 k a   o r   b = ∑ k ( p k ∨ q k ) 2 k a   a n d   b = ∑ k ( p k ∧ q k ) 2 k \begin{aligned} a+b=\sum_k(p_k+q_k)2^k \\ a \ or \ b=\sum_k(p_k\vee q_k)2^k\\ a \ and \ b=\sum_k(p_k \wedge q_k)2^k \\ \end{aligned} a+b=k∑​(pk​+qk​)2ka or b=k∑​(pk​∨qk​)2ka and b=k∑​(pk​∧qk​)2k​

a + b − a   o r   b − a   a n d   b = ∑ k ( p k + q k − p k ∧ q k − p k ∨ q k ) 2 k = 0 a+b-a \ or \ b - a \ and \ b = \sum_k(p_k+q_k-p_k \wedge q_k - p_k \vee q_k)2^k=0 a+b−a or b−a and b=k∑​(pk​+qk​−pk​∧qk​−pk​∨qk​)2k=0

然后通过列真值表，可以证明 a + b = ( a ∨ b ) + ( a ∧ b ) a + b = (a \vee b)+(a \wedge b) a+b=(a∨b)+(a∧b)成立。​

那么我们现在可以得出 a ∧ a_{\wedge} a∧​数组(即为 c − b c - b c−b​)，以及 a ∨ a_{\vee} a∨​(即为 b b b​)，因此我们可以根据这两个数组求 a [ 1 ] a[1] a[1]：

从最低位开始，每次枚举位为 0 0 0或 1 1 1，遍历 a ∨ a_{\vee} a∨​和 a ∧ a_{\wedge} a∧​序列，检验是否成立。如果 0 0 0和 1 1 1均不成立，则 a a a序列无解直接输出 0 0 0​；如果有一个成立，那么对于该位情况唯一，继续枚举；如果全部成立，则对于该位有两种情况，总情况 × 2 \times2 ×2。

AC Code

#include 
using namespace std;

const int N = 1e5 + 10;
int b[N], c[N];

inline bool check(int k, int x, int n){
    for (int i = 1; i > k) & 1;
        int _and = (c[i] >> k) & 1;
        if (_or && !_and) x ^= 1;
        if (_or && _and && !x) return false;
        if (!_or && _and) return false;
        if (!_or && !_and && x) return false;
    }
    return true;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n = 0, ans = 1; cin >> n;
    for(int i = 1; i > b[i];
    for(int i = 1; i > c[i];
    for(int i = 1; i