2025年广州大学程序设计竞赛新生赛

A   魔法门禁试炼

比较大小，难度一星

#include <iostream>
using namespace std;
int main()
{int a,b,c,d;cin>>a>>b>>c>>d;if(a<d&&b==c)cout<<"YES";elsecout<<"NO";return 0;
}

B   漫步大地的游医

把各药材收集起来后，变成多重背包dp（类似5. 多重背包问题 II - AcWing题库），时间复杂度 \(O(n*m)\) ,难度3星

#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+10,M=2010;
const int inf=1e9+7;
int n,m,k;
int a[N];
int v[N];
int dp[N];
void solve(){cin>>n>>m>>k;map<int,int>mp;for(int i=1;i<=n;i++){int p;cin>>p;mp[p]++;}for(int i=1;i<=m;i++)cin>>v[i];for(auto it:mp){for(int i=k;i>=0;i--){for(int j=min(it.se,i);j>=1;j--){int tmp=log(j+1)/log(2);dp[i]=max(dp[i],dp[i-j]+tmp*v[it.fi]);}}}cout<<dp[k]<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

C   归零者

模拟题，从左往右依次把1覆盖即可，难度一星

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;//cout<<n<<endl;string s;// cin>>s;int count=0;cin>>s;int t=0;while(t<n){if(s[t]=='1'){count++;t+=2;//cout<<t<<endl;}else if(s[t]=='0')t++;}cout<<count;return 0;
}

G   字符串GCD

输出相同的字母即可，难度一星

#include <bits/stdc++.h>
using namespace std;int main(){ string str1,str2;cin>>str1>>str2;for(int i=0;i<2;i++){for(int j=0;j<2;j++){if(str1[i]==str2[j]){cout<<str1[i];continue;}}}return 0;
}

H   学士的书签

比较大的模拟，难度2星

#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N=5e6+10,M=2010;
int n,m,k;
int a[N];
queue<int>q[3],p[3];
void solve(){cin>>n;int sum=n*(n+1)/2;if(sum%3==0){cout<<-1<<endl;return ;}for(int i=1;i<=n;i++){q[i%3].push(i);p[i%3].push(i);}vector<int>ans;ans.pb(q[1].front());q[1].pop();int idx=1;for(int i=2;i<=n;i++){if(idx==1){if(q[0].size()){ans.pb(q[0].front());q[0].pop();}else if(q[1].size()){ans.pb(q[1].front());q[1].pop();idx=2;}else {break;}}else {if(q[0].size()){ans.pb(q[0].front());q[0].pop();}else if(q[2].size()){ans.pb(q[2].front());q[2].pop();idx=1;}else {break;}}}if(ans.size()==n){for(auto it:ans){cout<<it<<" ";}return;}ans.clear();ans.pb(p[2].front());p[2].pop();idx=2;for(int i=2;i<=n;i++){if(idx==1){if(p[0].size()){ans.pb(p[0].front());p[0].pop();}else if(p[1].size()){ans.pb(p[1].front());p[1].pop();idx=2;}else {break;}}else {if(p[0].size()){ans.pb(p[0].front());p[0].pop();}else if(p[2].size()){ans.pb(p[2].front());p[2].pop();idx=1;}else {break;}}}if(ans.size()==n){for(auto it:ans){cout<<it<<" ";}return;}cout<<-1<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

I   卡牌游戏 2

猜结论+模拟，难度两星
无交集双方都为0，有交集一定一方得到总分，具体谁是赢家需要模拟。

#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N=1e6+10,M=2010;
int n,m,k;
int a[N];
int b[N];
bool st[N];
bool st2[N];
void solve(){cin>>n>>m;int res=0;for(int i=1;i<=n;i++)cin>>a[i],st[a[i]]=1;for(int i=1;i<=m;i++){cin>>b[i];if(st[b[i]]){res+=b[i];st2[b[i]]=1;}}if(res==0){cout<<"0 0"<<endl;return ;}queue<int>q1,q0,p1,p0;for(int i=1;i<=n;i++){if(st2[a[i]]){q1.push(a[i]);}else q0.push(a[i]);}for(int i=1;i<=m;i++){if(st2[b[i]]){p1.push(b[i]);}else p0.push(b[i]);}int idx=1;while(q0.size()+q1.size()&&p0.size()+p1.size()){if(idx==1){if(q0.size()==0){cout<<0<<" "<<res<<endl;return;}q0.pop();idx=2;}else {if(p0.size()==0){cout<<res<<" "<<0<<endl;return;}p0.pop();idx=1;}}if(idx==1){cout<<0<<" "<<res<<endl;}else {cout<<res<<" "<<0<<endl;}}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

J   星流萤

先去看K题！！！

bfs，难度4星；加练 P2802 回家 - 洛谷难度3星

熟练之后来进阶：P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱 - 洛谷，难度4星

#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+10,M=2010,inf=0x3f3f3f3f;
int n,m,k;
int dx[]={0,0,1,-1},dy[]={-1,1,0,0};
int hm[]={1,0,3,2};
bool st[M][M];
int dist[M][M][4];
struct nod{int x,y;int w,b;int cnt;bool operator<(const nod&u)const{return cnt>u.cnt;}
};
void bfs(){priority_queue<nod>qq;for(int i=0;i<4;i++){qq.push({1,1,i,hm[i],0});dist[1][1][i]=0;}while(qq.size()){auto tmp=qq.top();qq.pop();int x=tmp.x, y=tmp.y;int w=tmp.w, b=tmp.b;// cout<<x<<" "<<y<<" "<<w<<" "<<b<<endl;// cout<<dist[x][y]<<endl;for(int i=0;i<4;i++){if(i==b)continue;int tx=x+dx[i];int ty=y+dy[i];int cnt=tmp.cnt;if(i!=w)cnt++;if(tx<1||tx>n||ty<1||ty>m||st[tx][ty])continue;if(cnt<dist[tx][ty][i]){dist[tx][ty][i]=cnt;qq.push({tx,ty,i,hm[i],cnt});}}}int minv=inf;for(int i=0;i<4;i++)minv=min(minv,dist[n][m][i]);cout<<minv<<endl;}
void solve(){memset(dist,0x3f,sizeof dist);cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>st[i][j];bfs();}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

K   位运算2

bfs，难度2星
课程：AcWing 844. 走迷宫 - AcWing
加练：P1135 奇怪的电梯 - 洛谷

#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
#define LL long long
using namespace std;
const int N=5e6+10,M=2010;
const LL mod=1e9+7;
int n,m,k;
int a[N];void solve(){cin>>n>>m>>k;set<int>st;queue<int>qq;qq.push(n);st.insert(n);while(qq.size()){int tmp=qq.front();qq.pop();if(tmp==k){cout<<"YES"<<endl;return;}int idx=tmp|m;if(st.find(idx)==st.end()){st.insert(idx);qq.push(idx);}idx=tmp&m;if(st.find(idx)==st.end()){st.insert(idx);qq.push(idx);}idx=tmp^m;if(st.find(idx)==st.end()){st.insert(idx);qq.push(idx);}}cout<<"NO"<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

L   最大平均数

dp，需考虑继承上一长度的值，难度3星

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+10,M=5010;
const int inf=1e9+7;
int n,m,k;
int a[M];
int dp[M][M];
void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;dp[i][j]=max(dp[i+1][j],dp[i][j-1]);int sum=a[j]-a[i-1];dp[i][j]=max(dp[i][j],sum/len);}}int res=0;for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)res+=dp[i][j];cout<<res<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;// cin>>_;while(_--)solve();return 0;
}

