2020牛客寒假算法基础集训营3

总的来说，应该是前三场中最难的了。
题解

A.牛牛的DRB迷宫I：

  现在来看，很明显的状态递推，第一次看的是竟然没有想到，一直到最后才突然发现。（棋盘型 $dp$dp）。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
char ss[55][55];
ll dp[55][55];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",ss[i]+1);
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ss[i][j]=='R')
                dp[i][j+1]=dp[i][j+1]+dp[i][j]%mod;
            else if(ss[i][j]=='D')
                dp[i+1][j]=dp[i+1][j]+dp[i][j]%mod;
            else if(ss[i][j]=='B')
            {
                dp[i+1][j]=dp[i+1][j]+dp[i][j]%mod;
                dp[i][j+1]=dp[i][j+1]+dp[i][j]%mod;
            }
        }
    }
    printf("%lld\n",dp[n][m]%mod);
    return 0;
}

<mark>B.牛牛的DRB迷宫II</mark>：

C.牛牛的数组越位：

题面
模拟，t了一次，因为用来 $\text{memset()}$memset()，后来改成 $for$for 循环就过了。

#include <bits/stdc++.h>
using namespace std;
const int N=2e7+5;
int a[N];
void read(int &x)
{
    int f=1;
    x=0;
    char c;
    c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    x=x*f;
}
int main()
{
    int t,n,m,p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&p);
        for(int i=0;i<n*m;i++)
            a[i]=0;
        int x,y,v,f=0;
        for(int i=1;i<=p;i++)
        {
            //scanf("%d%d%d",&x,&y,&v);
            read(x);
            read(y);
            read(v);
            long long t=(1LL)*x*m+y;
            if(t>=(1LL)*n*m||t<0)
                f=2;
            if(f<2&&(x<0||x>n||y<0||y>m))
                f=1;
            if(f!=2)
                a[t]=v;//cout<<"t="<<t<<endl;
        }
        if(f==0)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    printf("%d%c",a[i*m+j],j==m-1?'\n':' ');
                }
            }
            printf("Accepted\n");
        }
        else if(f==1)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    printf("%d%c",a[i*m+j],j==m-1?'\n':' ');
                }
            }
            printf("Undefined Behaviour\n");
        }
        else
        {
            printf("Runtime error\n");
        }
    }
    return 0;
}

D.牛牛与二叉树的数组存储：

题面
递归，树的遍历，类似线段树的操作，数组注意初始化为-1，空间开4倍。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N<<2],pre[N],lchild[N],rchild[N];
int n,cnt;
void dfs(int v,int p)
{
    if(a[v]==-1)
        return;
    cnt++;//cout<<"cnt="<<cnt<<endl;
    pre[a[v]]=p;
    lchild[a[v]]=a[v<<1];
    dfs(v<<1,a[v]);
    rchild[a[v]]=a[v<<1|1];
    dfs(v<<1|1,a[v]);
}
int main()
{
    scanf("%d",&n);
    memset(a,-1,sizeof(a));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    cnt=0;
    dfs(1,-1);//cout<<"888"<<endl;
    printf("The size of the tree is %d\n",cnt);
    printf("Node %d is the root node of the tree\n",a[1]);
    for(int i=1;i<=cnt;i++)
        printf("The father of node %d is %d, the left child is %d, and the right child is %d\n",i,pre[i],lchild[i],rchild[i]);
    return 0;
}

<mark>E.牛牛的随机数</mark>：

F.牛牛的Link Power I：

  我的做法是推公式，先计算出相邻两个1之间的间距，然后算出每个间距的使用次数。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
char ss[N];
int a[N];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",ss+1);
    int p=-1,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(ss[i]=='1'&&p!=-1)
        {
            a[++cnt]=i-p;
            p=i;
        }
        else if(ss[i]=='1'&&p==-1)
            p=i;
    }
    long long ans=0;
    if(p==-1)
        printf("0\n");
    else
    {
        for(int i=1;i<=cnt;i++)
            ans=(ans+(1LL)*a[i]*(1LL)*i%mod*(1LL)*(cnt-i+1)%mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

<mark>G.牛牛的Link Power II</mark>：

H.牛牛的k合因子数：

  用欧拉筛把1e5以内的所有合数全部筛出来。然后用这些合数来枚举其在1~n内的倍数（埃氏筛原理），计数。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int num[N],k[N],he[N];
bool vis[N];
vector<int>prime;
int cnt;
void init()
{
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=N-5;i++)
    {
        if(!vis[i])
            prime.push_back(i);
        else
            he[++cnt]=i;//合数
        for(int j=0;j<prime.size()&&i*prime[j]<=N-5;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    cnt=0;
    init();
    for(int i=1;i<=cnt;i++)
    {
        for(int j=he[i];j<=n;j+=he[i])
            num[j]++;
    }
    for(int i=1;i<=n;i++)
        k[num[i]]++;
    int kk;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&kk);
        printf("%d\n",k[kk]);
    }
    return 0;
}

<mark>*I.牛牛的汉诺塔</mark>：

  首先，总次数有公式：<mark> $h\left[n\right]=2^n-1$h[n]=2n−1</mark> 可以直接算。
  而各个移动的次数，如果按照原有的递归程序计算的话，很明显会炸。我手推模拟了几次的移动过程，觉得可以用递推写，但递推式写了半天也没有写出来。
（1）先用题解的记忆化搜索：
在原有的hanoi塔问题的基础上更改，标记状态，移动时对应增加。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll mv[6];
    node operator +(const node b)const
    {
        node res;
        memset(res.mv,0,sizeof(res.mv));
        for(int i=0;i<6;i++)
            res.mv[i]=mv[i]+b.mv[i];
        return res;
    }
};
bool vis[70][5][5][5];
node dp[70][5][5][5];
void mov(int a,int b,int c,node &t)
{
    if(a==0&&c==1)t.mv[0]++;
    if(a==0&&c==2)t.mv[1]++;
    if(a==1&&c==0)t.mv[2]++;
    if(a==1&&c==2)t.mv[3]++;
    if(a==2&&c==0)t.mv[4]++;
    if(a==2&&c==1)t.mv[5]++;
}
node hanoi(int n,int a,int b,int c)
{
    if(vis[n][a][b][c])
        return dp[n][a][b][c];
    if(n==1)
    {
        mov(a,b,c,dp[n][a][b][c]);
        vis[n][a][b][c]=1;
        return dp[n][a][b][c];
    }
    dp[n][a][b][c]=dp[n][a][b][c]+hanoi(n-1,a,c,b);//向下递归
    mov(a,b,c,dp[n][a][b][c]);//移动一块
    dp[n][a][b][c]=dp[n][a][b][c]+hanoi(n-1,b,a,c);//向下递归
    vis[n][a][b][c]=1;
    return dp[n][a][b][c];
}
int main()
{
    int n;
    scanf("%d",&n);
    node ans=hanoi(n,0,1,2);
    printf("A->B:%lld\n",ans.mv[0]);
    printf("A->C:%lld\n",ans.mv[1]);
    printf("B->A:%lld\n",ans.mv[2]);
    printf("B->C:%lld\n",ans.mv[3]);
    printf("C->A:%lld\n",ans.mv[4]);
    printf("C->B:%lld\n",ans.mv[5]);
    printf("SUM=%lld\n",(1LL<<n)-1);
    return 0;
}

<mark>?J.牛牛的宝可梦Go</mark>：

和dp的思想有关，题解没看懂，学清楚dp再来。