题解：P12089 [RMI 2019] 钓鱼纸牌 / Fishing Game

· · 题解

讲一个模拟过程的做法。有点像小时候玩的乌龟纸牌，即为两人以上轮番进行的游戏。开局时从牌堆抽一张无人知晓的牌并藏起来，给每人分发好牌后开始清掉手中的对子，然后开始按顺时针或逆时针方向依次抽取下位玩家的牌，抽到牌后如果获得对子需清掉。可知最终会有一张牌留在某位玩家手中，和那张藏起来的牌可以成对。只有在此时才得知隐藏的牌。本题即三位玩家模拟上述过程，只不过无需藏初始的牌，无需确定谁留最后一张牌，流程改为随机传牌，并且所有人进行过一次传牌后，能保证有人凑出对子，故游戏一定会顺利完成而不陷入循环。输出所有的状态即可。

考虑到 A - B - C - A 为一轮传牌游戏，初始时所有人手上都没有对子，并且手中的牌都可以和剩下两位玩家凑成对子。A 将牌给 B 会有如下两种结果：这张牌将凑成一对，B 清掉手中一对对子，他们俩之间能凑牌的对数少一对；这张牌不能凑成对子，为 C 所需要成对子的牌，此时 B、C 两人存在的对子数将多一对，A、C 两人存在的对子数将少一对。题目问游戏过程一共存在多少种状态，从状态考虑首先想到记忆化搜索。先存一下三位玩家各自之间能凑的对数。

for (int p = 1; p <= 3; p ++ ) 
    {
        for (int i = 1; i <= 2 * n; i ++ ) 
        {
            int x;
            cin >> x;
            cards[x].push_back(p);  
        }
    }

    int bc = 0, ac = 0, ab = 0;
    for (int i = 1; i <= 3 * n; i ++ ) 
    {
        sort(cards[i].begin(), cards[i].end());
        if (cards[i].size() >= 2) 
        {
            if (cards[i][0] == 2 && cards[i][1] == 3) 
                bc ++;
            if (cards[i][0] == 1 && cards[i][1] == 3) 
                ac ++;
            if (cards[i][0] == 1 && cards[i][1] == 2) 
                ab ++;
        }
    }

然后使用记忆化搜索的思路去更新方案数，结果也是不出意外的超时了。

int dp[N][N][N], vis[N][N][N][4][2];
int n, T;

