during the exam weekend, find something to do,

  updating...

#A pure prime

Total score of this question: 5 points

Problem description

  if a positive integer has only 1 1 1 and its two divisors are called a prime number (also known as prime number).
  the first prime numbers are: 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , ⋅ ⋅ ⋅ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 2,3,5,7,11,13,17,19,23,29,31,37,⋅⋅⋅ .
  if all decimal digits of a prime number are prime, we call it pure prime. For example: 2 , 3 , 5 , 7 , 23 , 37 2, 3, 5, 7, 23, 37 2, 3, 5, 7, 23 and 37 are pure prime numbers, and 11 , 13 , 17 , 19 , 29 , 31 11, 13, 17, 19, 29, 31 11, 13, 17, 19, 29, 31 are not prime numbers. of course 1 , 4 , 35 1, 4, 35 1, 4 and 35 are not pure prime numbers.
  excuse me, where is it 1 1 1 to 20210605 20210605 How many prime numbers are there in 20210605?

Answer submission

  this is a question filled in with results. You just need to calculate the results and submit them. The result of this question is an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

1903

Enumerate in order

  a simple idea, making a watch [ 1 , 20210605 ] [1,20210605] For prime numbers between [120210605], conduct an additional pure prime number test and accumulate the results.

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static final int N = 20210605;

    public static void main(String[] args) {
        boolean[] marked = new boolean[N + 1];
        List<Integer> primes = new ArrayList();
        marked[0] = marked[1] = true;
        int ans = 0;
        for (int i = 2; i <= N; i++) {
            if (!marked[i]) {
                primes.add(i);
                boolean flag = false;
                for (int k = i; k > 0; k /= 10)
                    if (flag = marked[k % 10]) break;
                if (!flag) ans++;
            }
            for (int p : primes) {
                if (p * i > N)  break;
                marked[p * i] = true;
                if (i % p == 0) break;
            }
        }
        System.out.println(ans);
    }
}

Bitwise enumeration

  in the simple solution, we will find that many splits are not necessary to judge whether a prime number is a pure prime number, because in [ 0 , 10 ) [0,10) In [0,10), prime numbers only account for { 2 , 3 , 5 , 7 } \{2,3,5,7\} {2,3,5,7} four digits. If we only judge whether the number composed of these four numbers is a prime number, can the performance be further improved?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {

    public static final int N = 20210605;

    public static int[][] digits = new int[8][4];

    public static void main(String[] args) {
        boolean[] primes = new boolean[N + 1];
        List<Integer> helper = new ArrayList();
        Arrays.fill(primes, 2, N, true);
        int ans = 0;
        for (int i = 2; i <= N; i++) {
            if (primes[i]) helper.add(i);
            for (int p : helper) {
                if (p * i > N)  break;
                primes[p * i] = false;
                if (i % p == 0) break;
            }
        }
        digits[0] = new int[]{2, 3, 5, 7};
        for (int k = 1; k < 7; k++)
            for (int i = 0; i < 4; i++)
                digits[k][i] = digits[k - 1][i] * 10;
        digits[7] = new int[]{ digits[6][0] * 10 };
        System.out.println(dfs(primes, 0, 0));
    }

    public static int dfs(boolean[] primes, int k, int depth) {
        if (depth == 8) return k <= N && primes[k] ? 1 : 0;
        int ans = primes[k] ? 1 : 0;
        for (int a : digits[depth])
            ans += dfs(primes, k + a, depth + 1);
        return ans;
    }
}

  in fact, the performance has not been further improved, and the amount of code has increased.

  this is because ( 1 , N ] (1,N] (1,N] the prime number in this range is about N ln ⁡ N \cfrac{N}{\ln N} lnNN, and the number of bitwise components that may be pure prime numbers is about 4 ln ⁡ N 4^{\ln N} 4lnN, which is obviously not a value-added level.

#B full date

Total score of this question: 5 points

