小红的排列构造时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿了一个长度为n nn的数组a aa她希望你构造两个排列p pp和q qq满足对于i ∈ [ 1 , n ] i \in [1, n]i∈[1,n]a i a_iai为p i p_ipi或q i q_iqi二选一。你能帮帮她吗定义排列是一个长度为n nn的数组其中1 11到n nn每个元素恰好出现1 11次。输入描述第一行输入一个正整数n nn代表两个数组的长度。第二行输入n nn个正整数a i a_iai。数据范围1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1051 ≤ a i ≤ n 1 \le a_i \le n1≤ai≤n。输出描述如果无解请输出− 1 -1−1。否则第一行输出n nn个正整数p i p_ipi第二行输出n nn个正整数q i q_iqi代表小红构造的两个排列。有多解时输出任意即可。示例 1输入3 2 3 2输出2 3 1 1 3 2示例 2输入4 1 1 1 1输出-1解题思路本题是排列构造问题要求根据给定的数组a aa构造两个1 ∼ n 1\sim n1∼n的排列p pp和q qq使得对于每个位置i iip i p_ipi或q i q_iqi中至少有一个等于a i a_iai。需要判断是否有解并输出任意一组解。1. 问题等价转化对于每个a i a_iai必须满足p i a i p_i a_ipiai或q i a i q_i a_iqiai或两者都等于。若某个值x xx在数组a aa中出现次数超过2 22次则不可能构造成功因为每个值在两个排列中总共最多出现两次每个排列各一次。因此出现次数c n t [ x ] 2 cnt[x] 2cnt[x]2时无解。我们只需关注每个值出现0 , 1 , 2 0,1,20,1,2次的情况并利用排列的性质每个数恰好使用一次进行填充。2. 构造策略设pos[x]记录值x xx在数组a aa中的所有下标。出现2 22次的值x xx假设它出现在位置i ii和j jj。我们可以令p i x p_i xpixq j x q_j xqjx这样两个位置都满足了条件。此时在位置i ii的q i q_iqi还未确定位置j jj的p j p_jpj还未确定它们将成为“自由槽”需要填入那些在a aa中出现0 00次的值。出现1 11次的值x xx它只出现在位置i ii我们可以直接令p i q i x p_i q_i xpiqix这样该位置一定满足条件且不占用其他位置。出现0 00次的值y yy这些值没有直接出现在a aa中但它们必须分别出现在p pp和q qq的各一个位置。我们可以将它们填入上述“自由槽”中。每个出现2 22次的值会制造两个自由槽一个在p pp的某个位置一个在q qq的某个位置而出现0 00次的值也需要在两个排列中各出现一次因此二者的数量是匹配的每两个出现2 22次的值对应两个出现0 00次的值因为总出现次数守恒。通过将零数值依次填入自由槽即可保证每个数字在每个排列中恰好出现一次。3. 算法步骤读入n nn和数组a aa统计每个值x xx的出现次数cnt[x]和位置列表pos[x]。若存在cnt[x] 2直接输出-1。初始化两个答案数组p和q初始为0 00。处理出现2 22次的值对于每个x xx若cnt[x] 2设其两个位置为i和j。令p[i] xq[j] x。记录自由槽free_p.push_back(j)表示p[j]待填free_q.push_back(i)表示q[i]待填。处理出现1 11次的值对于每个x xx若cnt[x] 1设其唯一位置为i令p[i] q[i] x。收集出现0 00次的值到zeros数组。将zeros中的值依次填入自由槽第i d x idxidx个零数值y填入p[free_p[idx]] y和q[free_q[idx]] y。检查是否有任何位置仍为0 00理论上不会发生若有则输出-1否则输出p和q。4. 正确性说明每个位置i ii都满足p i a i p_i a_ipiai或q i a i q_i a_iqiai出现2 22次的值通过分别放在p pp和q qq的不同位置保证出现1 11次的值直接两边都放出现0 00次的值不影响条件因为原位置的a i a_iai已经由其他值满足。排列性质每个x ∈ [ 1 , n ] x\in[1,n]x∈[1,n]在p pp中恰好出现一次在q qq中恰好出现一次。出现1 11次的值两个排列都有出现2 22次的值分别放在一个排列的对应位置和另一个排列的自由槽出现0 00次的值通过自由槽填入两个排列各一次。数量守恒保证刚好填满。5. 复杂度分析时间复杂度O ( n ) O(n)O(n)只需线性扫描数组、统计次数、填充答案。空间复杂度O ( n ) O(n)O(n)存储位置列表、计数数组及答案数组。总结通过统计每个数值的出现次数利用“出现两次的值制造自由槽出现零次的值填充自由槽”的方式在线性时间内构造出满足条件的两个排列。方法巧妙且高效适用于10 5 10^5105规模的数据。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intn;cinn;vectorinta(n);vectorvectorintpos(n1);vectorintcnt(n1,0);for(inti0;in;i){cina[i];cnt[a[i]];pos[a[i]].push_back(i);}for(intx1;xn;x){if(cnt[x]2){cout-1endl;return0;}}vectorintp(n,0),q(n,0);vectorintfree_p,free_q;// 储存自由槽位置类型为p或qvectorintzeros;// 出现0次的数字// 处理出现两次的数字for(intx1;xn;x){if(cnt[x]2){intipos[x][0],jpos[x][1];// 将x放在p[i]和q[j]p[i]x;q[j]x;// 自由槽q[i] 和 p[j]free_p.push_back(j);// p槽位置free_q.push_back(i);// q槽位置}}// 处理出现一次的数字for(intx1;xn;x){if(cnt[x]1){intipos[x][0];p[i]q[i]x;}}// 收集零数for(intx1;xn;x){if(cnt[x]0){zeros.push_back(x);}}// 将零数分配到自由槽中for(intidx0;idx(int)zeros.size();idx){intyzeros[idx];intpos_pfree_p[idx];intpos_qfree_q[idx];p[pos_p]y;q[pos_q]y;}// 检查是否所有位置都已填充for(inti0;in;i){if(p[i]0||q[i]0){cout-1endl;return0;}}// 输出p和qfor(inti0;in;i){coutp[i](in-1?\n: );}for(inti0;in;i){coutq[i](in-1?\n: );}return0;}
小红的排列构造时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿了一个长度为n nn的数组a aa她希望你构造两个排列p pp和q qq满足对于i ∈ [ 1 , n ] i \in [1, n]i∈[1,n]a i a_iai为p i p_ipi或q i q_iqi二选一。你能帮帮她吗定义排列是一个长度为n nn的数组其中1 11到n nn每个元素恰好出现1 11次。输入描述第一行输入一个正整数n nn代表两个数组的长度。第二行输入n nn个正整数a i a_iai。数据范围1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1051 ≤ a i ≤ n 1 \le a_i \le n1≤ai≤n。输出描述如果无解请输出− 1 -1−1。否则第一行输出n nn个正整数p i p_ipi第二行输出n nn个正整数q i q_iqi代表小红构造的两个排列。有多解时输出任意即可。示例 1输入3 2 3 2输出2 3 1 1 3 2示例 2输入4 1 1 1 1输出-1解题思路本题是排列构造问题要求根据给定的数组a aa构造两个1 ∼ n 1\sim n1∼n的排列p pp和q qq使得对于每个位置i iip i p_ipi或q i q_iqi中至少有一个等于a i a_iai。需要判断是否有解并输出任意一组解。1. 问题等价转化对于每个a i a_iai必须满足p i a i p_i a_ipiai或q i a i q_i a_iqiai或两者都等于。若某个值x xx在数组a aa中出现次数超过2 22次则不可能构造成功因为每个值在两个排列中总共最多出现两次每个排列各一次。因此出现次数c n t [ x ] 2 cnt[x] 2cnt[x]2时无解。我们只需关注每个值出现0 , 1 , 2 0,1,20,1,2次的情况并利用排列的性质每个数恰好使用一次进行填充。2. 构造策略设pos[x]记录值x xx在数组a aa中的所有下标。出现2 22次的值x xx假设它出现在位置i ii和j jj。我们可以令p i x p_i xpixq j x q_j xqjx这样两个位置都满足了条件。此时在位置i ii的q i q_iqi还未确定位置j jj的p j p_jpj还未确定它们将成为“自由槽”需要填入那些在a aa中出现0 00次的值。出现1 11次的值x xx它只出现在位置i ii我们可以直接令p i q i x p_i q_i xpiqix这样该位置一定满足条件且不占用其他位置。出现0 00次的值y yy这些值没有直接出现在a aa中但它们必须分别出现在p pp和q qq的各一个位置。我们可以将它们填入上述“自由槽”中。每个出现2 22次的值会制造两个自由槽一个在p pp的某个位置一个在q qq的某个位置而出现0 00次的值也需要在两个排列中各出现一次因此二者的数量是匹配的每两个出现2 22次的值对应两个出现0 00次的值因为总出现次数守恒。通过将零数值依次填入自由槽即可保证每个数字在每个排列中恰好出现一次。3. 算法步骤读入n nn和数组a aa统计每个值x xx的出现次数cnt[x]和位置列表pos[x]。若存在cnt[x] 2直接输出-1。初始化两个答案数组p和q初始为0 00。处理出现2 22次的值对于每个x xx若cnt[x] 2设其两个位置为i和j。令p[i] xq[j] x。记录自由槽free_p.push_back(j)表示p[j]待填free_q.push_back(i)表示q[i]待填。处理出现1 11次的值对于每个x xx若cnt[x] 1设其唯一位置为i令p[i] q[i] x。收集出现0 00次的值到zeros数组。将zeros中的值依次填入自由槽第i d x idxidx个零数值y填入p[free_p[idx]] y和q[free_q[idx]] y。检查是否有任何位置仍为0 00理论上不会发生若有则输出-1否则输出p和q。4. 正确性说明每个位置i ii都满足p i a i p_i a_ipiai或q i a i q_i a_iqiai出现2 22次的值通过分别放在p pp和q qq的不同位置保证出现1 11次的值直接两边都放出现0 00次的值不影响条件因为原位置的a i a_iai已经由其他值满足。排列性质每个x ∈ [ 1 , n ] x\in[1,n]x∈[1,n]在p pp中恰好出现一次在q qq中恰好出现一次。出现1 11次的值两个排列都有出现2 22次的值分别放在一个排列的对应位置和另一个排列的自由槽出现0 00次的值通过自由槽填入两个排列各一次。数量守恒保证刚好填满。5. 复杂度分析时间复杂度O ( n ) O(n)O(n)只需线性扫描数组、统计次数、填充答案。空间复杂度O ( n ) O(n)O(n)存储位置列表、计数数组及答案数组。总结通过统计每个数值的出现次数利用“出现两次的值制造自由槽出现零次的值填充自由槽”的方式在线性时间内构造出满足条件的两个排列。方法巧妙且高效适用于10 5 10^5105规模的数据。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intn;cinn;vectorinta(n);vectorvectorintpos(n1);vectorintcnt(n1,0);for(inti0;in;i){cina[i];cnt[a[i]];pos[a[i]].push_back(i);}for(intx1;xn;x){if(cnt[x]2){cout-1endl;return0;}}vectorintp(n,0),q(n,0);vectorintfree_p,free_q;// 储存自由槽位置类型为p或qvectorintzeros;// 出现0次的数字// 处理出现两次的数字for(intx1;xn;x){if(cnt[x]2){intipos[x][0],jpos[x][1];// 将x放在p[i]和q[j]p[i]x;q[j]x;// 自由槽q[i] 和 p[j]free_p.push_back(j);// p槽位置free_q.push_back(i);// q槽位置}}// 处理出现一次的数字for(intx1;xn;x){if(cnt[x]1){intipos[x][0];p[i]q[i]x;}}// 收集零数for(intx1;xn;x){if(cnt[x]0){zeros.push_back(x);}}// 将零数分配到自由槽中for(intidx0;idx(int)zeros.size();idx){intyzeros[idx];intpos_pfree_p[idx];intpos_qfree_q[idx];p[pos_p]y;q[pos_q]y;}// 检查是否所有位置都已填充for(inti0;in;i){if(p[i]0||q[i]0){cout-1endl;return0;}}// 输出p和qfor(inti0;in;i){coutp[i](in-1?\n: );}for(inti0;in;i){coutq[i](in-1?\n: );}return0;}
