【题解】2020牛客寒假算法基础集训营3

Bertha 。 2023-07-05 05:20 10阅读 0赞

> 比赛链接：[https://ac.nowcoder.com/acm/contest/3004][https_ac.nowcoder.com_acm_contest_3004]  
> 其他比赛题解：  
> [【题解】2020牛客寒假算法基础集训营1][2020_1]  
> [【题解】2020牛客寒假算法基础集训营2][2020_2]  
> [【题解】2020牛客寒假算法基础集训营4][2020_4]  
> [【题解】2020牛客寒假算法基础集训营5][2020_5]

### 试题目录 ###

*  A - 牛牛的DRB迷宫I（dp）
 *  C - 牛牛的数组越位（模拟）
 *  D - 牛牛与二叉树的数组存储（模拟）
 *  F - 牛牛的Link Power I（dp）
 *  H - 牛牛的k合因子数（数论）

# A - 牛牛的DRB迷宫I（dp） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3004/A][https_ac.nowcoder.com_acm_contest_3004_A]

*  **思路：** 这本是一道经典的走格子dp，签到题，但是一开始一直深搜，然后TLE。其实题目也有暗示，要取模，说明答案超过了 1e9 的范围，就不可能是搜索了。从左上角开始for,如果是D就往下累加，如果是R就往右累加，如果是B就同时累加。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    const ll mod=1e9+7;
    char maps[55][55];
    ll dp[55][55];
    int main(){ 
        int n,m;    cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>maps[i][j];
        dp[1][1]=1;
        for(int i=1;i<=n;i++){ 
            for(int j=1;j<=m;j++){ 
                if(i==1 && j==1)    continue;
                if(i-1>=1){ 
                    if(maps[i-1][j]=='D' || maps[i-1][j]=='B')
                        dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                }
                if(j-1>=1){ 
                    if(maps[i][j-1]=='R' || maps[i][j-1]=='B')
                        dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
                }
            }
        }
        cout<<dp[n][m]%mod<<endl;
        return 0;
    }

# C - 牛牛的数组越位（模拟） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3004/C][https_ac.nowcoder.com_acm_contest_3004_C]

*  **思路：** 直接按照题意模拟就行了。

**Code：**

#include <iostream>
    using namespace std;
    const int N=2e7+10;
    int a[5000][5000];
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            int n,m,p;    cin>>n>>m>>p;
            for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                    a[i][j]=0;
            int vis1=0,vis2=0;
            while(p--){ 
                int x,y,val;    cin>>x>>y>>val;
                if(x<0 || x>=n || y<0 || y>=m)    vis1=1;
                if(m*x+y<0 || m*x+y>n*m-1)    vis2=1;
                if((x*m+y)/m<0 || x*m+y-((x*m+y)/m)*m<0)    continue;
                a[(x*m+y)/m][x*m+y-((x*m+y)/m)*m]=val;
            }
            if(vis1 && vis2)    cout<<"Runtime error"<<endl;
            else if(vis1 && !vis2){ 
                for(int i=0;i<n;i++){ 
                    for(int j=0;j<m;j++){ 
                        if(j!=m-1)    cout<<a[i][j]<<' ';
                        else cout<<a[i][j]<<endl;
                    }
                }
                cout<<"Undefined Behaviour"<<endl;
            }
            else if(!vis1){ 
                for(int i=0;i<n;i++){ 
                    for(int j=0;j<m;j++){ 
                        if(j!=m-1)    cout<<a[i][j]<<' ';
                        else cout<<a[i][j]<<endl;
                    }
                }
                cout<<"Accepted"<<endl;
            }
        }
        return 0;
    }

# D - 牛牛与二叉树的数组存储（模拟） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3004/D][https_ac.nowcoder.com_acm_contest_3004_D]

*  **思路：** 按照题意模拟即可。

