美满百褶裙

文章
5
资源
0
加入时间
3年0月28天

K King of the Waves(不回溯的特殊dfs)

首先分析可知,0应当作为序列尾,而前面放一个0能赢的,同理要保证倒数第二个是前面序列的最后赢家,要使得前面放一个他能赢的,由此可以写出一个由0开始的dfs,并在dfs中回溯,如果不成立,再从该位置找到另一个满足条件的点继续dfs但是这种方法太过费时,而题目中有个关键点,A如果能赢B,则A B和B A结果一样,不用严格组成输赢链,假设0的那行为X110000,对于第一个1向下dfs,形成了序列A(且A序列不完整,不能作为答案),按第一种写法需要重新从第二个1dfs,但是如果直接把第二个1放在A序