C 忽远忽近的距离
题意
1。构造一个长度为n的排列，使得满足对于每个\(a_i\)，有\(2\le |a_i-i|\le 3\)
思路1（dfs枚举）
- 对于每个\(a_i\)都有
- 当\(a_i>i\) 时$ i+2\le a_i\le i+3$
- 当\(a_i<i\) 时$ i-3\le a_i\le i-2$
- 因此\(a_i\)可能的取值为\(i-2,i-3,i+2,i+3\)【偏移量】
代码1
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef long long LL;
const char nl = '\n';
int n;
const int N = 1e5 + 10;
int a[N],d[N];
int dx[]={-2,-3,2,3}; //偏移量
bool f = 0;
void dfs(int x){
if(x > n && !f){ //如果第一次枚举到n+1位
for(int i = 1; i <= n; i ++ )cout << a[i] << " ";
cout << nl;
f = 1;
return;
}
for(int i = 0; i <= 3; i ++ ){
if(f)break; //只需要一个答案
int u = x + dx[i];
if(u <= 0 || u > n || d[u])continue;
d[u] = 1; //每个数只能用一次
a[x] = u;
dfs(x+1);
d[u] = 0;
//a[x] = 0; //后面会被覆盖掉
}
}
void solve(){
cin >> n;
dfs(1);
if(!f)cout << -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
思路2（模块化构造）
我们从样例可以发现，\([3,4,1,2]\)是一组合法解，那么可以以此构造出所有n=4k形式的情况：\([3,4,1,2,7,8,5,6]\)等。
之后我们可以尝试构造\(n=5\)和\(n=6\)的情况，发现有\([4,5,1,2,3]\)和\([4,5,6,1,2,3]\)，那么可以构造出\(n=4k+5、n=4k+6、n=4k+5+6\)的情况，以上分别对应n模4等于1、2、3的情况，加上之前的n=4k，那么就覆盖了几乎所有正整数（需要特判n=7和n<4时是无解的）。
例如\(n=13\)，我们发现\(13=4*2+5\)，那么可以构造成：\([3,4,1,2,7,8,5,6,12,13,9,10,11]\)，即\(13=4+4+5\)的情况。
代码2
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
int n,m;
int d4[]={3,4,1,2},d5[]={4,5,1,2,3},d6[]={4,5,6,1,2,3};
void solve(){
cin >> n;
int t = n % 4;
if(n < 4 || n == 7)cout << -1;
else if(t == 0){
for(int i = 0; i < n / 4; i ++)
for(int j = 0; j < 4; j ++)
cout << d4[j] + 4 * i << " ";
}
else if(t == 1){
for(int i = 0; i < n / 4 -1; i ++)
for(int j = 0; j < 4; j ++)
cout << d4[j] + 4 * i << " ";
for(int j = 0; j < 5; j ++)cout << d5[j] + n - 5 << " ";
}
else if(t == 2){
for(int i = 0; i < n / 4 -1; i ++)
for(int j = 0; j < 4; j ++)
cout << d4[j] + 4 * i << " ";
for(int j = 0; j < 6; j ++)cout << d6[j] + n - 6 << " ";
}
else{
for(int i = 0; i < n / 4 -2; i ++)
for(int j = 0; j < 4; j ++)
cout << d4[j] + 4 * i << " ";
for(int j = 0; j < 5; j ++)cout << d5[j] + n - 5 - 6 << " ";
for(int j = 0; j < 6; j ++)cout << d6[j] + n - 6 << " ";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}