2023济南大学acm新生赛题解

通过答题情况的难度系数：

签到：ACI

铜牌题：BG

银牌题：EF

金牌题：DHJKO

赛中暂未有人通过：LMNP

A - A+B Problem

直接根据公式计算就行。

#include<stdio.h>
int main(){int a,b;scanf("%d %d",&a,&b);printf("%d\n",a*b+a+b);return 0;
}

C - 五分钟慢题

输出当前时间五分钟之后。

#include<bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){int h,m;scanf("%d:%d",&h,&m);m+=5;h+=m/60;m%=60;h%=24;printf("%02d:%02d\n",h,m);}
}

I - 你的母校

输出“济南大学”四个字总共多少笔画，可能很多同学不知道“学”是8画，比赛途中很多同学交28，正确答案应该是29.

#include <bits/stdc++.h>
using namespace std;
int main(){printf("29\n");
}

B - A=B Problem

判断等式是否成立，容易发现，先进行乘法和除法操作，再进行加减，但是乘法和除法操作对结果没有影响，所以只需要判断等式两边进行加减的次数即可。

#include <bits/stdc++.h>
using namespace std;
char a[1005];
int main(){int t;cin>>t;while(t--){scanf("%s",a+1);int len=strlen(a+1);int op;//'='的位置int sub=0,add=0;for(int i=1;i<=len;i++){if(a[i]=='='){op=i;break;}else if(a[i]=='-') sub++;else if(a[i]=='+') add++;}int sub1=0,add1=0;for(int i=op+1;i<=len;i++){if(a[i]=='-') sub1++;else if(a[i]=='+') add1++;}sub-add==sub1-add1?printf("1\n"):printf("0\n");}
}

G - 荡蛛丝博士被生物电整红温了

给两个区间，每个区间各取一个值，保证加起来后的数十进制分解下各位数的最大值最大。容易想到，区间大小大于等于10就可得到最大值9，故可先算出左手的伤害范围+右手的伤害范围的区间，然后进行循环，循环次数最大十次即可得到答案。

#include<bits/stdc++.h>
using namespace std;
int solve(long long x){int mx=0;while(x!=0){int k=x%10;mx=max(mx,k);x/=10;}return mx;
}
int main(){int t;cin>>t;while(t--){long long a,b,c,d;cin>>a>>b>>c>>d;a+=c;b+=d;if(b-a>=10) cout<<"9"<<endl;else{int mx=0;for(long long i=a;i<=b;i++){mx=max(mx,solve(i));}cout<<mx<<endl;}}
}

E - 小w智取切糕

有一个切糕的长宽高分别为 x, y, z，摊主想把这块切糕切割成 x* y* z个边长为 1 的小正方体，保证切的次数最少。每次尽量往中间下刀，然后摞起来，一直重复这个过程就行。

#include<bits/stdc++.h>
using namespace std;
int solve(int x){int ans=0;while(x!=1){ans+=1;x=(x+1)/2;}return ans;
}
int main(){int t;cin>>t;while(t--){int x,y,z;cin>>x>>y>>z;int ans=0;ans+=solve(x);ans+=solve(y);ans+=solve(z);cout<<ans<<endl;}
}

F - ym的刀

比赛中，直到最后一场才知道谁是赢家，且每场小局也是如此，故只需要判断最后一场谁赢了，谁就是赢家。当然也可以暴力枚举X，Y，直到找到满足题意得X和Y。

#include<bits/stdc++.h>
using namespace std;
char a[10005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;scanf("%s",a+1);if(a[n]=='O') cout<<"OG wins!\n";else cout<<"LGD wins!\n";}
}

D - 两小时块题

判断矩阵中是否存在x行y列的子矩阵，且子矩阵中数字全为1.

暴力写法就是，枚举若干个x行y列的子矩阵，每个子矩阵进行枚举求和，判断是否等于x*y，时间复杂度O( $n^{4}$ )，如果在赛中写的这种暴力代码，加上一些优化，本题也是可以过的，按道理是不能过的。下面介绍O( $n^{3}$ )做法和O( $n^{2}$ )做法

