【Codeforces】(场次 Hello 2023 E题) Anya‘s Simultaneous Exhibition

  • Post author:
  • Post category:其他




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;
    }

然后对出度排序一下,寻找答案即可。



版权声明:本文为l961983207原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。