2023公益班题解

本文章由 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

lxn 的博客

博客

T1:

T2: