NOIOnline 2022 讨论

将每个人按会的题目 $k_i$ 从大到小排序。

按顺序枚举每个人 $x$，记录每道题目 $i$ 到当前会这道题的人且序号最小的人 $t_i$。

如果有两个不同的人与 $x$ 有交集。不妨设这两个人的题目集合为 $A,B$，$x$ 会的集合为 $S$。

  • $A\subseteq B$
    • 如果 $S \subseteq A$ ，显然就不会枚举到 $B$ 中的数了。
    • 否则 $A$ 和 $S$ 有交集且会相互讨论。
  • $B\subseteq A$ 同上
  • $A\cup B \not = \varnothing$ ，如果不包含但有交集，应该在算法枚举到 $A$ 或者 $B$ 时就退出了，故不存在这种情况。
  • $A\cup B=\varnothing$ ，随便出一个就是解。

综上，如果和两个不同的人有交集，便一定有解。

如果只有一个有交集，判断是否为包含关系即可。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005 
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n;
vector<int>a[maxn];
int t[2*maxn],id[maxn],len[maxn];
inline bool cmp(int x,int y) {return len[x]>len[y];}
int vis[2*maxn]; 
inline bool check(int i,int j) {
	int flag1=0,flag2=0;
	for (int x:a[j]) vis[x]=0;
	for (int x:a[i]) vis[x]=1;
	for (int x:a[j]) {
		vis[x]+=2;
		if (vis[x]==2) flag1=1; 
	}
	for (int x:a[i]) flag2|=(vis[x]==1);
	return flag1&&flag2;
}
inline void solve(void) {
	int i,j,x;
	read(n);
	for (i=1;i<=n;i++) {
		read(len[i]);a[i].clear();id[i]=i;
		for (j=0;j<len[i];j++) read(x),t[x]=0,a[i].push_back(x);
	}
	sort(id+1,id+1+n,cmp);
	for (i=1;i<=n;i++) {
		int las=0,flag=0;
		for (int x:a[id[i]]) 
			if (!t[x]) flag=1;
			else {
				if (!las) las=t[x];
				if (t[x]!=las) {
					if (check(id[i],t[x])) return printf("YES\n%d %d\n",id[i],t[x]),void();
					return printf("YES\n%d %d\n",id[i],las),void();
				}
			}
		if (las&&flag) {
			return printf("YES\n%d %d\n",id[i],las),void();
		}
		for (int x:a[id[i]]) t[x]=id[i];
	}
	puts("NO");
}
signed main(void){
	int T;
	read(T);
	while (T--) solve(); 
	return 0;
}