专栏文章

4.1错题总结

wwangyichenawm
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipqag5x
此快照首次捕获于
2025/12/03 16:11
3 个月前
此快照最后确认于
2025/12/03 16:11
3 个月前
查看原文

T2(P5638 【CSGRound2】光骓者的荣耀)

考试思路：前缀和取最大的可传送距离，用总路程减去，就行了

时间复杂度：O(n)

考试代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[1000005],a[1000005],n,k;
signed main()
{
	cin>>n>>k;
	for(int i=1;i<n;i++)
		cin>>a[i],sum[i]=sum[i-1]+a[i];
	int mx=-1e9;
	for(int i=1;i<n-k;i++)
		mx=max(mx,sum[i+k]-sum[i]);
	cout<<sum[n-1]-mx;
	return 0;
}

错误原因：取最大值应该是从0开始，从1开始只能取第2段路到第n段路，第一段路取不了，从0开始就可以取

正确思路：前缀和取最大的可传送距离，用总路程减去，就行了

时间复杂度：O(n)

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum[1000005],a[1000005],n,k;
signed main()
{
	cin>>n>>k;
	for(int i=1;i<n;i++)
		cin>>a[i],sum[i]=sum[i-1]+a[i];
	int mx=-1e9;
	for(int i=0;i<n-k;i++)
		mx=max(mx,sum[i+k]-sum[i]);
	cout<<sum[n-1]-mx;
	return 0;
}

T5(P1434 [SHOI2002] 滑雪)

考试思路：bfs每个点都搜一遍

时间复杂度：O(n4n^4)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][105],mx=-1e9,d[105][105],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct N
{
	int x,y;
};
void bfs(int sx,int sy)
{
	memset(d,0,sizeof d);
	queue<N>q;
	q.push({sx,sy});
	d[sx][sy]=1;
	while(q.size()>0)
	{
		N t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int x=t.x+dx[i],y=t.y+dy[i];
			if(x<1||x>n||y<1||y>m)
				continue;
			if(a[x][y]>=a[t.x][t.y])
				continue;
			d[x][y]=d[t.x][t.y]+1;
			mx=max(mx,d[x][y]);
			q.push({x,y});
		}
	}
	return ;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			bfs(i,j);
	cout<<mx;
	return 0;
}

错误原因：觉得像bfs，没有去思考是bfs好，还是dfs好，就直接开始写了

正确思路：记忆化+dfs，dp存这个点可以滑的最多数，统计出来

时间复杂度：O(n3n^3)

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[105][105],dp[105][105],dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int dfs(int i,int j)
{
	if(dp[i][j]!=0)
		return dp[i][j];
	dp[i][j]=1;
	for(int i1=0;i1<4;i1++)
	{
		int x=i+dx[i1];
		int y=j+dy[i1];
		if(x<1||x>n||y<1||y>m)
			continue;
		if(a[x][y]<a[i][j])
			dp[i][j]=max(dp[i][j],dfs(x,y)+1);
	}
	return dp[i][j];
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	int mx=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			mx=max(mx,dfs(i,j));
	cout<<mx<<endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...