題意 ：

• 給兩個長度為n - 1的序列b和c，定義bi = (ai | ai-1)，ci = (ai + ai-1)，求滿足該條件的a序列有多少種可能。

思路 ：

• a + b == a ^ b + 2(a & b) （*）
• a + b == a & b + a | b，所以已知bi，ci，那么定義di = (ai-1 & ai) = ci - bi
• 已知a1即可確定整個a序列，因此判斷a1的取值有多少種可能即代表a序列有多少種可能。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <vector> #include <unordered_map> #include <unordered_set> #include <set> #define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll;const int N = 1e5 + 10;int b[N], c[N]; int n;// x表示當前這一位是0還是1 int dfs(int pos, int x) {for (int i = 2; i <= n; i ++ ){int p = (b[i] >> pos & 1), q = (c[i] >> pos & 1);if (x && p && q) x = 1;else if (!x && p && q) return 0;else if (x && p && !q) x = 0; // 交替else if (!x && p && !q) x = 1; // 交替else if (x && !p && q) return 0;else if (!x && !p && q) return 0;else if (x && !p && !q) return 0;else if (!x && !p && !q) x = 0;}return 1; }int main() {IOS;cin >> n;for (int i = 2; i <= n; i ++ ) cin >> b[i];for (int i = 2; i <= n; i ++ ) cin >> c[i], c[i] -= b[i];for (int i = 2; i <= n; i ++ )if (c[i] < 0){cout << 0 << endl;return 0;}ll ans = 1;for (int i = 0; i < 31; i ++ ){int x = dfs(i, 0), y = dfs(i, 1);ans *= (x + y);}cout << ans << endl;return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的2021牛客暑期多校训练营8 OR 相加和与和或-dfs判断假设情况是否有矛盾的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。