B. Gardener and the Array

思路:只要找到一个c他的每一位均在除了它的集合中出现过即可

这题T了2发,用来multiset,注意multiset大的时间复杂度是O(K + logn)k是相同元素的个数,能用map尽量用map

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
#include <bits/stdc++.h> 

using namespace std;

const int N = 1e5 + 10;

void solve()
{
int n; scanf("%d", &n);
vector<int>a[n + 1];
map<int, int>cnt;
for(int i = 1; i <= n; ++ i)
{
int k;
scanf("%d", &k);
a[i].push_back(k);
for(int j = 0; j < k; ++ j)
{
int x; scanf("%d", &x);
a[i].push_back(x);
cnt[x] ++;
}
}

for(int i = 1; i <= n; ++ i)
{
int k = a[i][0];
for(int j = 1; j <= k; ++ j)
{
if(cnt[a[i][j]] < 2) break;
if(j == k && cnt[a[i][j]] >= 2)
{
printf("Yes\n");
return;
}
}
}
printf("No\n");
}

int main()
{
// freopen("1.in", "r", stdin);
int t; scanf("%d", &t);
while(t --) solve();
return 0;
}