O( $n^{3}$ )做法：每次枚举，固定x行，枚举列，例如：

求和ans，当遇到0的格子，ans=0，然后继续往后枚举，直到出现ans=x*y。下面附上赛中，电子2302谢家仪的代码进行参考：

#include<stdio.h>
#include<string.h>
int a[501][501];
int main(){int t,x,y,n,m,i,j,k,sum,flag=0;scanf("%d",&t);while(t--){memset(a,0,sizeof(a));flag=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++){for(j=0;j<m;j++){scanf("%d",&a[i][j]);}}sum=0;scanf("%d%d",&x,&y);for(i=0;i<n&&flag==0;i++){for(j=0;j<m&&flag==0;j++){for(k=i;k<i+x;k++){sum+=a[k][j];if(a[k][j]==0) {sum=0;break;}}if(sum==x*y){printf("yes\n");flag=1;}if(j==m-1&&sum!=0) sum=0;}}if(flag==0) printf("no\n");}return 0;
}

O( $n^{2}$ )做法：如果你了解二位前缀和的话，这题应该可以很快就出。可参考这篇博客：二维前缀和详解_二维矩阵前缀-CSDN博客

#include<bits/stdc++.h>
using namespace std;
int a[505][505],pre[505][505];
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];pre[i][j]=0;}}int x,y;cin>>x>>y;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];}}bool ok=false;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i-x>=0&&j-y>=0){int ans=pre[i][j]-pre[i-x][j]-pre[i][j-y]+pre[i-x][j-y];if(ans==x*y){ok=true;}}}}ok==true?cout<<"yes"<<endl:cout<<"no"<<endl;}
}

H - 这题真的不难

由题意可知，n-1条锁链形成了一棵树，每次操作都能删除一个叶子结点，先者都不想操作后使得编号 k变成叶子，不然后者赢得胜利，故删除叶子，只有两种情况，一种是一开始k本身就是叶子，第二种是进行n-2次操作后删除k。

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(){int t;cin>>t;while(t--){int n,k;cin>>n>>k;for(int i=1;i<=n;i++) a[i]=0;for(int i=1;i<=n-1;i++){int x,y;cin>>x>>y;a[x]++;a[y]++;}if(a[k]==1) cout<<"FuRongWang"<<endl;else{if(n&1) cout<<"MaMaShengDe"<<endl;else cout<<"FuRongWang"<<endl;}}
}

J - Syan移动

对数组进行两种操作，一种是左移X位，一种是右移X位，每次操作都进行移位，每组询问数据时间复杂度大概O(n*m)，最坏的情况能达到1e10，这种情况下肯定跑不出来。

显然，多次的不同左右移动操作，会有相互抵消的情况，定义初始状态为右移flag=0的情况，进行右移X位，即flag=flag+X，进行左移X位，即flag=flag-X，最后得到数组需要右移flag位，右移n，2*n，3*n，...相当于数组未移动，所以最后记得对flag进行取模操作，或者在累加操作中进行取模操作。

赛中，有些同学进行移位累加的操作，没有考虑到flag爆int的情况，导致答案错误。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int pre[100005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int m;cin>>m;int state=0;int ans=0;while(m--){char op;int x;cin>>op>>x;if(op=='-') ans-=x;else ans+=x;ans%=n;}if(ans>0){for(int i=n-ans+1;i<=n;i++) printf("%d ",a[i]);for(int i=1;i<=n-ans;i++) printf("%d ",a[i]);}else if(ans==0){for(int i=1;i<=n;i++) printf("%d ",a[i]);}else if(ans<0){ans*=-1;for(int i=ans+1;i<=n;i++) printf("%d ",a[i]);for(int i=1;i<=ans;i++) printf("%d ",a[i]);}printf("\n");}
}

K - Syan的加法

对数组进行两种操作，加法操作和翻转操作。在写这题之前，如果你了解差分，可能就不用太多的思考。

