L3-029 还原文件 (30 分)

题目描述：

m个纸片，每张纸片都有若干个特征点

m张纸片以唯一的一种排列方式放在一起，拼成一张完整的，有n个特征点的纸片

任意两个相邻的纸片的交界处的特征值相同

输出排列方式

思路1:

爆搜yyds

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
vector<int>v[1005];
bool vis[1004];
vector<int>ans;
bool p;
void dfs(int st){
    if(st == n){
        p = 1;
        for(int i = 0; i < m; ++i){
            if(i)cout << " ";
            cout << ans[i];
        }
        cout << endl;
        return;
    }
    for(int i = 1; i <= m; ++i){
        if(p || vis[i])continue;
        bool pp = 1;
        for(int j = 0; j < v[i].size(); ++j){
            if(tr[st + j] != v[i][j]){
                pp = 0;
            }
        }
        if(pp){
            ans.push_back(i);
            dfs(st + (int)v[i].size() - 1);
            ans.pop_back();
        }
    }
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> k;
        while (k--) {
            cin >> x;v[i].push_back(x);
        }
    }
    dfs(1);
}


int main(){
    io;
    work();
    return 0;
}

思路2:哈希优化 + 暴力匹配

我们只需要对长度为n的大纸片进行一次哈希处理

再对m个小纸片进行哈希，记录m个纸片哈希后的终值，然后枚举匹配就行

这里枚举的时候有点问题，正着枚举会wa在第二个点，但是倒着枚举就能过

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ull n, m, k, x;
ull tr[MAX];
vector<ull>v[1005];
ull hx[1005];

ull base = 13331;
ull hhash[MAX],mul[MAX];
void init()
{
    mul[0]=1;hhash[0]=0;
    for(int i=1;i<=n;i++)
        mul[i]=mul[i-1]*base;
    for(int i=1;i<=n;i++)
        hhash[i]=hhash[i-1]*base+tr[i];
}
ull getHash(int l,int r){
    return hhash[r]-hhash[l-1]*mul[r-l+1];
}
void haxi(int id){
    for(int i = 0; i < v[id].size(); ++i){
        hx[id] = hx[id] * base + v[id][i];
    }
}
ull ans[1005];
bool vis[1005];
void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    init();
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> k;
        while (k--) {
            cin >> x;
            v[i].push_back(x);
        }
        haxi(i);
    }
    int l = 1;
    for(int i = 1; i <= m; ++i){
        for(int j = m; j >= 1; --j){
            if(vis[j])continue;
            int r = l + (int)v[j].size() - 1;
            if(getHash(l, r) == hx[j]){
                l = r;
                vis[j] = 1;
                ans[i] = j;
                break;
            }
        }
    }
    for(int i = 1; i <= m; ++i){
        if(i != 1)cout << " ";
        cout << ans[i];
    }
}


int main(){
    work();
    return 0;
}