LG 题解 CF936B Sleepy Game

Solution

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

先判断 Win 的情况：

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

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

[f_{v,0} |= f_{u,1} ]

[f_{v,1} |= f_{u,0} ]

然后你在记录一个出度。

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

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

再考虑判断 Draw 的情况。

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

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

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

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

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

其他问题看代码。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct edge {
    int from, to, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 1;

int n, m, s, cnt = 0, t = 0, Max = 0;
int od[MAXN];
int pre[MAXN][2];
int dfn[MAXN], low[MAXN], siz[MAXN], num[MAXN], stc[MAXN], sc = 0;
bool f[MAXN][2], vis[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void add_edge(int from, int to) { e[++num_edge] = (edge){from, to, head[from]}, head[from] = num_edge; }

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt, vis[u] = true, stc[++sc] = u;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        int cnt = 0;
        int pre = stc[sc--]; vis[pre] = false;
        ++cnt;
        while(pre != u) {
            pre = stc[sc--], vis[pre] = false;
            ++cnt;
        }
        Max = max(Max, cnt);
    }
}

void Dfs(int u) {
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to, flag = false;
        if(!f[v][0] && f[u][1]) f[v][0] = true, flag = true, pre[v][0] = u;
        if(!f[v][1] && f[u][0]) f[v][1] = true, flag = true, pre[v][1] = u;
        if(flag) Dfs(v);
    }
}

void Print(int u, int p) {
    if(pre[u][p]) Print(pre[u][p], p^1);
    printf("%d ", u);
}

int main()
{
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) {
	    int k = read();
	    for(int j = 1, v; j <= k; ++j) {
	        v = read();
	        add_edge(i, v);
	        od[i]++;
        }
    }
    s = read();
    f[s][0] = true;
    Dfs(s);
    bool flag = false;
    for(int i = 1; i <= n; ++i) {
        if(!od[i] && f[i][1]) {
            puts("Win");
            Print(i, 1);
            puts("");
            return 0;
        }
    }
    tarjan(s);
    if(Max > 1) puts("Draw");
    else puts("Lose");
    return 0;
}