LG 题解 CF936B Sleepy Game

• Solution
• Code

题目传送

Solution

题意非常的简单，没啥可说的。

先判断 Win 的情况：

你考虑用 \(f_{u,0/1}\) 来表示走到 \(u\) 这个点走了偶（奇）步这个状态有没有出现过。

对于边 \((u,v)\)，显然有转移方程：

然后你在记录一个出度。

这样的话，dfs 更新一遍，最后看一看出度为 \(0\) 的点走了奇步这个状态存在没有。

题目要求输出路径，这个操作比较平凡，记录一个 \(pre\) 递归输出即可。

再考虑判断 Draw 的情况。

我们要注意的是 Draw 的优先级比 Lose 要高。估计就我一个人没看出来。

所以在不能走奇步停止的情况下，能进圈就进圈。

一开始我的想法是用 tarjan 缩点，建出新图，接着从 \(s\) 所在点 dfs，看看经过的路径有没有环。但是我写挂了。

考虑另外一种更简单的做法，只从 \(s\) 跑 tarjan，记录下缩的最大环。

直接根据这个最大环的大小来判断就可以了。

其他问题看代码。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"< 1) puts("Draw");
    else puts("Lose");
    return 0;
}