Problem description

  a date is called a complete date if the sum of the numbers of month, year and day in a date is a complete square number.
  for example: 2021 2021 2021 6 6 June 5 5 The sum of the figures on the 5th is 2 + 0 + 2 + 1 + 6 + 5 = 16 2 + 0 + 2 + 1 + 6 + 5 = 16 2 + 0 + 2 + 1 + 6 + 5 = 16, and 16 16 16 is a perfect square number, which is 4 4 Square of 4. therefore 2021 2021 2021 6 6 June 5 5 The 5th is a full date.
  for example: 2021 2021 2021 6 6 June 23 23 The sum of the figures on the 23rd is 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16, which is a complete square number. therefore 2021 2021 2021 6 6 June 23 23 The 23rd is also a full date.
  excuse me, from 2001 2001 2001 1 1 January 1 1 1 to 2021 2021 2021 12 12 December 31 31 How many full dates are there in 31 days?

Answer submission

  this is a question filled in with results. You just need to calculate the results and submit them. The result of this question is an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

977

A complete victory for the Java party

  LocalDate is easy to use.

Naive solution

  enumeration [ 2001 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 31] the time in this interval is judged and then accumulated.

import java.time.LocalDate;

public class Test {

    public static final int maxPerfect = 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9;

    public static final boolean[] perfect = new boolean[maxPerfect + 1];

    public static LocalDate start = LocalDate.of(2001, 01, 01);

    public static LocalDate end = LocalDate.of(2021, 12, 31);

    public static void main(String[] args) {
        int count = 0;
        for (int i = 1; i * i<= maxPerfect; i++)
            perfect[i * i] = true;
        while (end.compareTo(start) >= 0) {
            if (perfect[calc(start)])
                count++;
            start = start.plusDays(1);
        }
        System.out.println(count);
    }

    public static int calc(LocalDate date) {
        String dateStr = date.toString();
        int res = 0;
        for (int i = dateStr.length() - 1; i >= 0; i--)
            if (Character.isDigit(dateStr.charAt(i)))
                res += Character.digit(dateStr.charAt(i), 10);
        return res;
    }
}

Simple improvement

  in [ 2001 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 31], there is not only a maximum value for the sum of the digits 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32, there is also a minimum value 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1, that is, the possible complete square number is nothing more than 3 × 3 3 × 3 3×3, 4 × 4 4 × 4 4×4, 5 × 5 5 × 5 five × 5 three, let's simplify our code at this point.

import java.time.LocalDate;

public class Test {

    public static LocalDate start = LocalDate.of(2001, 01, 01);

    public static LocalDate end = LocalDate.of(2021, 12, 31);

    public static void main(String[] args) {
        int count = 0;
        while (end.compareTo(start) >= 0) {
            if (isPerfect(start)) count++;
            start = start.plusDays(1);
        }
        System.out.println(count);
    }

    public static boolean isPerfect(LocalDate date) {
        String dateStr = date.toString();
        int sum = 0;
        for (int i = dateStr.length() - 1; i >= 0; i--)
            if (Character.isDigit(dateStr.charAt(i)))
                sum += Character.digit(dateStr.charAt(i), 10);
        return sum == 3 * 3 || sum == 4 * 4 || sum == 5 * 5;
    }
}

Implementation independent of API

  first count the occurrence times of the sum of the digits of the month and date in a normal year, and then judge whether it is a leap year when traversing the year.

public class Test {

    public static void main(String[] args) {
        int[] bigMonth = { 1, 3, 5, 7, 8, 1 + 0, 1 + 2 };
        int[] smallMonth = { 4, 6, 9, 1 + 1 };
        int[] calendar = new int[9 + 2 + 9 + 1];
        int ans = 0;
        for (int day = 1; day <= 31; day++)
            for (int month : bigMonth)
                calendar[month + calc(day)]++;
        for (int day = 1; day <= 30; day++)
            for (int month : smallMonth)
                calendar[month + calc(day)]++;
        for (int day = 1; day <= 28; day++)
            calendar[2 + calc(day)]++;
        for (int year = 2001; year <= 2021; year++) {
            if (isLeapYear(year))
                if (isLeapYear(year + 2 + 2 + 9)) ans++;
            for (int i = 0; i < calendar.length; i++) {
                if (calendar[i] == 0) continue;
                if (isPerfect(calc(year) + i))
                    ans += calendar[i];
            }
        }
        System.out.println(ans);
    }

    public static int calc(int n) {
        int res = 0;
        do
            res += n % 10;
        while ((n /= 10) > 0);
        return res;
    }

