L3-2 还原文件 (30 分)
一份重要文件被撕成两半，其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号，如图 1 所示。然后根据断口的折线形状跟没有切碎的半张纸进行匹配，最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。
图1 纸条编号
图2 还原结果
输入格式：
输入首先在第一行中给出一个正整数 N（1<N≤105），为没有切碎的半张纸上断口折线角点的个数；随后一行给出从左到右 N 个折线角点的高度值（均为不超过 100 的非负整数）。
随后一行给出一个正整数 M（≤100），为碎纸机里的纸条数量。接下去有 M 行，其中第 i 行给出编号为 i（1≤i≤M）的纸条的断口信息，格式为：
K h[1] h[2] ... h[K]
其中 K 是断口折线角点的个数（不超过 104+1），后面是从左到右 K 个折线角点的高度值。为简单起见，这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。
输出格式：
在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔，行首尾不得有多余空格。
题目数据保证存在唯一解。
输入样例：
17 95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80 6 4 68 58 58 80 3 81 68 68 3 95 70 80 3 68 60 80 5 80 72 88 81 81 4 80 97 97 68
结尾无空行
输出样例：
3 6 1 5 2 4
结尾无空行
#include <bits/stdc++.h> using namespace std; int n, m, k, t, flag1, flag2; int h[100001], vis[101]; vector<int> Ans, frag[101]; void DFS (int p) { if ((int)Ans.size() == m) { flag1 = 1; for (int i = 0; i < m; i++) { if (i) cout << ' '; cout << Ans[i]; } } if (flag1) return; for (int i = 1; i <= m; i++) { if (vis[i]) continue; flag2= 0; for (int j = 0; j < (int)frag[i].size(); j++) { if (frag[i][j] != h[p + j]) { flag2 = 1; break; } } if (flag2) continue; Ans.push_back(i); vis[i] = 1; DFS(p + (int)frag[i].size() - 1); vis[i] = 0; Ans.pop_back(); } }; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> h[i]; cin >> m; for (int i = 1; i<= m; i++) { cin >> k; for (int j = 0; j < k; j++) { cin >> t; frag[i].push_back(t); } } DFS(0); return 0; }
#include<bits/stdc++.h> using namespace std; typedef long long ULL; const int N=100010,M=110,P=131; int n,m; ULL h[N],p[N]; int width[M]; ULL g[M]; bool st[M]; int ans[M]; ULL get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } bool dfs(int u,int end){ if(end==n)return 1; for(int i=1;i<=m;i++) if(!st[i]&&g[i]==get(end,end+width[i]-1)){ st[i]=1; ans[u]=i; if(dfs(u+1,end+width[i]-1))return 1; else return 0; } } int main(){ scanf("%d",&n); p[0]=1; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); p[i]=p[i-1]*P; h[i]=h[i-1]*P+x+1; } scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d",&width[i]); for(int j=0;j<width[i];j++){ int x; scanf("%d",&x); g[i]=g[i]*P+x+1; } } dfs(1,1); for(int i=1;i<=m;i++){ printf("%d",ans[i]); if(i!=m)printf(" "); } return 0; }
#include <iostream> #include <algorithm> using namespace std; struct node{ string s; int num; int t; }; bool cmp(node a, node b){ return a.t < b.t; } bool cmp1(node a, node b){ return a.num > b.num; } int main(){ int n; cin>>n; getchar(); string str; getline(cin, str); int m; cin>>m,getchar(); node a[m]; for(int i=0;i<m;i++){ int k; cin>>k,getchar(); string t; getline(cin,t),a[i].num=i+1,a[i].s=t; } sort(a,a+m,cmp1); for(int i=0;i<m;i++){ int x=str.find(a[i].s); int len=a[i].s.length(); a[i].t=x; int num=0; for(int j=x;;j++){ if(str[j]==' '){ str[j]='*',num++; } if(num==2)break; } } sort(a,a+m,cmp); for(int i=0;i<m;i++){ if(i)cout<<" "; cout<<a[i].num; } return 0; }
