蓝桥杯31天冲刺打卡题解（Day1）

Day1

第一题

第十二届2021年国赛

C++B组第2题

填空题

纯质数

只有每一位是由

2，3，5，7

凑成的质数才是纯质数。

publicclassMain{publicstaticvoidmain(String[] args){int cnt =0;for(int i =2; i <=20210605; i++){if(check(i)&&isPrime(i)) cnt++;}
        System.out.println(cnt);}// 求质数 O(sqrt(n))会快很多privatestaticbooleanisPrime(int n){for(int i =2; i <= Math.sqrt(n); i++){if(n % i ==0)returnfalse;}returntrue;}// 将不满足纯质数的条件筛出去privatestaticbooleancheck(int n){while(n !=0){// 枚举每一位判断int temp = n %10;if(temp ==0|| temp ==1|| temp ==4|| temp ==6|| temp ==8|| temp ==9)returnfalse;
            n /=10;}returntrue;}}

第二题

第十二届2021年省赛

JavaB组第7题

找规律/贪心思想

最少砝码

天平是两边都可以放砝码的，我们表示重量不仅仅是放在一边相加重量，我们可以用一边减去另一边的重量来表示，选择更少的砝码来贪心的表示更大的范围。

n

是需要称出

1 ~ n

的重量。

当

n == 1

时，只用1个重量为1的砝码即可。

当

n == 2

时，我们可以用2个重量为1的砝码，但我们可以基于贪心的思想，第1个用重量为1的砝码，第2个用重量为3的砝码，，

3 - 1 = 2

，此时也可以表示

3 + 1 = 4

，所以可以表示

(1, 2, 3, 4)

这四个重量，最大可以表示的重量是4。

当

n == 5

时，就需要用3个砝码了，同样基于贪心，

9 - 3 - 1 = 5

，此时第3个砝码重量我们选择9，

9 + 3 + 1 = 13

，最大可以表示的重量是13。

当

n == 14

时，用4个砝码，

27 - 13 = 14

，此时第4个砝码选择27。

此时我们已经找到砝码选择的规律，就是

    (
   
   
    
     3
    
    
     0
    
   
   
    ,
   
   
    
     3
    
    
     1
    
   
   
    ,
   
   
    
     3
    
    
     2
    
   
   
    .
   
   
    .
   
   
    .
   
   
    
     3
    
    
     k
    
   
   
    )
   
  
  
   (3^{0},3^{1},3^{2}... 3^{k})
  
 
(30,31,32...3k)

公式：下一个砝码重量 - 当前所有砝码能表示的最大重量 = 当前砝码表示不出来的最小数量

import java.util.Scanner;publicclassMain{publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);int n = sc.nextInt();int cnt =1, weight =1, sum =1;// 砝码个数 选择的砝码重量 砝码最大能表示的重量while(true){if(sum >= n)break;    
            weight *=3;// 1 3 9 27
            sum += weight;// 1 4 13 27
              cnt++;}
        System.out.print(cnt);}}

第三题

2021年模拟赛

灌溉

bfs模板。

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;publicclassMain{staticfinalint N =110;staticint[][] a =newint[N][N];staticint n, m, T;static Queue<PII> q =newLinkedList<>();// 灌溉队列publicstaticvoidmain(String[] args){
        Scanner sc =newScanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        T = sc.nextInt();while(T-->0){int x = sc.nextInt(), y = sc.nextInt();int k = sc.nextInt()-1;while(k-->0){bfs(x, y);}}int cnt =0;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(a[i][j]==1) cnt++;}}

        System.out.print(cnt);}privatestaticvoidbfs(int sx,int sy){int[] dx =newint[]{-1,0,1,0}, dy =newint[]{0,1,0,-1};while(T-->0){
            a[sx][sy]=1;// 水管处已经灌溉好
            q.offer(newPII(sx, sy));while(!q.isEmpty()){
                PII t = q.poll();for(int i =0; i <4; i++){int x = t.x + dx[i], y = t.y + dy[i];if(x <0|| x >= n || y <0|| y >= n)continue;// 出界if(a[x][y]==1)continue;// 已被灌溉
                    a[x][y]=1;
                    q.offer(newPII(x, y));}}}}staticclassPII{int x;int y;publicPII(int x,int y){this.x = x;this.y = y;}}}