蘑菇阵_字符串计数

蘑菇阵

//error 未解之谜!!!!垃圾bug 2022 05 17 一道算法题整整一下午没调试出来,裂开!!!一杯茶,一道题,一个bug调一天...
// write your code here
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int N = sc.nextInt();
            int M = sc.nextInt();
            int k = sc.nextInt();
            double[][] arr = new double[N][M];
            boolean[][] table = new boolean[N][M];
            for(int i = 0;i<k;i++){
                int x = sc.nextInt();
                int y = sc.nextInt();
                table[x-1][y-1] = true;
            }

            //初始化
            arr[0][0] = 1;
            for(int i = 1;i<N;i++){
                //第一列
                if(table[i][0]){
                    //设置该位置概率为0!
                    arr[i][0] = 0;
                    break;//后面的概率都为0!
                }
                arr[i][0] = 0.5;
            }
            for(int i = 1;i<M;i++){
                //第一行!
                if(table[0][i]){
                    //设置该位置概率为0!
                    arr[0][i] = 0;
                    break;//后面的概率都为0!
                }
                arr[0][i] = 0.5;
            }
            for(int i = 1;i<N;i++){
                for(int j = 1;j<M;j++){
                    if(table[i][j]){//蘑菇位置!
                        arr[i][j] = 0;
                        continue;
                    }
                    if(i==N-1&&j==M-1){//最后一个位置!
                        //上面坐标只能往下走
                        //左边坐标只能往右走
                        arr[i][j] =  arr[i-1][j] + arr[i][j-1];
                        continue;
                    }
//                    if(i==N-1){//最后一行!
//                        //考虑边界!
//                        //说明左边位置只能往右走!否者越界!
//                       arr[i][j] =  0.5*arr[i-1][j] + arr[i][j-1];
//                       continue;
//                    }
//                    if(j==M-1) {//最后一列!
//                        //说明这里上面的位置坐标只能往下走!
//                        arr[i][j] = arr[i - 1][j] + 0.5 * arr[i][j - 1];
//                        continue;
//                    }
//                  //这里的前一个路径点可以有2种选择所以要乘0.5!
                // arr[i][j] = 0.5*arr[i-1][j] + 0.5*arr[i][j-1];
                    arr[i][j] = (i==N-1?1.0:0.5)*arr[i][j-1] +
                            (j==M-1?1.0:0.5)*arr[i-1][j];
                }
            }
            System.out.println(arr[N-1][M-1]);
        }
    }
}

//正确答案!
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int N = sc.nextInt();
            int M = sc.nextInt();
            int k = sc.nextInt();
            double[][] arr = new double[N+1][M+1];
            boolean[][] table = new boolean[N+1][M+1];
            for(int i = 0;i<k;i++){
                int x = sc.nextInt();
                int y = sc.nextInt();
                table[x][y] = true;
            }

            //初始化
            arr[1][1] = 1.0;
            for(int i = 1;i<=N;i++){
                for(int j = 1;j<=M;j++){
                    if(i==1&&j==1)continue;
                    if(table[i][j]){//蘑菇位置!
                        arr[i][j] = 0;
                        continue;
                    }
                    arr[i][j] = (i==N?1.0:0.5)*arr[i][j-1] +
                            (j==M?1.0:0.5)*arr[i-1][j];
                }
            }
            System.out.printf("%.2f\n",arr[N][M]);
        }
    }
}

总结:

动态规划问题老老实实多开辟一行一列吧!

害,还有这里的概率要会分析!

字符串计数

字符串计数

// write your code here
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            //一组测试用例!
            StringBuffer str1 = new StringBuffer(sc.next());
            StringBuffer str2 = new StringBuffer(sc.next());
            int len1 = sc.nextInt();
            int len2 = sc.nextInt();
            //将str1 和 str2 补位到len2
            for(int i = str1.length();i<len2;i++){//str1 补 a
                str1.append('a');
            }
             for(int i = str2.length();i<len2;i++){//str2 补'z'+1
                str2.append('z'+1);
            }
            //用于保存字符串相减后每位的差值!
            //便于计算每个长度的个数
            int[] array = new int[len2];
            for(int i = 0;i<len2;i++){
                array[i] = str2.charAt(i) - str1.charAt(i);
            }
            //进行求和!
            int result = 0;
            for(int i = len1;i<=len2;i++){//长度[len1,len2]
                for(int j = 0;j<i;j++){ //计算每一个长度的个数!
                    //进行多少位的相减!
                    result += array[j]*Math.pow(26,i-j-1);// 1位 26^0 2位 26^1 ....
                }
            }
            System.out.println((result-1)%1000007); //减去str2 重复计算!
        }
    }
}