CF455B 题解

$\text{Description}$

给定 $n$ 个非空字符串，你和对手交互行动，在一个初始为空字符串末尾填小写字母，每次填完都必须抱证该串为之前的 $n$ 个字符串之一的前缀，不能操作者输。

游戏会进行 $k$ 次，上一轮输的人先手，最后一轮赢的人赢下整个游戏，问先手必胜或后手必胜。

$n\le 10^5,k\le 10^9,\sum|s|\le 10^5$。

$\text{Solution}$

我们称这种博弈为双重博弈，本题中，内层博弈为填字符，外层博弈为选择胜负。

考虑如何解决内层博弈，分析发现，对 $n$ 个字符串建 Trie，然后进行转移。

考虑内层博弈的几种情况：

先手必定胜利，此时若 $k$ 为奇数则外层先手必胜，反之外层先手必败。
先手必定失败，此时外层先手必败。
先手可以控制输赢，此时外层先手必胜。
后手可以控制输赢，此时外层后手必胜。

按照上面分类讨论一下就行了。

$\text{Code}$

#include<bits/stdc++.h>
#define REG register
#define MAXN 100005
using namespace std;
inline void read(int& x){
    static char c;
    while(!isdigit(c=getchar()));x=c^48;
    while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

int n,k;

int Win[MAXN],Lose[MAXN],ch[26][MAXN];

int siz;

char str[MAXN];

inline void Insert(){
    int Now=0,len=strlen(str+1);
    for(REG int i=1;i<=len;++i){
        if(!ch[str[i]-'a'][Now]){Now=ch[str[i]-'a'][Now]=++siz;continue;}
        Now=ch[str[i]-'a'][Now];
    }
}

void dfs(int Now){
    int tmp=0,flag=0;
    for(REG int i=0;i<=25;++i){
        if(!ch[i][Now]) continue;
        dfs(ch[i][Now]),Win[Now]|=(Win[ch[i][Now]]^1),tmp|=(Lose[ch[i][Now]]^1),flag=1;
    }
    Lose[Now]=flag?tmp:1;
}

inline void Work(){
    read(n),read(k);
    for(REG int i=1;i<=n;++i) scanf("%s",str+1),Insert();
    dfs(0);
    if(Win[0]^Lose[0])
        if(Win[0])
            if(k&1) puts("First");
            else puts("Second");
        else puts("Second");
    else
        if(Win[0]) puts("First");
        else puts("Second");
}

int main(){Work();}

2021-03-20

CF Chapter2 简要题解

CodeForces

CF455B 题解

CF455B 题解

$\text{Description}$

$\text{Solution}$

$\text{Code}$

Catalogue

Links

Categories

Tag Cloud

Recent

Archives

Tags

Recent

Archives

Tags

Your browser is out-of-date!