原题链接
题目大意
现有一个游戏，给出$N \left ( 1 \le N \le 16 \right )$个不含空格的小写字母字符串（长度不超过10且字符串间两两互不相同），两人轮流从中选择字符串，每个字符串只能被选择一次。除第一次选择外，每次选择的字符串首字母必须和上一次选择的字符串的末字母相同。当轮到某人时没有可选的单词就会输掉，同时另一人获胜。
现在假设两人每次的决策都是最优的，问在给定的字符串下先手还是后手能获胜。
题目样例
1
2
3
4
5
6
7
8
9
10
11
12
13
| **Sample Input 1**
6
enum
float
if
modint
takahashi
template
**Sample Output 1**
First
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| **Sample Input 2**
10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec
**Sample Output 2**
Second
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| **Sample Input 3**
16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs
**Sample Output 3**
First
|
题解
由$\left ( 1 \le N \le 16 \right )$想到可以将每个单词的使用情况以状态压缩的形式表示，这里假设二进制位上1对应单词还没有用过，0表示已被选过，用一个int变量来表示目前还能使用的单词的集合。
经分析，显然所有单词都被选过的状态为必败状态，作为动态规划的初状态，这里将必败设为0。
在游戏的玩家必定做出最优决策的情况下，可以把游戏拆分成各个局面来分析。
一个局面是必胜局面的充要条件是该局面存在将对手引入必败局面的合法决策。
而必败局面的所有合法决策都只能将对手引入必胜局面，或者本身到这就败了。
状态定义和转移
$dp[i][j]$表示当前字符串使用情况状态压缩为i，上一个末字母是j的局面，1为必胜，0为必败。
显然$dp[0][j]=0 \qquad (字符a \le j \le 字符z)$
对于局面$dp[i][j]$，只要有一个游戏推进顺序在其之后的局面是必败的，它就是必胜的，否则必败。
按与游戏推进相反的方向DP，最后检查游戏开始时是否为必胜局面即可判断谁能获胜。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> PII;
int main(){
fastIO
int n;
cin>>n;
vector<PII> words;
for(int i=0;i<n;i++){
string s;
cin>>s;
words.push_back({s.front()-'a',s.back()-'a'});
}
vector<int> dp(1<<n);
for(int i=1;i<1<<n;i++)
for(int j=0;j<n;j++)
if(1&i>>j)
dp[i] |=(1&~dp[i^1<<j]>>words[j].second)<<words[j].first;
cout<<(dp.back()?"First":"Second")<<endl;
return 0;
}
|
