8.23错题总结

· · 个人记录

T1(B3702 [语言月赛202301] 华小科的旅行开始了)

考试思路：直接按照数组给的路线模拟，并输出

考试代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
    int x,y;
}a[1005][1005];
int main()
{
    cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j].x>>a[i][j].y;
    while(a[sx][sy].x!=0&&a[sx][sy].y!=0)
    {
        cout<<sx<<' '<<sy<<'\n';
        int j=sx;
        sx=a[sx][sy].x;
        sy=a[j][sy].y;
    }
    cout<<sx<<' '<<sy<<'\n';
    return 0;
}

正确思路：直接按照数组给的路线模拟，并输出，注意先输入m再输入n，不要搞反了

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
    int x,y;
}a[1005][1005];
int main()
{
    cin>>m>>n>>sx>>sy;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j].x>>a[i][j].y;
    while(a[sx][sy].x!=0&&a[sx][sy].y!=0)
    {
        cout<<sx<<' '<<sy<<'\n';
        int j=sx;
        sx=a[sx][sy].x;
        sy=a[j][sy].y;
    }
    cout<<sx<<' '<<sy<<'\n';
    return 0;
}

T3(T658802 突击考试)

考试思路：因为a[i]和b[i]只有5，所以我就用了前缀和记录，再跑5遍双指针

考试代码：

#include<bits/stdc++.h>
using namespace std;
int sum[15][100005],ans,k,a[100005],b[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        sum[a[i]][i]=1;
        if(a[i]==b[i])
            continue;
        sum[b[i]][i]=1;
    }
    for(int j=1;j<=5;j++)
        for(int i=1;i<=n;i++)
            sum[j][i]+=sum[j][i-1];
    for(int i=1;i<=5;i++)
    {
        int l=1,cnt=0;
        for(int r=1;r<=n;r++)
        {
            int z=sum[i][r]-sum[i][l-1];
            while(sum[i][r]-sum[i][l]>=z&&l<=r)
                l++;
            if(l>r)
                l--;
            if(sum[i][r]-sum[i][l-1]>=r-l+1)
                cnt=max(cnt,r-l+1);
        }
        if(ans<cnt)
        {
            ans=cnt;
            k=i;
        }
    }
    cout<<ans<<' '<<k;
    return 0;
}

正确思路：直接硬搜我竟然没想出来

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,K=100,ans,cnt,a[100005],b[100005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    for(int k=1;k<=5;k++)
    {
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==k||b[i]==k)
                cnt++;
            else
                cnt=0;
            if(cnt>ans)
                ans=cnt,K=k;
        }
    }
    cout<<ans<<' '<<K;
    return 0;
}

T5(T658813 奶牛的羁绊)

考试思路：骗分

考试代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"0\n1\n0\n2\n1\n";
    return 0;
}

正确思路：树的父节点已经搜到了，那它的子节点一定会受影响。DFS序中，一个节点和它的子树一定是连在一起的。所以用DFS求出各个节点的子树大小和DFS序，因为要做区间修改，所以我们用树状数组维护差分数组，每次用get_sum求出单点的答案，然后再把它的子树全部加一，以便后面求值。

正确代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5, INF=1E9;
int n,m,a[N],c[N];
int idx,dfn[N],siz[N];
vector<int>e[N];
void dfs(int u,int father)
{
    dfn[u]=++idx;
    siz[u]=1;
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        if(v==father)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
    return;
}
int lowbit(int x)
{
    return x&-x;
}
int get_sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        int id=dfn[x];
        cout<<get_sum(id)<<'\n';
        modify(id+1,1);
        modify(id+siz[x]-1+1,-1);
    }
    return 0;
}