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;
}