标签：AtCoder Beginner int 单词 vis needc 278 include sides

《F - Shiritori 》

博弈

 

 

 首先在这个博弈题中有个很重要的结论：

　　1.如果一个点，走一步，能够到达的点如果其中有一个为先手必胜点，那么这个点必然是先手必败点

　　2.如果一个点，走一步，能够到达的点如果全部为先手必败点，那么这个点必然是先手必胜点

这道题如果用爆搜的方式：

首先我们可以根据他的单词首尾相连的方式建个图，这个建图很有讲究，可以在O（n）的时间内建出

 

 

 即就是将开头为c的单词的下标i，保存在集合中，然后

在尾部为单词needc时，就去找头部为needc的单词

 

 

 注意这里的爆搜是要回溯的，因为全局的状态会根据搜索的起始点儿不同，比如：

 

 

 于是：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 20;
 7 // dp[i]表示以第i个字符串为先手最终的结果
 8 //-1表示最初始的状态，1表示先手必胜,0表示先手必败
 9 int dp[N], n;
10 string str[N];
11 // sides[i]表示以字母i开头的字符有哪些
12 vector<int> sides[2 * N];
13 // dfs时有用
14 bool vis[N];
15 int dfs(int u)
16 {
17     int needc = str[u].back() - 'a';
18     for (int i = 0; i < sides[needc].size(); i++)
19     {
20         int to = sides[needc][i];
21         if (!vis[to])
22         {
23             vis[to] = true;
24             if (dfs(to))
25             {
26                 vis[to] = false;
27                 return dp[u] = 0;
28             }
29             vis[to] = false;
30         }
31     }
32     return dp[u] = 1;
33 }
34 int main()
35 {
36     cin >> n;
37     for (int i = 1; i <= n; i++)
38     {
39         cin >> str[i];
40         int c = str[i][0] - 'a';
41         sides[c].push_back(i);
42     }
43     for (int i = 1; i <= n; i++)
44     {
45         vis[i] = true;
46         if (dfs(i))
47         {
48             cout << "First" << endl;
49             return 0;
50         }
51         vis[i] = false;
52     }
53     cout << "Second" << endl;
54     return 0;
55 }

然鹅会超时，按照状态压缩我还不理解：

 

 

 

 

 这里我有很多疑惑点:

1.这里枚举k，如果枚举的最后的一个单词，根本不存在怎么办？

比如状态1111011是枚举到的,但是枚举到的单词k根据不存在于任何上面的状态单词中怎么办？

  《AtCoder Beginner Contest 209 E - Shiritori 》

 

 

 

 

 

标签：AtCoder,Beginner,int,单词,vis,needc,278,include,sides
From： https://www.cnblogs.com/cilinmengye/p/16921208.html