4.1错题总结

wangyichenawm · 2025-04-03 13:27:27 · 个人记录

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

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

时间复杂度：O(n)

考试代码：

#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)

正确代码：

#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(n^4)

考试代码：

#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(n^3)

正确代码：

#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;
}