    public static boolean isPerfect(int num) { return num == 3 * 3 || num == 4 * 4 || num == 5 * 5; }

    public static boolean isLeapYear(int year) { return year % 100 == 0 ? year % 400 == 0 : year % 4 == 0; }
}

#C minimum weight

Total score: 10 points

Problem description

  for a rooted binary tree T T T. Xiaolan defines the weights of the nodes in the tree W ( T ) W(T) W(T) is as follows:
  the weight of empty subtree is 0 0 0.
  if a node v v v has left subtree L L 50. Right subtree R R R. Respectively C ( L ) C(L) C(L) and C ( R ) C(R) C(R) nodes, then W ( v ) = 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) W(v) = 1 + 2W(L) + 3W(R) + (C(L))^{2} C(R) W(v)=1+2W(L)+3W(R)+(C(L))2C(R).
   the weight of the tree is defined as the weight of the root node of the tree.
  Xiaolan wants to know that for a tree 2021 2021 For a binary tree with 2021 nodes, what is the minimum weight of the tree?

Answer submission

  this is a question to fill in the blank. You just need to calculate the result and submit it. The result of this question is an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

2653631372

dynamic programming

  according to the meaning of the topic, it is obvious that N = 2021 N = 2021 N=2021， W ( 0 ) = 0 W(0) = 0 W(0)=0， W ( N ) = min ⁡ { 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) } W(N) = \min \{1 + 2W(L) + 3W(R) + (C(L))^{2}C(R)\} W(N)=min{1+2W(L)+3W(R)+(C(L))2C(R)}, where L + R = N − 1 L + R = N - 1 L+R=N−1， 0 ≤ L ≤ R ≤ N 0 \leq L \leq R \leq N 0≤L≤R≤N.

  the state transition equation is on your face: d p ( y ) = { 0 i = 0 min ⁡ { 1 + 2 d p ( l ) + 3 d p ( r ) + l 2 r } l + r = i − 1 ， 0 ≤ l ≤ r ≤ i dp(y)=\left\{ \begin{array}{lr} 0&i = 0\\ \min \{1 + 2dp(l) + 3dp(r) + l^{2}r\}&l + r = i - 1，0 \leq l \leq r \leq i \end{array} \right. dp(y)={0min{1+2dp(l)+3dp(r)+l2r} i=0l+r=i − 1, 0 ≤ L ≤ R ≤ i     is also a sign in question.

public class Test {

    public static final int N = 2021;

    public static void main(String[] args) {
        long[] dp = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            dp[i] = Long.MAX_VALUE;
            for (int l = i >> 1; l >= 0; l--)
                dp[i] = Math.min(dp[i],
                    1 + 2 * dp[l] + 3 * dp[i - l - 1] + l * l * (i - l - 1));
        }
        System.out.println(dp[N]);
    }
}

#D coverage

Total score: 10 points

Problem description

  Xiaolan has a chess board, the size of which is 8 × 8 8 × 8 eight × 8, i.e 8 8 8 lines 8 8 8 trains in total 64 64 64 squares. There are beautiful patterns on the chessboard, so the chessboard is different from the original chessboard after rotation.
  Xiaolan has many identical pieces of paper. Each piece of paper can cover two adjacent squares of the chessboard. Xiaolan wants to use it 32 32 32 pieces of paper just cover the chessboard completely, and each piece of paper covers two squares.
  Xiaolan found that there are many schemes to achieve such coverage. If the chessboard is relatively small, the number of schemes is relatively easy to calculate, for example, when the chessboard is 2 × 2 2 × 2 two × There are two schemes when the chessboard is 4 × 4 4 × 4 four × 4 sometimes 36 36 36 schemes. But Xiao Lan can't figure out his own one 8 × 8 8 × 8 eight × How many coverage schemes are there on the chessboard of 8.
  please help Xiao Lan figure out for this 8 × 8 8 × 8 eight × How many coverage schemes are there on the chessboard of 8.

Answer submission

  this is a question filled in with results. You just need to calculate the results and submit them. The result of this question is an integer. When submitting the answer, only fill in this integer. If you fill in the redundant content, you will not be able to score.

2653631372

Pressure DP

  it's late at night. It's time to go to bed.