2026江南程序设计竞赛联盟暑假多校训练第五场_补题题解

L CTR？篮球！

题目分析：

一共有两排数量为 n 的篮球队伍， 现在要在这两个队伍中任取 x 个人组成一个队伍，且不能连续选择同一排的学生，求所选的队伍最大的总身高。

解题思路：

根据题目，我们可以得出这样一个结论：如果选择第一排第 i 位学生，上一个选中的学生只能来自第二排（编号小于 i）；同理，如果选择第二排第 i 位学生，上一个选中的学生只能来自第一排（编号小于 i）。

这个时候我们可以利用动态规划的思想。
设 max0：遍历到当前编号，最后一人选自第一排所能得到的最大总身高；
设 max1：遍历到当前编号，最后一人选自第二排所能得到的最大总身高。
max0 = max(max0, max1 + 第一排的第 i 位置的值)
max1 = max(max1, max0 + 第二排的第 i 位置的值)

而最后的答案则为 max(max0, max1).

代码实现：

#include<bits/stdc++.h>#definelllonglongusingnamespacestd;ll a[100010];ll b[100010];voidsolve(){intn;ll ans0=0,ans1=0,ans=0;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)cin>>b[i];for(inti=1;i<=n;i++){ll tem0=ans1+a[i];ll tem1=ans0+b[i];ans0=max(ans0,tem0);ans1=max(ans1,tem1);}ans=max(ans0,ans1);cout<<ans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);solve();}

G GCD与MINI

题目分析：

给了我们一个长度为 n 的数组，我们可重新排列数组，判断是否可以找到一个以 i 为分界线，左边所有数的最小值 = 右边所有数的最大公约数。

解题思路：

既然是让我们判断是否存在 ：以 i 为分界线，左边所有数的最小值 = 右边所有数的最大公约数。

那么我们可以判断的是左边的最小值一定是整个数组的最小值，所以我们只需要找到是否存在 x ( 1 <= x <= n - 1) 个数的 gcd 等于这个最小值。

特殊情况：
如果数组中的最小值的个数不止一个，那么就我们可以直接输出 “Yes”；
如果数组只有两个数，那么如果这两个数相等则输出 “Yes”， 反之，输出 “No”。

代码实现：

#include<bits/stdc++.h>#definelllonglongusingnamespacestd;ll a[100010];voidsolve(){intn,cnt=0;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];if(n==2){if(a[1]==a[2]){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return;}sort(a+1,a+1+n);if(a[1]==a[2]){cout<<"Yes"<<endl;return;}vector<ll>v;for(inti=2;i<=n;i++){if(a[i]%a[1]==0){cnt++;v.push_back(a[i]);}}if(cnt<2){cout<<"No"<<endl;return;}ll tem=v[0];for(autoit:v){tem=gcd(tem,it);if(tem==a[1]){cout<<"Yes"<<endl;return;}}cout<<"No"<<endl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cin>>T;while(T--){solve();}}