定义：假设有原数组 $a[ ] = {a_1,a_2,a_3...a_n}$ ，现构造出一个数组 $b[ ] = {b_1,b_2,b_3...b_n}$ ，使得 $a_i = b_1 + b_2 + b_3 + ... + b_i$ ，那么 b[ ] 就称为 a[ ] 的差分，a[ ] 就称为 b[ ] 的前缀和。可以发现，差分与前缀和是逆运算。

一维差分可以快速地实现如下操作：区间修改，时间复杂度为 O(1)

假如现在要将原数列 a[ ] 区间 [L,R] 上的每个数都加上 x，那么通过上述定义可以知道：

第一个受影响的差分数组中的元素为 b[L]，所以令 b[L]+=x，那么后面数列元素在计算过程中都会加上 x。
最后一个受影响的差分数组中的元素为 b[R]，所以令 b[R+1]−=x，那么可以保证不会影响到 R 之后数列元素的计算。

这样一来，就不必对区间内每一个数进行处理，只需处理两个端点即可，翻转操作中途不用进行，最后进行翻转就行，不过中间需要记录翻转的状态，然后判断对哪段区间进行操作。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int pre[100005];
int main(){int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int m;cin>>m;int state=0;while(m--){int op,l,r;cin>>op;if(op==1){cin>>l>>r;if(state==0){pre[l]+=1,pre[r+1]-=1;}else{pre[n-r+1]+=1,pre[n-l+2]-=1;}}else{state^=1;}}for(int i=1;i<=n;i++) pre[i]+=pre[i-1],a[i]+=pre[i];if(state==0){for(int i=1;i<=n;i++){i==1?printf("%d",a[i]):printf(" %d",a[i]);}}else{for(int i=n;i>=1;i--){i==n?printf("%d",a[i]):printf(" %d",a[i]);}}for(int i=1;i<=n+1;i++) pre[i]=0;printf("\n"); }
}

O - 微风与笔尖与春日花抄

每次查询，可以暴力枚举以每个方格为起点，然后往八个方向进行枚举匹配。赛中有些同学理解题目可能有误，出现的字串只能是任意一个方向延伸任意长度，将这段路径上的字符按顺序连接，不会出现拐弯的情况。

#include<bits/stdc++.h>
using namespace std;
char a[35][35];
char b[105];
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,-1,1,1,-1,1,-1,-1};
int main(){int n;cin>>n;int m;cin>>m;for(int i=1;i<=n;i++) scanf("%s",a[i]+1);for(int i=1;i<=m;i++){scanf("%s",b+1);int len=strlen(b+1);bool ok=false;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]==b[1]){for(int k=0;k<8;k++){int x=i,y=j;bool flag=true;for(int m=1;m<=len;m++){if(x>=1&&x<=n&&y>=1&&y<=n&&b[m]==a[x][y]){}else flag=false;x+=dir[k][0];y+=dir[k][1];}if(flag){ok=true;break;}}}}}ok==true?printf("yes\n"):printf("no\n");}
}

L - Syan的最大金币数（2）

