ABC278 F - Shiritori

向右看齐 2024-03-25 23:29 63阅读 0赞

**不懂博弈和状压DP，今晚加训状压DP！**

**博弈太难了，东西太多了，等蓝桥杯打完再说QwQ**

[F - Shiritori (atcoder.jp)][F - Shiritori _atcoder.jp]

题意：

![ba95eda08a103372304a0316d54a3723.png][]

![d26e8aff3d056062cbf0c5f2ac21463f.png][]

思路：

注意到数据范围是到16，因此可以考虑状压DP

状态设计：（考虑影响决策的因素+转移的特殊性质+记录答案）

因为要字符串头和另一个字符串的尾相同才转移，因此需要记录最后一个选的是第几个

设dp\[i\]\[j\]表示选的情况为i，最后一次选的是第j个

然后去考虑SG函数

遍历后面的状态，如果有一个为必败态，那么该状态就是必胜态

如果后面的状态全是必胜态，那么该状态就是必败态

因此我们需要倒着考虑状态

然后在枚举状态和决策的时候注意把不符合条件的状态筛去

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=3e2+10;
    const int mxe=2e5+10;
    
    string s[mxn];
    int n,dp[1<<16][30];
    void solve(){
        cin>>n;
        for(int i=0;i<n;i++) cin>>s[i];
        for(int i=(1<<16)-1;i>=1;i--){
            for(int j=0;j<n;j++){
                if((i>>j)&1){
                    for(int k=0;k<n;k++){
                        if((i>>k)&1) continue;
                        int p=i|(1<<k);
                        if(s[j].back()==s[k][0]&&dp[p][k]==0) dp[i][j]=1;
                    }
                }
            }
        }
        int ok=0;
        for(int i=0;i<n;i++){
            if(dp[(1<<i)][i]==0) ok=1;
        }
        if(ok) cout<<"First"<<'\n';
        else cout<<"Second"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[F - Shiritori _atcoder.jp]: https://atcoder.jp/contests/abc278/tasks/abc278_f
[ba95eda08a103372304a0316d54a3723.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b6bd8805600242cabfc8e6ca3cc3c426.png
[d26e8aff3d056062cbf0c5f2ac21463f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3f8ba5b9b9b14c96a7d18cff230e0f24.png