D   小学一年级地理

只用维护两个数组，分别记录一个上升或下降段的左端点就可以进行判断了

#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define pb push_back
#define vvi vector<vector<int>>
#define fi first
#define se second
#define endl '\n' 
using namespace std;
const int N=1e6+10,M=2010,mod=100003;
const int INF=0x3f3f3f3f;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int n,m,k;
int a[N];
int up[N],down[N];
/*
up[i]表示在第i个数前面，维持上升趋势的最底下的数的位置
换一种说法，就是该（第i个数所在的）上升段的左端点的位置
*/
//down[i]表示在第i个数前面，维持下降趋势的最底下的数的位置，与up数组的效果类似
void solve(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];up[1]=down[1]=1;for(int i=2;i<=n;i++){if(a[i]<a[i-1]){down[i]=down[i-1];up[i]=i;}else {down[i]=i;up[i]=up[i-1];}//cout<<up[i]<<" "<<down[i]<<endl;}while(m--){int l,r;cin>>l>>r;//l和r在同一个上升段上if(up[l]==up[r])cout<<"u"<<endl;//l和r在同一个下降段上else if(down[l]==down[r])cout<<"d"<<endl;/*通过r先找到峰顶:down[r]通过峰顶找山底：up[down[r]]如果山地的位置小于等于l，说明这是一个山峰*/else if(up[down[r]]<=l)cout<<"t"<<endl;/*通过r先找到谷底:up[r]通过谷底找山顶：down[up[r]]如果山地的位置小于等于l，说明这是一个山谷*/else if(down[up[r]]<=l)cout<<"v"<<endl;else cout<<"?"<<endl;}}signed main(){std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--) solve();return 0;
}

F   时光终逝，盛宴永存

题目要求将G视为一棵二叉树，意味着在该连通分量中 s 的度数最大为 2。对于一已经选择的连通分量 G，如果存在节点 s' 的度数为 3，通过舍弃 s' 的一条边所连接的整个连通分量，令s'成为满足条件的根节点时，答案一定会劣于直接选择被舍弃的连通分量上的一个叶子节点作为根节点。因此，答案的连通分量应当选择森林中一棵完整的树，并挑选一个度数不为 3 的最小节点作为根节点。
遍历整个图即可，复杂度 O(n)

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define endl '\n' 
using namespace std;
const int N=1e6+10,M=2010,inf=0x3f3f3f3f3f3f3f3f;
int n,m,k;
int a[N],d[N];
int h[N],ne[N],e[N],idx;
int vis[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(int p){queue<int>qq;qq.push(p);vector<int>tr;tr.pb(p);vis[p]=1;while(qq.size()){int tmp=qq.front();qq.pop();for(int i=h[tmp];~i;i=ne[i]){int j=e[i];if(vis[j])continue;vis[j]=1;qq.push(j);tr.pb(j);}}int mina=inf,sum=0;for(auto i:tr){sum+=a[i];if(d[i]<=2)mina=min(mina,a[i]);}return 2*sum-mina;}
void solve(){memset(h,-1,sizeof h);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];while(m--){int u,v;cin>>u>>v;add(u,v);add(v,u);d[u]++,d[v]++;}int maxv=0;for(int i=1;i<=n;i++)if(!vis[i])maxv=max(maxv,bfs(i));cout<<maxv<<endl;
}signed main(){std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _=1;//cin>>_;while(_--) solve();return 0;
}