题目描述

题目大意

给定一个长度为 n n 的序列，每次可以把中间的数移到队首或者队尾，问移动的最小次数

解题思路

这题的核心在于判重

因为数据很小，所以我们很容易可以想到dfsdfs/ bfs b f s 的方法，对于判重可以使用九进制数或者 HASH H A S H ，使用 HASH H A S H 的过程中可以把每个数都减去159，这样就可以大大降低运算结果的大小，从而减轻 HASH H A S H 的负担

70分代码

#include<cstdio> #define p 1000003 #define hash(x) x%p #define min(a,b) a<b?a:b #define temp1 k=a[mid];for(int i=mid;i>1;i--) a[i]=a[i-1];a[1]=k #define temp2 k=a[mid];for(int i=mid;i<n;i++) a[i]=a[i+1];a[n]=k using namespace std;int a[10],f[p],n,mid,ans=2147483647;long long h[p]; int num(int a[]) { long long t=0; for(int i=1;i<=n;i++) t=(t<<3)+(t<<1)+a[i]; return t; } int find(long long x) { int y=hash(x); while(h[y]&&h[y]!=x) y=hash(++y); return y; } bool init(int a[],int x) { int t=num(a),y=find(t); return h[y]==t&&x>=f[y]; } void push(int a[],int x) { int t=num(a),y=find(t); h[y]=t;f[y]=min(x,f[y]); return; } bool check() { for(int i=1;i<n;i++) if(a[i]>a[i+1]) return false; return true; } void dfs(int dep) { if(dep>=ans||init(a,dep)) return; if(check()) {ans=min(ans,dep);return;} int k=0; push(a,dep); int b[10]={a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]}; temp1; dfs(dep+1);for(int i=1;i<=n;i++) a[i]=b[i]; temp2; dfs(dep+1);for(int i=1;i<=n;i++) a[i]=b[i]; } int main() { scanf("%d",&n);mid=(n+1)>>1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=159; dfs(0); if(ans==2147483647) printf("No Answer"); else printf("%d",ans); }

100分代码（map库，378ms）

#include<map> #include<queue> #include<cstdio> #define min(a,b) a<b?a:b #define temp1 k=a[mid];for(int i=mid;i>1;i--) a[i]=a[i-1];a[1]=k #define temp2 k=a[mid];for(int i=mid;i<n;i++) a[i]=a[i+1];a[n]=k using namespace std;int a[10],n,mid,ans=2147483647,head,tail,q[1000001][10],bs[1000001]; map<long long,bool>m; long long num(int a[]) { long long t=0; for(int i=1;i<=n;i++) t=(t<<3)+(t<<1)+a[i]; return t; } bool init(int a[]) { long long t=num(a); return !m[t]; } void push(int a[]) { long long t=num(a);m[t]=true; tail=tail%1000001+1; for(int i=1;i<=n;i++) q[tail][i]=a[i]; return; } bool check() { for(int i=1;i<n;i++) if(a[i]>a[i+1]) return false; return true; } void bfs() { push(a);int k; while(head!=tail) { head=head%1000001+1; for(int i=1;i<=n;i++) a[i]=q[head][i]; temp1; if(init(a)) {push(a);bs[tail]=bs[head]+1;} if(check()) {ans=bs[tail];return;} for(int i=1;i<=n;i++) a[i]=q[head][i]; temp2; if(init(a)) {push(a);bs[tail]=bs[head]+1;} if(check()) {ans=bs[tail];return;} } return; } int main() { scanf("%d",&n);mid=(n+1)>>1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=159; bfs(); if(ans==2147483647) printf("No Answer"); else printf("%d",ans); }

100分代码（哈希，62ms）

#include<queue> #include<cstdio> #define p 1000003 #define hash(x) x%p #define min(a,b) a<b?a:b #define temp1 k=a[mid];for(int i=mid;i>1;i--) a[i]=a[i-1];a[1]=k #define temp2 k=a[mid];for(int i=mid;i<n;i++) a[i]=a[i+1];a[n]=k using namespace std;int a[10],n,mid,ans=2147483647,head,tail,q[1000001][10],bs[1000001];long long h[p]; long long num(int a[]) { long long t=0; for(int i=1;i<=n;i++) t=(t<<3)+(t<<1)+a[i]; return t; } int find(long long x) { int y=hash(x); while(h[y]&&h[y]!=x) y=hash(++y); return y; } bool init(int a[]) { long long t=num(a),y=find(t); return h[y]==t; } void push(int a[]) { long long t=num(a),y=find(t); h[y]=t; tail=tail00001+1; for(int i=1;i<=n;i++) q[tail][i]=a[i]; return; } bool check() { for(int i=1;i<n;i++) if(a[i]>a[i+1]) return false; return true; } void bfs() { push(a);int k; while(head!=tail) { head=head00001+1; for(int i=1;i<=n;i++) a[i]=q[head][i]; temp1; if(!init(a)) {push(a);bs[tail]=bs[head]+1;} if(check()) {ans=bs[tail];return;} for(int i=1;i<=n;i++) a[i]=q[head][i]; temp2; if(!init(a)) {push(a);bs[tail]=bs[head]+1;} if(check()) {ans=bs[tail];return;} } return; } int main() { scanf("%d",&n);mid=(n+1)>>1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=159; bfs(); if(ans==2147483647) printf("No Answer"); else printf("%d",ans); }