首页 > 代码库 > codeforces 456d （字典树+DP）
codeforces 456d （字典树+DP）
题目大意：给定n，表示字符串集合。给定k，表示进行了k次游戏，然后是n个字符串。每局开始，字符串为空串，然后两人轮流在末尾追加字符，保证新的字符串为集合中某字符串的前缀，不能操作者输，新一轮由上一句输的人先手。
思路：00 代表不能控制 01代表败，10代表胜，11代表能输能赢
转自 http://blog.csdn.net/blankcqk/article/details/38459033
附带字典树模版：
void insert(){ int len = strlen(s); int now = root; for(int i = 0;i < len;i++){ int tmp = s[i] - ‘a‘ + 0; if(!q[now][tmp]) q[now][tmp] = ++top; now = q[now][tmp]; }}其中root为初始值加入所得的序号根据加入的顺序得来
AC代码：
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <queue>#include <stack>#include <cmath>//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;#define PF(x) cout << "debug: " << x << " ";#define EL cout << endl;#define PC(x) puts(x);typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;const int INF = 0x5f5f5f5f;const int N= 1000050;const int maxn=1e5+10;int n,k,top,root,q[maxn][30];char s[maxn];void insert(){ int len = strlen(s); int now = root; for(int i = 0;i < len;i++){ int tmp = s[i] - ‘a‘ + 0; if(!q[now][tmp]) q[now][tmp] = ++top; now = q[now][tmp]; }}int solve(int now){ int fg = 0,ans = 0; for(int i = 0;i <26;i++){ if(q[now][i]){ fg = 1; ans |= solve(q[now][i]) ^ 3;//可知子状态对父状态的贡献为^3再用|则得父状态 } } if(!fg) ans = 1;//没有后续状态则此状态先手必败 return ans;}int main () { // freopen("in.txt","r",stdin); cin>>n>>k; while(n--){ scanf("%s",s); insert(); } int ans = solve(root); if(ans == 3) cout<<"First"<<endl; else if(k & 1 && ans == 2) cout<<"First"<<endl; else cout<<"Second"<<endl; return 0;}
codeforces 456d （字典树+DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。