由题意可得，整个迷宫被障碍物分成了几个区域，如果起点和终点不在一个区域，将无法离开迷宫；如果在一个区域，区域中，不管Syan从哪个点出发，都能到达整个区域的所有点，然后选择一个金币数最大的格子，最后离开迷宫。故这题可以先使用bfs或者dfs找出所有区域的最大值，然后离线查询即可。

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
int vis[1005][1005];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m;
int num=0;
void dfs(int x,int y){for(int i=0;i<4;i++){int X=x+dir[i][0],Y=y+dir[i][1];if(X>=1&&X<=n&&Y>=1&&Y<=n&&a[X][Y]!=-1&&vis[X][Y]==0){vis[X][Y]=vis[x][y];dfs(X,Y);}}
}
void bfs(int x,int y){queue<pair<int,int> >q;q.push({x,y});while(!q.empty()){pair<int,int> st = q.front();q.pop();for(int i=0;i<4;i++){int nx=st.first+dir[i][0],ny=st.second+dir[i][1];if(nx>=1&&nx<=n&&ny<=n&&ny>=1&&a[nx][ny]!=-1&&vis[nx][ny]==0){vis[nx][ny]=vis[st.first][st.second];q.push({nx,ny});}}}
}
int mx[1000005];
int main(){int t;cin>>t;while(t--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];vis[i][j]=0;}}int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]!=-1&&vis[i][j]==0){vis[i][j]=++cnt;bfs(i,j);//或者dfs(i,j)}}}for(int i=0;i<=cnt;i++) mx[i]=-1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(vis[i][j]!=0) mx[vis[i][j]]=max(mx[vis[i][j]],a[i][j]);}}while(m--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;if(vis[x1][y1]!=vis[x2][y2]) cout<<"-1\n";else cout<<mx[vis[x1][y1]]<<endl;}}
}

M - 色彩与轮回与夜幕之国

给为0的格子进行上色，保证相邻格子不会出现相同颜色。首先，出现了相邻格子且都是1的情况，肯定不能满足题意，无法实现目标。其他情况就是可以实现目标的情况，显然，有如下几种情况需要改变相邻位置为0的颜色：

1. 出现若干个相邻位置为0的情况，且若干个位置形成一条直线，需要一种颜色；

例如： $\begin{bmatrix} 0 &0 &0 &0 \end{bmatrix}$ 或者 $\begin{bmatrix} 0\\ 0\\ 0\\ 0 \end{bmatrix}$

2. 出现"三角形"相邻位置为0的情况，需要两种颜色；

例如： $\begin{bmatrix} &0 \\ 0 & 0 \end{bmatrix}$ 或者 $\begin{bmatrix} 0& \\ 0& 0 \end{bmatrix}$ 或者 $\begin{bmatrix} 0&0 \\ & 0 \end{bmatrix}$ 或者 $\begin{bmatrix} 0&0 \\ 0& \end{bmatrix}$

3. 出现"正方形"相邻位置为0的情况，需要三种颜色；

例如： $\begin{bmatrix} 0&0 \\ 0 & 0 \end{bmatrix}$

优先级为情况3>情况2>情况1.

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int dir[8][2]={-1,0,1,0,0,-1,0,1,-1,1,-1,-1,1,1,1,-1};
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}bool ok=true;bool ok1=false,ok2=false,ok3=false;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<8;k++){int x=i+dir[k][0],y=j+dir[k][1];if(x>=1&&y>=1&&x<=n&&y<=m){if(a[x][y]&&a[i][j]) ok=false;if(!a[x][y]&&!a[i][j]){ok1=true;if(x==i&&y-j==1){if(x-1>=1&&!a[x-1][j]){ok2=true;if(!a[x-1][y]) ok3=true;}if(x+1<=n&&!a[x+1][j]){ok2=true;if(!a[x+1][y]) ok3=true;}}if(x==i&&y-j==-1){if(x-1>=1&&!a[x-1][j]){ok2=true;if(!a[x-1][y]) ok3=true;}if(x+1<=n&&!a[x+1][j]){ok2=true;if(!a[x+1][y]) ok3=true;}}}}}}}if(!ok) cout<<"-1"<<endl;else{if(ok3) cout<<"3"<<endl;else if(ok2) cout<<"2"<<endl;else if(ok1) cout<<"1"<<endl;else cout<<"0"<<endl;}}
}

N - 吉他与孤独与蓝色星球

由题意可知，需要在区间[l,r]中找到x阶升调乐段，容易直到x最大为r-l+1，故区间[l,r]中可以组成升调乐段的最小段树为mina，如果x>=mina，说明可以组成x阶升调乐段，反之不可组成，现在得问题就是找到mina。显然，找到区间[l,r]中的最长递减（严格递减）子序列，你会发现递减（严格递减）子序列，不管怎么进行组合，都只能组成单个音符的乐段，故这题只需要找到区间[l,r]中的最长递减（严格递减）子序列，其长度就是区间[l,r]中可以组成升调乐段的最小段树mina。