int dfs(int bc, int ac, int ab, int st, int flag) 
{
    if (bc == 0 && ac == 0 && ab == 0) 
        return 1;

    if (st == 0 && !flag) 
        return 0;

    if (vis[bc][ac][ab][st][flag]) 
        return dp[bc][ac][ab];

    vis[bc][ac][ab][st][flag] = 1;
    dp[bc][ac][ab] = 0;

    if (st == 0)
    {
        st = 1;
        flag = 0;
    }

    if (st == 1)
    {
        if (ab > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * ab * dfs(bc, ac, ab - 1, 2, 1)) % mod;
        if (ac > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * ac * dfs(bc + 1, ac - 1, ab, 2, flag)) % mod;
        if (ab == 0 && ac == 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * dfs(bc, ac, ab, 2, flag)) % mod;
    }
    else if (st == 2)
    {
        if (bc > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * bc * dfs(bc - 1, ac, ab, 3, 1)) % mod;
        if (ab > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * ab * dfs(bc, ac + 1, ab - 1, 3, flag)) % mod;
        if (bc == 0 && ab == 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * dfs(bc, ac, ab, 3, flag)) % mod;
    }
    else
    {
        if (ac > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * ac * dfs(bc, ac - 1, ab, 0, 1)) % mod;
        if (bc > 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * bc * dfs(bc - 1, ac, ab + 1, 0, flag)) % mod;
        if (ac == 0 && bc == 0)
            dp[bc][ac][ab] = (dp[bc][ac][ab] + 1ll * dfs(bc, ac, ab, 0, flag)) % mod;
    }

    return dp[bc][ac][ab];

一步为一个状态，递归消耗内存过于庞大，考虑一轮为一个状态，缩小递归空间后顺利通过。

Code:

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;

const int N = 300;
const int mod = 1e9 + 7;
int dp[N][N][N], vis[N][N][N];
int n, T;

int dfs(int bc, int ac, int ab) 
{
    if (vis[bc][ac][ab]) 
        return dp[bc][ac][ab];
    if (bc == 0 && ac == 0 && ab == 0) 
        return 1;

    vis[bc][ac][ab] = 1;

    vector<PII> opA = {{1, 0}, {2, -1}, {-1, -1}};
    vector<PII> opB = {{0, -1}, {2, 1}, {-1, -1}};
    vector<PII> opC = {{0, 2}, {1, -1}, {-1, -1}};

    for (auto op1 : opA)
    {
        array<int, 3> tmp1 = {bc, ac, ab}; 
        int cnt1 = 1;
        int flag1 = 0;

        if ((op1.x == -1 && tmp1[1] + tmp1[2] == 0) // 无对
        || (op1.x != -1 && tmp1[op1.x])) // 可传
        {
            if (op1.x != -1) 
            {
                cnt1 = (1ll * cnt1 * tmp1[op1.x]) % mod; // 更新方案
                tmp1[op1.x] --; // 传牌
                if (op1.y != -1) // 间接对
                    tmp1[op1.y]++;
                else
                    flag1 = 1; // 直接对
            }

            for (auto op2 : opB) 
            {         
                array<int, 3> tmp2 = tmp1;
                int cnt2 = cnt1;
                int flag2 = flag1;

                if ((op2.x == -1 && tmp2[0] + tmp2[2] == 0) 
                    || (op2.x != -1 && tmp2[op2.x])) 
                    {

                    if (op2.x != -1) 
                    {
                        cnt2 = (1ll * cnt2 * tmp2[op2.x]) % mod;
                        tmp2[op2.x]--;
                        if (op2.y != -1)
                            tmp2[op2.y]++;
                        else
                            flag2 = 1;
                    }

                    for (auto op3 : opC) 
                    {
                        array<int, 3> tmp3 = tmp2;
                        int cnt3 = cnt2;
                        int flag3 = flag2;
                        if ((op3.x == -1 && tmp3[0] + tmp3[1] == 0) 
                            || (op3.x != -1 && tmp3[op3.x])) 
                            {

                            if (op3.x != -1) 
                            {
                                cnt3 = (1ll * cnt3 * tmp3[op3.x]) % mod;
                                tmp3[op3.x]--;
                                if (op3.y != -1)
                                    tmp3[op3.y]++;
                                else
                                    flag3 = 1;
                            }

                            if (flag3)  // 如果这轮形成了对子
                                dp[bc][ac][ab] = (dp[bc][ac][ab] + 
                                    1ll * cnt3 * dfs(tmp3[0], tmp3[1], tmp3[2])) % mod;
                        }
                    }
                }
            }
        }
    }

    return dp[bc][ac][ab];
}

void solve() 
{
    memset(dp, 0, sizeof dp);
    memset(vis, 0, sizeof vis);
    vector<vector<int>> cards(3 * n + 10); 
    for (int p = 1; p <= 3; p ++ ) 
    {
        for (int i = 1; i <= 2 * n; i ++ ) 
        {
            int x;
            cin >> x;
            cards[x].push_back(p);  
        }
    }

    int bc = 0, ac = 0, ab = 0;
    for (int i = 1; i <= 3 * n; i ++ ) 
    {
        sort(cards[i].begin(), cards[i].end());
        if (cards[i].size() >= 2) 
        {
            if (cards[i][0] == 2 && cards[i][1] == 3) 
                bc ++;
            if (cards[i][0] == 1 && cards[i][1] == 3) 
                ac ++;
            if (cards[i][0] == 1 && cards[i][1] == 2) 
                ab ++;
        }
    }
    cout << dfs(bc, ac, ab) << endl;
}

int main()
{
    cin >> n >> T;
    while(T -- )
    {
        solve();
    }
    return 0;
}