F - Shiritori
题解:n最大16,所以可以状态压缩,相当于n个点的带权有向图。
dp[i][j]表示当前状态为i,j结尾的情况,其中dp[i][j]=1表示First赢,0为second赢,如果一个字符串s[i],第一个字符为j,那么如果dp[k][s[i].back()]为1那么,dp[i][j]为0,反之亦然,其中最后的状态,就是dp[(1<<n)-1][j]肯定为1,因为First可以选择直接从这个状态开始。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll mod=1e9+7;
typedef pair<ll,ll> pll;
#define endl '\n'
ll n;
string s[N];
ll dp[1<<16][30];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;cin>>n;
for(ll i=0;i<n;i++) cin>>s[i];
for(ll i=(1<<n)-1;i;i--){
for(ll k=0;k<26;k++){
ll pt=1;
for(ll j=0;j<n;j++){
if((1<<j)&i) continue;//判断当前状态中包不包含这个字符串
if(s[j][0]!=k+'a') continue;//判断能收尾接上
if(dp[i|(1<<j)][s[j].back()-'a']){//如果为1便是0
pt=0;break;
}
}
dp[i][k]=pt;
}
}
for(ll i=0;i<n;i++){
if(dp[1<<i][s[i].back()-'a']){
cout<<"First"<<endl;return 0;
}
}
cout<<"Second"<<endl;
}
标签:AtCoder,typedef,const,Beginner,Contest,ll,278,dp
From: https://www.cnblogs.com/hhzp/p/16911116.html