题解#小白月赛-交换#

tag:

cf分段1800+
字典树，哈希hash，枚举

题意：

给定连续操作序列，对于操作序列l，r，使其实现交换当前位置上的数字
给定一堆未完成的排列，利用连续操作序列使其变成顺序递增排列

题解：

这题最先通过连续操作序列这一点就能想到 $o (n^{2})$ 的枚举状态获得对应操作结果。

那么如果我们可以记录下所有操作对应的结果，然后通过逆向操作就能知道当前序列最后操作的结果是什么情况。

比如说我们操作 3 2 1，我们的一个连续操作序列可以使得原串 1 2 3 变成 3 2 1 ，那么他就可以使得原串为 3 2 1的序列变成 1 2 3

然后就是查询的问题，根据某沙老师所言，最初他并没有想卡掉map的查询，而是后面某人想到了利用字典树实现查询加速的方案，才使得这题变得如此妖孽。

字典树的查询时间跟串长有关，这题的串长只有10，所以时间复杂度相当低。而map的log跟字符串数量有关，至少是1e6起步，所以会很慢。（也就是俗称的卡常）

当然这里也给一些别的我看到的思路，比如说康托展开加速，或者玄学hash并放在数组里o1查询，这些都是一些比较可行的办法（但并不常见）

代码

#include<bits/stdc++.h>
using namespace std;

int n, m;
int x[20];

pair<int, int>rm[2040];
#define ll long long
vector<array<int,10>> nex(1);
#include<bits/stdc++.h>
using namespace std;
struct trie {
    
    int ve[20000004];
    int cnt = 0;
    //s是字符串，l是s的长度
    void insert(string s, int l,int num) {
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - '0';
            if (!nex[p][c]) nex.push_back({}),nex[p][c]=nex.size()-1;
            p = nex[p][c];
        }
        //代表他是否出现过
        if(ve[p])
       ve[p] = min(num,ve[p]);
        else ve[p] = num;
    }
    int find(string s, int l) {
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - '0';
            if (!nex[p][c])return 0;
            p = nex[p][c];
        }
        return ve[p];
    }
}tr;

int main() {
    int n, m;
    ios::sync_with_stdio(0);
    cin >> n >> m;
    int a, b;
    map<string, int>mp;
    for (int i = 1; i <= n; i++) {
        cin >> rm[i].first >> rm[i].second;
    }
    for (int l = 1; l <= n; l++) {
        string ans = "0123456789";
        for (int j = l; j <= n; j++) {
            swap(ans[rm[j].first - 1], ans[rm[j].second - 1]);
            string tmp;
            for (int k = 0; k < 10; k++) {
                tmp += ans[k];
                tr.insert(tmp,tmp.size(),j - l + 1);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> n;
        string pp;
        int bb[10] = {};
        int f = 0;
        for (int j = 1; j <= n; j++) {
            int tt;
            cin >> tt;
            if (tt != j)f = 1;
            bb[tt] = j - 1;
        }
        if (f == 0) {

            cout << "0\n";
            continue;
        }
        for (int j = 1; j <= n; j++) {
            pp += char(bb[j] + '0');
        }

        if (tr.find(pp,pp.size()) == 0)cout << -1 << "\n";
        else cout << tr.find(pp,pp.size()) << "\n";
    }
}