烟台网站建设电话,军事新闻今天,中国好公司网站建设,wordpress 前台多语言J.Permutation and Primes
构造
题目大意
给定一个正整数 n n n #xff0c;构造一个 n n n 的排列#xff0c;使得每对相邻元素的和或差的绝对值为一奇素数
解题思路
两个数的和或差是奇数#xff0c;那么它们的奇偶性一定是不同的#xff0c;因此所求排列中#…J.Permutation and Primes
构造
题目大意
给定一个正整数 n n n 构造一个 n n n 的排列使得每对相邻元素的和或差的绝对值为一奇素数
解题思路
两个数的和或差是奇数那么它们的奇偶性一定是不同的因此所求排列中奇数和偶数是交错分布的
对于排列的构造首先考虑能不能通过自然排列转化而成//
赛时首先想到奇偶分开后将全体偶数向左或向右循环移动 2 2 2 ~ 3 3 3 位这样可以保证绝大部分位置和左右两边之差为 3 3 3 或 5 5 5 //当时以为要切了结果剩余的数字考虑了两年半还是没有找到符合题意而不失一般性的构造方法
然后考虑分段调整。在上面思想的基础上发现如果元素个数为 8 8 8 个那么全体偶数左移 2 2 2 位和右移 2 2 2 位的结果都为 1 , 6 , 3 , 8 , 5 , 2 , 7 , 4 1,6,3,8,5,2,7,4 1,6,3,8,5,2,7,4 。并且如果下一段长度为 8 8 8 的序列也按照这种规则变换顺序那么 4 4 4 和下一段长度为 8 8 8 的序列的开头 9 9 9 之差为 5 5 5 符合题意从而解决了边界问题
将 n n n 模 8 8 8 取余记 n 8 k r n8kr n8kr 。解决前 r r r 个数的排列后之后每 8 8 8 个数按 1 , 6 , 3 , 8 , 5 , 2 , 7 , 4 1,6,3,8,5,2,7,4 1,6,3,8,5,2,7,4 的顺序变换即可
时间复杂度 O ( n ) O(n) O(n)
参考代码 参考代码为已AC代码主干其中部分功能需读者自行实现 ll rem[8][8]{{},{1},{1,2},{1,2,3},{1,4,3,2},{5,2,1,4,3},{5,2,1,4,3,6},{7,2,5,6,3,4,1}};
ll pl[9]{0,1,6,3,8,5,2,7,4};
void solve(){ll n;cin n;ll rn%8,dn/8;vectorll v;FORLL(i,0,r-1) v.emplace_back(rem[r][i]);FORLL(i,0,d-1){FORLL(j,1,8){v.emplace_back(8*ipl[j]r);}}FORLL(i,0,n-1) cout v[i] Presentation(i,n-1);
}
