P8371 绿色游戏题解

Fdjo · 2023-12-17 17:50:10 · 题解

题目传送门

题解：

题目大意：

Ann 和 Billy 在一个棋盘上移动 1 个棋子，棋盘由 a+b 个点构成，其中有一些是绿色的，前 a 个属于 Ann，后 b 个属于 Billy。这些点都有后继点且后继点一定属于对方，对于每一次移动，都由当前棋子所在点的拥有者完成，当棋子第二次到达一个点 Q，游戏结束，如果在 Q 到 Q 的过程中，棋子到过绿色点，Ann 赢，否则 Billy 赢。问你 Ann 有必胜策略的起始点有多少个并输出。

思路分析：

我们设 f _ {i} 表示从 i 开始时 Ann 是否有必胜策略。那么：

当 i \le a 时：（b _ {w} 表示 i 的第 w 个后继点) f _ {i} = f _ {b _ {1}} \operatorname{or} f _ {b _ {2}} \operatorname{or} \cdots \operatorname{or} f _ {b _ {n}}，因为当前由 Ann 操控，他可以选择去一个有必胜策略的点。
当 i > a 时：（b _ {w} 表示 i 的第 w 个后继点）f _ {i} = f _ {b _ {1}} \operatorname{and} f _ {b _ {2}} \operatorname{and} \cdots \operatorname{and} f _ {b _ {n}}，因为当前由 Billy 操控，只要有不让 Ann 胜利的点，他就会去，所以 Ann 能胜利当且仅当这个点所有后继点都能让 Ann 胜利。

到这里我们遇到了一个问题，这个题的图存在环，所以我们无法常规计算。~~经过我在英语课上的不断思索~~，发现可以迭代求解。

所谓迭代，就是反复通过旧数据计算新数据，并将结果用到下一次计算中，从而不断逼近直至找到正确答案。本题我们可以搞一个集合 Q，然后具体操作如下：

把目前的绿点全加入集合。
从绿点向外扩展到每个点，对于第 i 个点来说，如果 i \le a，那么他只要有后继点是绿点就把它加进来并标记为绿点，如果 i > a，那么只要他所有的后继点都是绿点就把它加入集合并标记为绿点。
通过以上操作，有一些绿点其实是不符合递推式的，所以对于绿点 i，如果 i \le a，那么只要他所有后继点都不在 Q 中，就把它搞出去并标记为非绿点，如果 i > a，那么只要他有一个点不在 Q 中，就把它踢出集合并标记为非绿点。

最重要的一点，我们要重复这个过程，直到迭代变得稳定。（如果不进行这一步，就会只得 27 分）。

具体来说，我们要让所有绿点都符合条件才能停止，否则答案是错误的。有两种方法：一是强制执行 a+b 次（稍慢）。二是在每次操作结束后，判断是否有绿点被改为非绿点，如果没有了，意味着已经稳定，继续循环也没有意义，此时退出，并输出结果。如果还有就继续执行。

（本人存图喜欢用 vector，本题也可以用其他方式，集合 Q 用队列 queue 维护即可)。

100pts Code:

#include "iostream"
#include "cstdio"
#include "queue"
#include "vector"
using namespace std;
int a,b,col[6005],bac[6005],f[6005],ans;//col[i] 表示第 i 个点的颜色;bac[i] 表示第 i 个点的后继点数目
vector<int> e[6005];//存图
bool work()
{
    queue <int> q;
    int tmp[6005];//因为后期 bac 数组要修改，所以先存到另外一个数组
    for (int i = 1;i <= b;i++)
    {
        tmp[i] = bac[i];

        f[i] = col[i];
        if (f[i] == 1)q.push(i);//把所有绿点加入
    }
    while (!q.empty())//类似bfs
    {
        int cur = q.front();
        q.pop();

        for (auto i:e[cur])
        {
            if (f[i] == 0)
            {
                tmp[i]--;//每有一个后继点成为绿点就减一，为零时就合法，入集合
                if (tmp[i] == 0 || i <= a)
                {
                    f[i] = 1;
                    q.push(i);
                }
            }
        }
    }
    for (int i = 1;i <= b;i++)
    {
        tmp[i] = bac[i];
        if (f[i] == 0)//找非绿点，加入集合，这次要往外筛
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (auto i:e[cur])
        {
            if (f[i] == 1)
            {
                tmp[i]--;//每有一个后继点成为非绿点就减一，为0时不合法，出集合
                if (tmp[i] == 0||i > a)
                {
                    f[i] = 0;
                    q.push(i);
                }
            }
        }
    }
    bool fl = 0;
    for (int i = 1;i <= b;i++)
    {
        if (col[i] == 1 && f[i] == 0)//统计是否有绿点被修改（迭代是否稳定），并修改颜色，作为下一次计算的初始数据
        {
            col[i] = 0;
            fl = 1;
        }
    }
    return fl;
}
int main()
{
    scanf("%d%d",&a,&b);
    b += a; //此时 a+b 就是点的总数
    for (int i = 1;i <= b;i++)
    {
        scanf("%d%d",&col[i],&bac[i]);
        for (int j = 1;j <= bac[i];j++)
        {
            int u;
            scanf("%d",&u);
            e[u].push_back(i);//反向建边，便于计算 f[i]
        }
    }
    while (work());//work函数是bool类型的，只要返回值为一就继续进行，这里也可以重复执行点的总数量次。
    for (int i = 1;i <= b;i++)
    {
        if (f[i] == 1)
        {
            ans++;
        }
    }
    printf("%d\n",ans);//先输出个数
    for (int i = 1;i <= b;i++)
    {
        if (f[i] == 1)
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

P8371 绿色游戏 题解

题解：