2025年3月电子学会c++五级真题

结绳

#include <bits/stdc++.h>
using namespace std;int n,a[10010];int main()
{cin>>n;for(int i = 0;i<n;i++){cin>>a[i];}sort(a+0,a+n);//将a数组从小到大排序double sum = 0;for(int i = 0;i<n;i++){sum = (sum+a[i])/2;}cout<<(int)sum;return 0;
}

最大乘积和

（思路：使用回溯算法（深搜DFS）） 

#include <bits/stdc++.h>
using namespace std;int a[100010],b[100010];
int ca[100010],cb[100010];
int n,m;
int ma;void aaa(int);
int main()
{cin>>n;for(int i = 0;i<n;i++){cin>>a[i];}cin>>m;for(int i = 0;i<m;i++){cin>>b[i];}aaa(0);cout<<ma;return 0;
}
void aaa(int sum)
{ma = max(ma,sum);for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(ca[i]==0&&cb[j]==0){ca[i] = 1;cb[j] = 1;aaa(sum+a[i]*b[j]);ca[i] = 0;cb[j] = 0;}}}}

从A到B

（思路：使用广度优先搜索算法BFS（广搜））

#include <bits/stdc++.h>
using namespace std;
struct node
{int x,v;bool f = true;node(){};node(int aa,int bb){x = aa;v = bb;}
};
node que[200020];
int head,tail;int f[200020];
int a,b,n;int main()
{int t;cin>>t;while(t!=0){head = 0;tail = 0;for(int i = 0;i<200020;i++){f[i] = 0;}cin>>a>>b>>n;a += 100010;b += 100010;//两个“＋100010”是为了加上负数（数轴上的数整体往右移100010个单位长度）que[++tail] = {a,0};f[a] = 1;bool ff = false;while(head<tail){head++;for(int i = 0;i<3;i++){int tx;if(i==0) tx = que[head].x+1;else if(i==1) tx = que[head].x-1;else tx = (que[head].x-100010)*n+100010;if(tx>=0&&tx<200020&&f[tx]==0){f[tx] = 1;que[++tail] = {tx,que[head].v+1};}if(que[tail].x==b){cout<<que[tail].v<<endl;ff = true;break;}}if(ff==true) break;}t--;}return 0;
}

#include <bits/stdc++.h>
using namespace std;int m,n,a[110],b[110];
int ff[110];
bool fff = false;void aaa(int);int main()
{cin>>m;for(int i = 0;i<m;i++){if(i*(i-1)/2==m){n = i;break;}}for(int i = 0;i<m;i++){cin>>a[i];}sort(a+0,a+m);//将a数组从小到大排序b[0] = 0;//确定首个收费站的位置b[n-1] = a[m-1];//确定尾个收费站的位置aaa(1);return 0;
}
void aaa(int x)
{if(x==n-1){int aa[110] = {0};int la = 0;for(int i = 0;i<n;i++){for(int j = i+1;j<n;j++){aa[la] = b[j]-b[i];la++;}}sort(aa+0,aa+la);//将aa数组从小到大排序bool f = true;for(int i = 0;i<m;i++){if(a[i]!=aa[i]){f = false;break;}}if(f==true){fff = true;for(int i = 0;i<n-1;i++){cout<<b[i]<<" ";}cout<<b[n-1];return;}return;}for(int i = 0;i<n;i++){int bb = b[x-1]+a[i];if(ff[bb]==0){b[x] = bb;ff[bb] = 1;aaa(x+1);ff[bb] = 0;}if(fff==true) return;}return;
}