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

前言：还是个菜

怎么说，题目思路都有，统统TLE，啊还是应当再去多优化优化算法，多见识见识题目，看看别人的先进想法。有事没事搞个高产卫星什么的。
这次的题目整体偏难，涉及的陌生算法，很多时候都是有思路了，但没有足够的时间去吧想法实现和把细节完善了，和那些已经系统学习过，有模板，并且熟练联系过很多次的人差了很多。还是应当去多总结归纳，看看网上相关的算法学习帖子，借鉴借鉴他人的方式，同时指望指望学校能提供一些学习上的便利吧。

A、牛牛的DRB迷宫I

这个题就是个DP，直接建立状态转移方程

然后就是个码代码了，这个题的定位应该是签到题。

import java.util.*;
class q {
    q() {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int m =scanner.nextInt();
        int val=n;
        n=m;
        m=val;
        char[][] map=new char[m][n];
        long[] dp=new long[m];
        Arrays.fill(dp,0);
        for(int i=0;i<m;i++)map[i]=scanner.next().toCharArray();
        dp[0]=1;
        for(int i=0;i<m-1;i++)if((map[i][0]=='D'||map[i][0]=='B')&&dp[i]==1)dp[i+1]=1;
        for(int i=0;i<n-1;i++){
            if(map[0][i]!='B'&&map[0][i]!='R')dp[0]=0;
            for(int j=1;j<m;j++){
                dp[j]=(map[j][i]=='R'||map[j][i]=='B')?dp[j]:0;
                dp[j]+=(map[j-1][i+1]=='B'||map[j-1][i+1]=='D')?dp[j-1]:0;
                dp[j]%=1000000007;
            }
        }
        System.out.println(dp[m-1]);
    }
}
public class Main {
    public static void main(String[] args) {
        new q();
    }
}

B、牛牛的DRB迷宫II

这个题当时没想出来，现在这个题来边写边想。这个题的题意说白了就是和第一题反着来，第一题给地图让你输出路径条数，这道题是给条数让你输出地图。emmm…毫无想法，想到哪算哪儿吧。

先假设个的地图。

首先，如果按照动态规划的思想，根据状态转移方程，在理想条件下可发现他的递增方式为，我感觉现在可以通过一些比大小的方法，根据已给数据划分出的范围来，然后再通过逐层构造的方式来进行拓展。然后，这组数据就我感觉来说，如果对R和D进行调整，发生的偏差应当也符合这一式子。举个例子，若令传递到的值减少 ，则在产生的影响为

(小声逼逼：这个图好奇怪，LaTeX语法对的了呀，为啥上下的留白那么大)

然后我的思路就是，先构建一个全是B的地图，大小通过进行估算，然后根据所求差值找我们我在什么地方改变字母。

暂时就想到这么多，啊，毫无头绪，再想想。

没忍住看了人家的题解，强，通过二进制构造法去实现对任意数字的模拟。强，牛逼！

C、牛牛的数组越位

这是个水题，对于每大组数据，可以建个，然后将每组中的 导入到所建数组中，这个

数组的意义是，在导入数据的时候准备两个布尔值来确认在导入过程中是否超

出范围。然后把中的值基于进行个排序，然后再去输出就可以了，输出的时候用指针滑动来操作。

D、牛牛与二叉树的数组存储

这个题怎么说呢……和leetcode上的题是两个路子，然后受到leetcode上面的影响太重了。这个题就是直接算就行了，给你组数据，然后让你根据题目所给式子去来回找爸爸….没了。

E、牛牛的随机数

这个题一开始想的就是穷尽，不过很显然的，TLE了，然后也没个好想法。之后看解析，说使用了一种叫做数位dp的东西，感觉很nb，这里贴上网址。

数位DP

数位dp总结 之 从入门到模板

动态规划专题（三）——数位DP

F、牛牛的Link Power I

I、牛牛的汉诺塔

听群里人说这道题好做，就先做的这个，这个题其实好写…….可以打表，可以递推，也可以找通项公式。我用的是先写个打表程序，然后去找通项公式。

以下是打表程序

class q {
    private BigInteger[] k=new BigInteger[6];
    BigInteger sss=BigInteger.valueOf(1);
    public void hanoi(int n, int origin, int assist, int destination) {
        if (n == 1) {
            move(origin, destination);
        } else {
            hanoi(n - 1, origin, destination, assist);
            move(origin, destination);
            hanoi(n - 1, assist, origin, destination);
        }
    }
    private void move(int origin, int destination) {
        if(origin==0){
            if(destination==1)k[0]=k[0].add(sss);else k[1]=k[1].add(sss);
        }else if (origin==1){
            if(destination==0)k[2]=k[2].add(sss);else k[3]=k[3].add(sss);
        }else {
            if(destination==0)k[4]=k[4].add(sss);else k[5]=k[5].add(sss);
        }
    }
    q() {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for(n=1;n<10;n++){
            for(int i=0;i<6;i++)k[i]=new BigInteger("0");
            hanoi(n,0,1,2);
            System.out.println(Arrays.toString(k));
        }
        System.out.println("A->B:" + k[0]);
        System.out.println("A->C:" + k[1]);
        System.out.println("B->A:" + k[2]);
        System.out.println("B->C:" + k[3]);
        System.out.println("C->A:" + k[4]);
        System.out.println("C->B:" + k[5]);
        System.out.println("SUM:" + k[6]);
    }
}

奇数项打出的结果为

偶数项打出的结果为

通过观察，不难发现其通项公式和n的关系为

因为总1等于总2，剩下的就是解方程，码代码了，程序的时间复杂度低到不得了。

import java.math.BigInteger;
import java.util.*;
class q {
    q() {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        BigInteger[] k=new BigInteger[7];
        k[6]= new BigInteger("2").pow(n).subtract(BigInteger.valueOf(1));
        if(n%2==1) {
            BigInteger s=new BigInteger(String.valueOf((n+1)/2));
            k[4]=k[6].add(BigInteger.valueOf(2)).subtract(s).subtract(s).divide(BigInteger.valueOf(9));
            k[0]=k[3]=k[4].add(s).subtract(BigInteger.valueOf(1));
            k[2]=k[5]=k[3].add(k[4]);
            k[1]=k[4].add(k[4]).add(BigInteger.valueOf(n));
        }else {
            BigInteger s=new BigInteger(String.valueOf(n/2));
            k[2]=k[5]=k[6].subtract(s.multiply(BigInteger.valueOf(3))).divide(BigInteger.valueOf(9));
            k[4]=k[5].multiply(BigInteger.valueOf(2));
            k[0]=k[3]=k[4].add(s);
            k[1]=k[5].add(s);
        }
        System.out.println("A->B:" + k[0]);
        System.out.println("A->C:" + k[1]);
        System.out.println("B->A:" + k[2]);
        System.out.println("B->C:" + k[3]);
        System.out.println("C->A:" + k[4]);
        System.out.println("C->B:" + k[5]);
        System.out.println("SUM:" + k[6]);
    }
}
public class Main {
    public static void main(String[] args) {
        new q();
    }
}