2026江南程序设计竞赛联盟暑期多校第一场_补题题解

A 构造的芙莉莲

题目分析：

题目给了我们两个长度均为 n 的排列数组，一个是原数组 a，一个是目标数组 b，要求我们利用异或运算在不超过 3*n 次的操作下，判断是否可以将 a 数组转化为 b 数组。可以则输出Yes，并输出操作过程，反之则输出No。

解题思路：

我们知道数组a，b均为长度为n的排列，即数组元素相同，那么我们要想将a转化为b，就只通过至多n-1次的数据交换就可以实现，而恰好，题目要求的异或操作能够实现这样一个目标：

交换x、y的值，只需通过3次异或操作：
x = x ^y, y = y ^ x, x = x ^ y

这样一来，要想将每个元素归位到相应位置，只需要至多 3 * (n - 1) 次，将不会超过题目要求的 3 * n 次，即一定能构造出这样一个操作序列使得数组a 转化为数组b

代码实现：

#include<bits/stdc++.h>usingnamespacestd;inta[100010];//原数组intb[100010];//目标数组intpos[100010];//记录数组a中每个元素目前所在的位置structfunc{intans1,ans2;}s[300010];//统计答案voidsolve(){intn,ans=0;cin>>n;for(inti=1;i<=n;i++){cin>>a[i];pos[a[i]]=i;}for(inti=1;i<=n;i++)cin>>b[i];cout<<"Yes"<<endl;for(inti=1;i<=n;i++){if(a[i]!=b[i]){intpos1=pos[a[i]],pos2=pos[b[i]];s[ans+1].ans1=pos1;s[ans+1].ans2=pos2;//记录答案s[ans+2].ans1=pos2;s[ans+2].ans2=pos1;s[ans+3].ans1=pos1;s[ans+3].ans2=pos2;swap(a[pos1],a[pos2]);//置换元素pos[a[pos1]]=pos1;//更新元素位置pos[a[pos2]]=pos2;ans+=3;}}cout<<ans<<endl;for(inti=1;i<=ans;i++){cout<<s[i].ans1<<" "<<s[i].ans2<<endl;}}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份，否则代价将偏大

代码实现：

#include<bits/stdc++.h>#definelllonglongusingnamespacestd;voidsolve(){intn,k;cin>>n>>k;ll ans=0;priority_queue<ll,vector<ll>,greater<>>pq;for(ll i=1,x;i<=n;i++){cin>>x;pq.push(x);}intre=(n-1)%(k-1);if(re){ll tem=0;for(inti=0;i<=re;i++){ll t=pq.top();tem+=t;pq.pop();}pq.push(tem);ans+=tem;}while((ll)pq.size()>1){ll tem=0;for(ll i=1;i<=k;i++){ll t=pq.top();tem+=t;pq.pop();}pq.push(tem);ans+=tem;}cout<<ans<<endl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cin>>T;while(T--){solve();}}