本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-06 17:17:15
2023编程公益班期末考试题解
T1:
加法，求和，不解释
T2:
注意i<=j<=k
方法1 ：三重循环枚举，超时。
方法2：减少枚举量
选择枚举中间，可以并列枚举左侧赵最大xai，右侧找最大zak;时间复杂度o(n*n)
long long x,y,z ,n,a[200009],ans;
int main()
{
cin>>n>>x>>y>>z;
ans=-3*1e18;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int j=1;j<=n;j++){
long long l=-2e18,r=-2e18;
for(int i=1;i<=j;i++)l=max(l,x*a[i]);
for(int k=j;k<=n;k++)r=max(r,z*a[k]);
ans=max(ans,l+a[j]*y+r);
}
cout<<ans<<endl;
}
方法三：
方法二内的枚举有大量重复计算。
for(int j=1;j<=n;j++){
long long l=-2e18,r=-2e18;
for(int i=1;i<=j;i++)l=max(l,x*a[i]);\/\/改成提前枚举前缀最大值。
for(int k=j;k<=n;k++)r=max(r,z*a[k]);\/\/改成提前处理后缀最大值。
ans=max(ans,l+a[j]*y+r);
}
参考代码：
long long x,y,z ,n,a[200009],f[200009],g[200009],ans;
int main(){
cin>>n>>x>>y>>z;
memset(f,0x80,sizeof(f));
memset(g,0x80,sizeof(g));
ans=-3*1e18;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i]=max(f[i-1],a[i]*x);
}
for(int i=n;i>=1;i--)
g[i]=max(g[i+1],a[i]*z);
for(int i=1;i<=n;i++){
ans=max(ans,f[i]+a[i]*y+g[i]);
}
cout<<ans<<endl;
}
方法四：
可以进行3次前缀最值。
#include<bits\/stdc++.h>
using namespace std;
long long x,y,z,a,n,p,q,r;
int main() {
cin>>n>>p>>q>>r;
x=y=z=-3*1e18;
for(int i=1; i<=n; ++i) {
cin>>a;
x=max(x,a*p);
y=max(y,x+a*q);
z=max(z,y+a*r);
}
cout<<z;
}
T3:
我们可以把题目看成一个栈，而题目的要求就是在这个栈里面进行入栈、出栈和查询的工作。
- 解题思路： 我们设f[i]为栈中从下到上的i个元素中的最大值，当我们加入一个新元素x时，t++，由于多了一个元素，所以f[t]=max(f[t-1],x)。那么在出栈时只要输出f[t-1]，在查找时只要输出f[t]。
T4:
本题修改自:一平学长讲课练习题ABC289C
深度优先搜索，子集枚举，广度优先搜索等做法都可以。
T5:马走日
本题的一次行走过程是宽度优先搜索BFS。每次行走都BFS的化，时间复杂度O(LLN)只能解决一般的数据，另外一半超时。
实际这个题目我们只需要计算马的相对位置即可。运用一次BFS，后面直接对马的两对坐标求差值，o(1)查询。时间复杂度O(L*L+N);
参考代码;
#include <bits\/stdc++.h>
using namespace std;
#define maxn 1010
\/\/ a：从(1,1)到目标坐标需要的最少步数，vis:访问标志
int a[maxn][maxn], vis[maxn][maxn],l;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
queue<pair<int,int> > q; \/\/ q:坐标队列
void bfs()
{
while (!q.empty())
{
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 8; ++i)
{
int nx = x + dx[i], ny = y + dy[i];
if ( nx >0 && nx <=l && ny >0 && ny <=l && vis[nx][ny] == 0)
{
a[nx][ny] = a[x][y] + 1;
q.push(make_pair(nx,ny));
vis[nx][ny] = 1;
}
}
}
}
int main()
{
memset(a, 0, sizeof a);
\/\/ (1,1)进入队列，并初始化
q.push(make_pair(1,1));
vis[1][1] = 1;
a[1][1] = 0;
\/\/ 搜索(1,1)到所有坐标的最少步数
int T;
scanf("%d%d",&l, &T);
bfs();
while (T--)
{
int ax, ay, bx, by;
scanf("%d%d%d%d", &ax, &ay, &bx, &by);
\/\/ 获取坐标距离
int x = abs(ax - bx) + 1;
int y = abs(ay - by) + 1;
if(vis[x][y])printf("%d\n", a[x][y]);
else printf("-1\n");
}
return 0;
}
T6:返程之旅
学过图论的同学，可以发现这是最短路的变形题目。
注意到是单源最短路，且没有负边权，选择 Dijkstra。在城市的停留的时间可以丢进路线的时间里，具体操作如下：每条路的边权=原来的边权+目的地的点权。这样就转化成了一个 Dijkstra 板子题。
T7：瘦身迷宫
类似于求最短路径的问题，可以使用 bfs 讨论。
定义队列 q，含有四个元素：x 和 y：当前小容坐标、Time：当前时刻、size：小容身材
每次取出队首并向四个方向以及不动拓展，并判断当前位置是否走过以及这个位置小容能否站的下（小容的占地区域内有没有障碍物），如果站的下就入队，入队时判断一下小容身材的情况。
- 优化1.及当小容占地是 1×1的时候可以不用判断小容原地不动的情况，此时站着不动是无意义的举措，因为无论怎样走都不会有障碍物遮挡他。
- 优化2.只有当身体缩小才能继续移动的时候等待，其余的点不用等待。
T8:隔离点
方法一：
直接考虑原问题比较困难，我们可以这么想：删去的最少=留下来的最多。
那么我们考虑用类似于最小生成树的思想。在使用Kruskal算法时，并查集还要保存一个是否连接感染病毒的城市。然后合并的时候必须要两个集合不是都有病毒的城市（最多只有一个集合有病毒的城市）才可以合并。
方法二:
树形dp
鲁ICP备2025150228号