专栏文章

题解：AT_abc209_e [ABC209E] Shiritori

zzhaomumu1218
AT_abc209_e题解参与者 10已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@mipghyoc
此快照首次捕获于
2025/12/03 11:37
3 个月前
此快照最后确认于
2025/12/03 11:37
3 个月前
查看原文
提供一个很抽象的思路。

题意

两个人玩接龙游戏，后一个人说的单词的前 33 个字符必须和前一个人说的单词的后 33 个字符一样。如果先手先说第 ii 个单词，问谁会赢。

思路

注：下文中先手指目前选择的人。

第一版（非正解）

从第 ii 个单词的前 33 个字母向后 33 个字母连边，出度为零的点为先手必败。
  1. 如果当前的点走一步能到下一步的先手必败点，说明这个点是先手必胜点。
  2. 如果当前的点访问第 22 次，说明这个点是平局点。
  3. 如果当前的点无法走一步达到下一步的先手必败点，且能走一步到平局点，说明这个点是平局点。
  4. 如果当前的点无法走一步达到下一步的先手必败点，且能无法走一步到平局点，说明这个点是当前先手必败点。
    这就结束了？

hack

不！错误数据：
CPP
5
fffccc
aaabbb
bbbccc
cccaaa
aaaeee
图是这样的

aaa 这个点是先手必败点，但我的思路会因为输入顺序先去点 bbb，然后到点 ccc。由于点 ccc 访问过，点 bbb 变成了平局点，但很明显祂不是平局点。

第二版（正解）

仔细分析，发现错误的原因是 dfs 顺序不对，应该先访问未访问的点，一个点被访问第 22 次才是平局点，其他同第一版。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define LOCAL
namespace lsy{
    namespace IO{
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr{
            template<typename type>
            inline type read(type &x){
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x){
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace lsy::IO::usr;
const int maxn=200010,maxd=200000;
string s[maxn];
int ans[maxd];
int flag[maxd];
int jh(char z){
    if(z>='a') return z-'a'+27;
    return z-'A';
}
int js(string ss){
    return jh(ss[0])*53*53+jh(ss[1])*53+jh(ss[2]);
}
vector<int>e[maxd];
map<pair<int,int>,bool>mp;
int dfs(int u){ //1先手必胜2后手必胜3平局 现在是先手选
    if(e[u].size()==0) return 2;
    if(ans[u]) return ans[u];
    if(flag[u]==2) return ans[u]=3;
    flag[u]++;
    int re=2;
    for(int v:e[u]){
        if(flag[v]) continue;
        int z=dfs(v);
        if(z==3) re=3;
        if(z==2) return ans[u]=1;
    }
    for(int v:e[u]){
        if(!flag[v]) continue;
        int z=dfs(v);
        if(z==3) re=3;
        if(z==2) return ans[u]=1;
    }
    ans[u]=re;
    return re;
}
signed main(){
    int n;
    read(n);
    for(int i=1;i<=n;i++){
        read(s[i]);
        string x="";
        x+=s[i][0];
        x+=s[i][1];
        x+=s[i][2];
        string xx="";
        xx+=s[i][s[i].size()-3];
        xx+=s[i][s[i].size()-2];
        xx+=s[i][s[i].size()-1];
        int sx=js(x),sxx=js(xx);
        if(mp[{sx,sxx}]) continue;
        mp[{sx,sxx}]=1;
        e[sx].push_back(sxx);
    }
    for(int i=1;i<=n;i++){
        string xx="";
        xx+=s[i][s[i].size()-3];
        xx+=s[i][s[i].size()-2];
        xx+=s[i][s[i].size()-1];
        int z=js(xx);
        int ans=dfs(z);
        if(ans==2) write("Takahashi\n");
        if(ans==1) write("Aoki\n");
        if(ans==3) write("Draw\n");
    }
    return 0;
}
/*
5
fffccc
aaabbb
bbbccc
cccaaa
aaaeee
*/

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...