P6937 [ICPC2017 WF]Secret Chamber at Mount Rushmore 题解

· · 题解

宣传博客

简要题意：告诉你可以从哪些字符转化为哪些字符，然后再问你某一个字符串能否转化为另一个字符串。

这里提供两种做法：爆搜和传递闭包。

算法一 爆搜

刚开始看到数据范围第一个念头就是爆搜，于是五分钟打完过了样例就交了。

然后就 \text{RE} 爆系统栈了。

仔细想了一下，应该是出现了环导致死递归了，就比如这种情况：

a -> b
b -> c
c -> a

他们三个形成了一个环，然后就会在这个环里无限递归，所以这样就会 \text{RE}。

要解决也不难，直接开一个 \text{vis} 数组标识当前点是否访问过，然后访问到某个点时就标记为 \text{true}，这样就不会在环里死递归了。

然后记得每次递归之前都要 \text{memset} 一遍。

代码：

#include <iostream>
#include <map>
#include <cstring>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define N 35
#define M 505
#define LENGTH 55
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}

/*

*/

int m, Q, star_cnt, lena, lenb;
char vis[N];
char st[LENGTH], ed[LENGTH];
int head[N];

struct star{int v, nxt;};

struct star e[M<<1];

map<char, int> mp;

inline void star_add(int u, int v){e[++ star_cnt].v=v, e[star_cnt].nxt=head[u], head[u]=star_cnt;}

char dfs(int x, int faer, int target){
    vis[x] = true;
    if (x == target)
        return true;
    for (re i = head[x] ; i ; i = e[i].nxt){
        int v = e[i].v;
        if (v == faer or vis[v] == true)
            continue;
        if (dfs(v, x, target) == true)
            return true;
    }
    return false;
}

inline void work(){
    scanf("%d %d", &m, &Q);

    for (re i = 1 ; i <= 26 ; ++ i)
        mp['a'+i-1] = i;

    char uu, space, vv, enter; uu = getchar();
    for (re i = 1 ; i <= m ; ++ i){
        uu = getchar(), space = getchar(), vv = getchar(), enter = getchar();
        star_add(mp[uu], mp[vv]);
    }

    while (Q --){
        scanf("%s %s", st+1, ed+1);
        lena = strlen(st+1), lenb = strlen(ed+1);

        if (lena != lenb)
            {cout << "no" << '\n'; continue;}

        for (re i = 1 ; i <= lena ; ++ i){
            memset(vis, false, sizeof(vis)); vis[mp[st[i]]] = true;
            if (dfs(mp[st[i]], 0, mp[ed[i]]) == false)
                {cout << "no" << '\n'; goto Continuer;}
        }

        cout << "yes" << '\n';

        Continuer:{}
    }
}
// #define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a, a);
    #endif
    // Fastio_setup();
    work();
    return GMY;
}

算法二 传递闭包

因为字母只有 26 个，我们开数组不会太大，所以每次 \text{memset} 所耗时间几乎可以不计。但是当这题的数据范围更大时，对于每个询问都搜一遍的时间复杂度是 O(Qm) 的，那么就会 \text{T} 掉。

那么我们可以预处理出每个点之间的关系，然后 O(1) 回答询问。

考虑使用传递闭包。传递闭包和 \text{Floyd} 很像，也是枚举中间转移点，通过中间转移点将“关系”转移给另一个点，时间复杂度是 O(n^3) 的。

最后记得初始化 can[i][i] = true，一个元素从自己变成自己当然是可以的。

代码：

#include <iostream>
#include <cctype>
#include <cstring>
#include <map>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define N 35
#define M 505
#define LENGTH 55
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}

/*

*/

int n, m, Q, lena, lenb;
char st[LENGTH], ed[LENGTH];
char can[N][N];

map<char, int> mp;

inline void Floyd(){
    for (re k = 1 ; k <= n ; ++ k)
        for (re i = 1 ; i <= n ; ++ i)
            for (re j = 1 ; j <= n ; ++ j)
                can[i][j] |= (can[i][k] & can[k][j]);
}

inline void work(){
    cin >> m >> Q; n = 26;

    for (re i = 1 ; i <= 26 ; ++ i)
        mp[(char)('a'+i-1)] = i, can[i][i] = true;

    char uu, vv;
    for (re i = 1 ; i <= m ; ++ i){
        cin >> uu >> vv;
        can[mp[uu]][mp[vv]] = true;
    }

    Floyd();

    while (Q --){
        cin >> st+1 >> ed+1; lena = strlen(st+1), lenb = strlen(ed+1);

        if (lena != lenb)
            {puts("no"); goto Continuer;}

        for (re i = 1 ; i <= lena ; ++ i)
            if (can[mp[st[i]]][mp[ed[i]]] == false)
                {puts("no"); goto Continuer;}

        puts("yes");

        Continuer:{}
    }
}
// #define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a, a);
    #endif
    Fastio_setup();
    work();
    return GMY;
}