最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

C 忽远忽近的距离【2023牛客寒假算法基础集训营3 】

来源:博客园


【资料图】

C忽远忽近的距离

原题链接

题意

1。构造一个长度为n的排列,使得满足对于每个\(a_i\),有\(2\le |a_i-i|\le 3\)

思路1(dfs枚举)

  1. 对于每个\(a_i\)都有
  • 当\(a_i>i\) 时$ i+2\le a_i\le i+3$
  • 当\(a_i
  • 因此\(a_i\)可能的取值为\(i-2,i-3,i+2,i+3\)【偏移量】

代码1

点击查看代码
#include#include#include#include#include#include#includeusing namespace std;#define X first#define Y secondtypedef 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#include#include#include#include#include#includeusing namespace std;#define X first#define Y secondtypedef 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();}

关键词: 点击查看 只需要一个 分别对应