E2. Unforgivable Curse (hard version)

Problem - E2 - Codeforces

问题描述：给两个字符串和一个k。如果下标i，j满足|i - j| == k or |i - j| == k + 1，则可以swap(s[i], s[j])，s为两个字符串之一。

思路：如果 可行，那么一定也是可行的。发现对于一个连通块而言，这一个连通块内的字符总是可以进行交换。如果对于一个连通块来说，两个字符串在这个连通块中的字符种类对应的个数是相同的，那么总是可以经过若干操作，使这两个字符串在连通块中对应的下标的元素相等。

因此dfs找连通块，之后判断这个连通块中字符种类及其对应的个数是否相等，相等则可能相同，不等则一定不相等。

AC代码：

const int N = 2e5 + 21;
char s1[N], s2[N];
int fa[N]; // 并查集
// vis数组是判断连通块是否遍历过，st是判断这个点是否在找连通块中被遍历过
bool vis[N], st[N];
int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]); }
void inpfile();
void solve() {
    int n,k; cin>>n>>k;
    // 初始化
    for(int i = 1;  i <= n; ++i) fa[i] = i, vis[i] = 0, st[i] = 0;
    cin>>s1 + 1>> s2 + 1;
    bool fg = true;
    map<int,int> mii;
    // 找连通块
    auto dfs = [&] (auto &&dfs, int u) -> void {
        if(st[u]) return ;
        st[u] = 1;
        int len = 0;
        for(int j = 0; j < 4; ++j) {
            len = (k + j%2) * (j < 2 ? 1 : -1);
            int pos = u + len;
            // 上面操作是得到 位置 
            // pos - k  |  pos + k
            // pos + k + 1 |  pos - (k + 1)

            // 位置不合法
            if(pos < 1 || pos > n) continue;

            // 找父亲
            int pfa = find(pos), ifa = find(u);
            if(pfa != ifa) {
                // 注意一定是将 pos的指向u的。因为后面遍历时，是根据第一个的位置来判断的
                fa[pfa] = ifa;
                /**
                 * 1 -- > 2 --> 3 -- > 4
                 * 将2的父亲指向1的父亲，这样在后面判断是否遍历过就行。
                 * 
                 * 由于我用的vis数组判断，如果用的是用map或者什么的，将每个点都进行个判断也行
                */

               // 判断字符种类及其个数是否相同
               // 这里用 一个字符串进行++操作，一个字符串进行--操作，等价于次
                mii[s1[pos]] ++;
                mii[s2[pos]] --;
                dfs(dfs, pos);
            }
        }
    };
    for(int i = 1; i <= n; ++i) {
        // 由于我是用这个父亲值进行判断的
        if(vis[find(i)]) continue;
        vis[find(i)] = 1;
        // 每次要清空
        mii.clear();
        
        // 第一个i，没有对应上，要手动设置上
        mii[s1[i]]++;
        mii[s2[i]]--;
        dfs(dfs, i);
        
        // 判断字符种类及其对应个数是否相同
        for(auto t: mii) {
            if(t.vs != 0) {
                fg = false;
            }
        }
    }
    puts(fg ? "YES" : "NO");

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71