2021天梯L3-2 还原文件

题目大意

给你一个数组，然后给你其中的一些片段，问能还原回去的片段序列。

解题思路

比赛的时候完全没有思路。

比完告诉我是爆搜。

完全没想到可以直接暴力匹配，这数据这么水的么。

思路就是直接在数组上搜，其他的就是正常的dfs了。

只要想到是在数组上搜索，这题就不难了。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
int num[N], n, m, vis[N], f = 0;
vector<int> v[110], ans;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int check(int p, int t) {
	if (p + v[t].size() - 1 > n) return 0;
	int cnt = 0;
	rep(i, p, p + v[t].size() - 1) {
		if (num[i] != v[t][cnt++])	return 0;
	}
	return 1;
}

void dfs(int p) {
	if (p == n && !f) {
		rep(i, 0, ans.size() - 1) {
			cout << ans[i];
			if (i != ans.size() - 1) cout << ' ';
		}
	}
	rep(i, 1, m) {
 		if (!vis[i] && check(p, i)) {
			vis[i] = 1;
			ans.push_back(i);
			dfs(p + v[i].size() - 1);
			vis[i] = 0;
			ans.pop_back();
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	cin >> n;
	rep(i, 1, n)	cin >> num[i];
	cin >> m;
	rep(i, 1, m) {
		int t; cin >> t;
		rep(j, 1, t) {
			int x; cin >> x;
			v[i].push_back(x);
		}
	}
	dfs(1);
	return 0;
}