Codeforces Round 843 B题

题意：

记$ f(a)$ 是 $a$ 数组中，所有数的按位或。

现有 $n$ 个数 $c_1,c_2…c_n $组成的数组，询问是否有两个不同的子数组 $a和b$,使得 $f(a)=f(b)$。

分析：

考虑下述方法：

  • 选择$a=c,b$是$c$中去掉某个元素形成的数组。

例如样例

1
2
3
4
5
4
3 1 2 4
2 2 4
4 1 2 5 6
2 2 5

$a$ 选取所有的数，所以 $a$ 在 $1,2,4,5,6$ 位上都表现为 1 $, b$ 去除了最后一个数，其按位或一致。

判别方法如下：

  • 对于每一个位，统计它在这 n 个数中的出现次数。
  • 如果去除某个数之后，出现次数大于等于 1 的位的集合不变，则可行。

例如在上面的策略中，每个数的出现次数为：$ \{1:2;2:4;4:2;5:2;6:1\}$ ，去除了最后一个数则是 $\{1:2;2:3;4:2;5:1;6:1\}$ ，满足要求。

我们可以证明任意的方案都可以转化为这一类方案。假设某种 $a≠b$ 方案符合要求，则通过以下方法可以转化：

  • 假设此时$ a 不是 b $的子集，如果是，交换 $a,b$ 。
  • 对于 $b 选取了，但 a$ 没有选取的数，即使 a 选取它们，依然可以满足需求。因此可以转化为一种 $b⊂a$ 的方案。这里可保证 $a≠b$ 。
  • 对于$ a $在 $c $中的补集中的数，让 $a,b$ 都选取它们，依然可以满足要求。此时 $a=c,b≠a$
  • 如果 $b 选$取了少于$ n−1 $个数，证明 $b 在$所有位上都至少出现一次，和 $a$ 相同。那么令 $b 再$随意选取直到 $n−1$ 个数，依然可以满足要求。

因此，只要上述一类方案不可行，就不存在可行的方案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve()
{
    int n; cin >> n;
    map<int, int> cnt; // 记录每个位的出现次数
    vector<int> v[n + 1]; //记录每个数为1的位数
    for (int i = 1;i <= n;i++)
    {
        int k; cin >> k;
        for (int j = 1;j <= k;j++)
        {
            int x; cin >> x;
            v[i].push_back(x);
            cnt[x]++;
        }
    }
    for (int i = 1;i <= n;i++)
    {
        int flag = 1;
        for (auto it : v[i])
        {
            if (cnt[it] == 1)
                // 如果仅出现一次的话，去除这个数之后，在这一位上就只能为0，不满足要求
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
        {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    std::system("pause");
    return 0;
}