Problem:
题目链接
有n个棋手,每两个棋手之间的胜负关系是确定的,如果一个人可以在他参与的所有比赛中取得胜利,那么称他为“候选冠军”。
(一个奇葩的输入输出格式:
现在为了能够知道谁是候选冠军,需要进行至多2n场比赛,每场比赛选出一个选手,与其他选出的任意个选手分别比赛,但不会有人淘汰,并给出他能赢这些人里面的几个,问都有谁是候选冠军。
数据范围:3<=n<=250
思路
由题意推得两个结论:
有可能赢得自己参与的所有比赛才是候选冠军
<=> 除了自己以外,记录自己可以战胜的人为集合A,
则自己不可以战胜的人若均可被A中人战胜,那么这个人就是候选冠军
(即,可以让他人帮自己淘汰对方,然后收渔翁之利)
=>结论1:可以战胜候选冠军的人一定也是候选冠军
=>结论2:不是候选冠军的人一定无法战胜任意一个候选冠军
建立有向图,辅助理解
=> 根据胜负关系建立图,单向边。
判断选手i是否是候选冠军,即从点i出发,是否可以将图走完
※注:由于任意两个人之间都会有胜负关系,所以这一定是一个完全图
由结论得推论
由结论1==> 候选冠军们 构成了一个强连通分量,该强连通分量入度为0,
将该强连通分量记为G,内含p个点,则其向G外的连边有
(n-p)* p
条
连通分量内部的连边有
i * (i-1)/2
条
推论1:G所有点出度和一定等于
p*(n-p)+p*(p-1)/2
; G的入度=
p*(p-1)/2
由结论2==> 非候选冠军的单个点,其
出度 <=(n-p)
,因为只能连向G外节点
候选冠军的单个点,其
出度>=(n-p)
,因为可以战胜所有非候选
推论2:G内任意点的出度 一定大于等于 G外任意点的出度
核心结论:
由推论1 推论2
=>
核心结论:按出度从大到小排序节点,找到合适的p,使得满足上述。
则所求答案即为,出度前p大个点的所有点
该思路部分源自:
知乎博主
代码
奇怪的输入格式:
for(int i = 1; i <= n; i++){//莫名其妙的输入格式,笑死
string s = string(n, '1');
s[i - 1] = '0';
p[i].second = i;
cout << "? " << i << ' ' << s << endl;
cin >> p[i].first;
}
然后对出度排序一下,寻找答案即可。