2026江南程序设计竞赛联盟暑期多校第一场_补题题解
A 构造的芙莉莲题目分析题目给了我们两个长度均为 n 的排列数组一个是原数组 a一个是目标数组 b要求我们利用异或运算在不超过 3*n 次的操作下判断是否可以将 a 数组转化为 b 数组。可以则输出Yes并输出操作过程反之则输出No。解题思路我们知道数组ab均为长度为n的排列即数组元素相同那么我们要想将a转化为b就只通过至多n-1次的数据交换就可以实现而恰好题目要求的异或操作能够实现这样一个目标交换x、y的值只需通过3次异或操作x x ^y, y y ^ x, x x ^ y这样一来要想将每个元素归位到相应位置只需要至多 3 * (n - 1) 次将不会超过题目要求的 3 * n 次即一定能构造出这样一个操作序列使得数组a 转化为数组b代码实现#includebits/stdc.husingnamespacestd;inta[100010];//原数组intb[100010];//目标数组intpos[100010];//记录数组a中每个元素目前所在的位置structfunc{intans1,ans2;}s[300010];//统计答案voidsolve(){intn,ans0;cinn;for(inti1;in;i){cina[i];pos[a[i]]i;}for(inti1;in;i)cinb[i];coutYesendl;for(inti1;in;i){if(a[i]!b[i]){intpos1pos[a[i]],pos2pos[b[i]];s[ans1].ans1pos1;s[ans1].ans2pos2;//记录答案s[ans2].ans1pos2;s[ans2].ans2pos1;s[ans3].ans1pos1;s[ans3].ans2pos2;swap(a[pos1],a[pos2]);//置换元素pos[a[pos1]]pos1;//更新元素位置pos[a[pos2]]pos2;ans3;}}coutansendl;for(inti1;ians;i){couts[i].ans1 s[i].ans2endl;}}intmain(){solve();}I 实验报告缝合题目分析在每组的测试数据中我们有 n 份报告 我们要做的是每次合并至少2份至多k份报告使之最终合并为1份报告求出我们合并的最小代价解题思路当我们看到求一串数的最小代价时要能想到是哈夫曼树而本题说我们一次至多可选择k份即 k叉哈夫曼树。那么此时我们就需要用到优先队列(priority_queue)保证我们每次取出的数是此时数组中的最小的数且合并后的数能够归位到相应的位置。因为我们每次选取 k 份报告合并为 1 份报告即每次合并净减 k-1 份报告而我们的总数量是由 n 变为 1即总共减少 n-1 份要想保证我们每次尽量合并 k 份报告那么如果 re (n - 1) % (k - 1) 不为 0 即当总数不能保证每次都合并k份时我们在第一次就要合并 re 1 份报告使之第一次能净减 re 次保证后续都能合并k份否则代价将偏大代码实现#includebits/stdc.h#definelllonglongusingnamespacestd;voidsolve(){intn,k;cinnk;ll ans0;priority_queuell,vectorll,greaterpq;for(ll i1,x;in;i){cinx;pq.push(x);}intre(n-1)%(k-1);if(re){ll tem0;for(inti0;ire;i){ll tpq.top();temt;pq.pop();}pq.push(tem);anstem;}while((ll)pq.size()1){ll tem0;for(ll i1;ik;i){ll tpq.top();temt;pq.pop();}pq.push(tem);anstem;}coutansendl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;while(T--){solve();}}
