[数据结构与算法]倒计时31天，蓝桥每日刷题（day one）

写在开篇：
黄沙百战穿金甲，不破楼兰终不还！
加油!

第一题 纯质数

解题思路

1，判定质数

public static boolean iszhishu(int n){
  for(int i=2;i<=n/i;i++){
    if(n%i==0){
      return false;
    }
  }
  return true;
}

2，判定是否是纯质数，即判断一下这个数的每一个数位是否为质数，一位一位判断的话，我们已知10以内非质数的是0 , 1，4, 6 ，8, 9，所以

public static boolean check(int n){
  while(n!=0){
    int temp=n%10;
    if(temp==1||temp==4||temp==6||temp==8||temp==9||temp==0)
    return false;
    n/=10;
  }
  return true;
}

完整代码

import java.util.Scanner;

public class Main {
public static boolean iszhishu(int n){
  for(int i=2;i<=n/i;i++){
    if(n%i==0){
      return false;
    }
  }
  return true;
}

public static boolean check(int n){
  while(n!=0){
    int temp=n%10;
    if(temp==1||temp==4||temp==6||temp==8||temp==9||temp==0)
    return false;
    n/=10;
  }
  return true;
}
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int count=0;
        for(int i=2;i<=20210605;i++){
          if(check(i)&&iszhishu(i)){
          count++;
          }
        }
        System.out.println(count);
        scan.close();
    }
}

第二题 最少砝码

解题思路

本篇使用的是三进制解法
想具体了解的，可以参考下面这篇博客
第十二届蓝桥杯省赛JavaB组 试题 G: 最少砝码

完整代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      int n;
        Scanner scan = new Scanner(System.in);
        n=scan.nextInt();
        //本题运用三进制的理解方法，就是n位三进制可以表示的数可以从0——3^n-1，而且中间每个数都可以取到
        int count=1;
        int total=1;
        int weight=1;
        while(total<n){
          count++;
          weight*=3;
          total+=weight;
        }
        System.out.println(count);
        scan.close();
    }
}

第三题 灌溉

解题思路

bfs，直接看代码吧

完整代码

public class 灌溉 {

        static int n, m, t, k;
        static HashSet<Integer> niu = new HashSet<Integer>();
        static HashSet<Integer> old = new HashSet<Integer>();

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            m = sc.nextInt();
            t = sc.nextInt();
            for (int i = 0; i < t; i++) {
                int r = sc.nextInt();
                int c = sc.nextInt();
                niu.add(r * 1000 + c);//经典的坐标分隔
            }
            k = sc.nextInt();
            bfs();
            System.out.println(niu.size());
            sc.close();
        }

        private static void bfs() {
            for (int i = 0; i < k; i++) {
                for (int x : niu) {
                    int r = x / 1000;
                    int c = x % 1000;
                    for (int j = -1; j <= 1; j++) {
                        for (int k = -1; k <= 1; k++) {
                            if (Math.abs(j + k) != 1)//这里指的就是本身这个点不进行操作。
                                continue;
                            if (r + j <= 0 || r + j > n || c + k <= 0 || c + k > m)//因为x和y的坐标都是从1开始的。
                                
                                continue;
                            old.add((r + j) * 1000 + c + k);
                        }
                    }
                }
                niu.addAll(old);
                old.clear();
            }
        }
    }