**Code：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int N=3e5;
    struct node{ 
        int val,fa,left,right;
    }a[N];
    bool cmp(node a,node b){ 
        return a.val<b.val;
    }
    int main(){ 
        int n;    cin>>n;
        int size=-1;
        for(int i=1;i<=n;i++){ 
            cin>>a[i].val;
            size=max(size,a[i].val);
        }
        int root;
        for(int i=1;i<=n;i++)
            if(a[i].val!=-1){ 
                root=a[i].val;
                break;
            }
        for(int i=1;i<=n;i++){ 
            a[i].fa=a[i/2].val;
            a[i].left=a[i*2].val;
            a[i].right=a[i*2+1].val;
        }
        for(int i=1;i<=n;i++){ 
            if(a[i].val!=-1){ 
                if(a[i].fa==0)    a[i].fa=-1;
                if(a[i].left==0)    a[i].left=-1;
                if(a[i].right==0)    a[i].right=-1;
            }
        }
        sort(a+1,a+1+n,cmp);
        cout<<"The size of the tree is "<<size<<endl;
        cout<<"Node "<<root<<" is the root node of the tree"<<endl;
        for(int i=1;i<=n;i++){ 
            if(a[i].val!=-1){ 
                cout<<"The father of node "<<a[i].val<<" is "<<a[i].fa<<", the left child is "<<a[i].left<<", and the right child is "<<a[i].right<<endl;
            }
        }
        return 0;
    }

# F - 牛牛的Link Power I（dp） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3004/F][https_ac.nowcoder.com_acm_contest_3004_F]

*  **思路：** 对于 dp\[i\] ，等于其累加 dp\[i-1\] 加 i 前面所有的点到 i 的距离 。

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    const ll mod=1e9+7;
    ll a[100100];
    ll dp[100100];
    int main(){ 
        int n;    cin>>n;
        string str;    cin>>str;
        int x=1;
        for(int i=0;i<n;i++){ 
            if(str[i]=='1'){ 
                a[x++]=i;
            }
        }
        x--;
        dp[1]=0;
        ll ans=0;
        for(int i=2;i<=x;i++){ 
            ans=(ans+(i-1)*(a[i]-a[i-1])%mod)%mod;
            dp[i]+=((dp[i-1]%mod+ans%mod)%mod)%mod;
        }
        cout<<dp[x]%mod<<endl;
        return 0;
    }

# H - 牛牛的k合因子数（数论） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/3004/F][https_ac.nowcoder.com_acm_contest_3004_F]

*  **思路：** 埃氏筛先筛出质数，然后对于 n 以内的所有合数，计算其因子为合数的数量并统计。

**Code：**

#include <iostream>
    #include <cstring>
    using namespace std;
    const int N=1e5+10;
    int ans[N],k[N],vis[N];
    void isprime(int n){ 
        memset(vis,1,sizeof(vis));
        vis[0]=vis[1]=1;
        for(int i=2;i*i<=n;i++){ 
            if(vis[i]){ 
                for(int j=i*i;j<=n;j+=i)
                    vis[j]=0;
            }
        }
    }
    int compute(int x){ 
        int num=0;
        for(int i=1;i*i<=x;i++){ 
            if(x%i==0){ 
                if(i*i==x){ 
                    if(!vis[i])    num++;
                }
                else{ 
                    if(!vis[i])    num++;
                    if(!vis[x/i])    num++;
                }
            }
        }
        return num;
    }
    int main(){ 
        ios::sync_with_stdio(0);
        int n,m;    cin>>n>>m;
        isprime(n);
        for(int i=1;i<=m;i++)
            cin>>k[i];
        for(int i=2;i<=n;i++){ 
            if(!vis[i])
                ans[compute(i)]++;
        }
        for(int i=1;i<=m;i++)
            cout<<ans[k[i]]<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_3004]: https://ac.nowcoder.com/acm/contest/3004
[2020_1]: https://blog.csdn.net/weixin_44668898/article/details/104284030
[2020_2]: https://blog.csdn.net/weixin_44668898/article/details/104286708
[2020_4]: https://blog.csdn.net/weixin_44668898/article/details/104292168
[2020_5]: https://blog.csdn.net/weixin_44668898/article/details/104308608
[https_ac.nowcoder.com_acm_contest_3004_A]: https://ac.nowcoder.com/acm/contest/3004/A
[https_ac.nowcoder.com_acm_contest_3004_C]: https://ac.nowcoder.com/acm/contest/3004/C
[https_ac.nowcoder.com_acm_contest_3004_D]: https://ac.nowcoder.com/acm/contest/3004/D
[https_ac.nowcoder.com_acm_contest_3004_F]: https://ac.nowcoder.com/acm/contest/3004/F