算法的合理性其实很清楚，找到最长递减（严格递减）子序列，剩余的其他数，每个都可以往最长递减（严格递减）子序列其中的某个位置后面塞。

#include<bits/stdc++.h>
using namespace std;
int a[1005],f[1005];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]);while(m--){int x,y,z,s=1;scanf("%d%d%d",&x,&y,&z);for(int i=x;i<=y;i++){f[i]=1;for(int j=x;j<i;j++) if(a[i]<a[j]) f[i]=max(f[i],f[j]+1),s=max(s,f[i]);}puts(s<=z?"yes":"no");}
}

P - 守护与救济与星海泛舟

给一个无向图，每条边都有边权，每次查询结点x到结点y中的所有路径，找出到达结点y路径上的最大边权最小。

首先，我们可以先把所有的边按照从小到大排序，遍历所有边，对每条边的端点u,v，通过并查集将他们表示相连，每次连完后判断起点和终点是否在同一集合里，如果在则输出这次的边权，即为答案。算法的合理性其实很清楚，贪心地从最短的边开始找起，一直到起点终点相连，最后加入的边是此次路径内的边的最大值，就是答案。

但是本题有m次查询，每次都重复这个步骤，时间肯定不允许，故可以预处理出最小生成树，然后利用倍增法求树中两个结点的最近公共祖先LCA的思路（可参考博客84-倍增法求最近公共祖先LCA(超清晰的思路) - 知乎 (zhihu.com)），保存每个结点往上跳 $2^i$ 下的路径最大值。

#include<bits/stdc++.h>
using namespace std;
const int Max=2e6+5;
int n,m,k;
struct node1{int to;int val;
};
vector<node1>v[Max];int vis[Max];
void init(int n){for(int i=1;i<=n;i++) vis[i]=i;
}
int father(int x){if(x==vis[x]) return x;return vis[x]=father(vis[x]);
}
void link(int x,int y){vis[father(x)]=vis[father(y)];
}
struct node{int u,v,z;
};
node mp[Max];
int dep[Max];
int fa[Max][25],fa1[Max][25];
void dfs(int fat,int u,int s){fa[u][0]=fat;fa1[u][0]=s;dep[u]=dep[fat]+1;for(auto tmp:v[u]){if(tmp.to!=fat){dfs(u,tmp.to,tmp.val);}}
}
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int u,vv,w;scanf("%d%d%d",&u,&vv,&w);mp[i]={u,vv,w};}sort(mp+1,mp+1+m,[&](node a,node b){return a.z<b.z;});init(n);for(int i=1;i<=m;i++){if(father(mp[i].u)!=father(mp[i].v)){link(mp[i].u,mp[i].v);v[mp[i].u].push_back({mp[i].v,mp[i].z});v[mp[i].v].push_back({mp[i].u,mp[i].z});}}dfs(0,1,0);for(int i=1;i<=20;i++){for(int j=1;j<=n;j++){fa[j][i]=fa[fa[j][i-1]][i-1];fa1[j][i]=max(fa1[fa[j][i-1]][i-1],fa1[j][i-1]);}}while(k--){int x,y;scanf("%d%d",&x,&y);if(dep[x]>dep[y]) swap(x,y);int ans=0;int num=dep[y]-dep[x];for(int i=20;i>=0;i--){if(num>=(1<<i)){num-=(1<<i);ans=max(ans,fa1[y][i]);y=fa[y][i];}}for(int i=20;i>=0;i--){if(fa[x][i]!=fa[y][i]){ans=max(ans,fa1[y][i]);ans=max(ans,fa1[x][i]);y=fa[y][i];x=fa[x][i];}}if(x!=y) ans=max(ans,fa1[y][0]),ans=max(ans,fa1[x][0]);printf("%d\n",ans);}
}