Bo2SS

Euler-1: Multiples of 3 or 5#

• Idea

  • ① Regular solution: Traverse from 1 to 1000, check if it can be divided by 3 or 5, if so, add to sum
    • Time complexity: O(N)
  • ② Better solution: Directly calculate the sum of multiples of 3 or 5
    • Use arithmetic series, be careful of double counting
      • Formula: (first term + last term) * number of terms / 2
    • Sum of multiples of 3 from 3 to 999 + sum of multiples of 5 from 5 to 1000 - sum of multiples of 15 from 15 to 985
    • Time complexity: O(1)

• Code

• 

Euler-2: Even Fibonacci Numbers#

• Idea

  • Regular solution: Use an array to store previous values, recursively add to sum when even
    • Space complexity: O(N), requires a lot of extra space
  • Better solution: Use two variables to alternate (the teacher mentioned three, but actually only need two)
    • b, c: In each iteration, c = c + b; b = c - b;
    • Space complexity: O(1)

• Code

• 

Euler-4: Largest Palindrome Product#

• Idea
  • Method to determine palindrome numbers
    • Two pointers compare from both ends
    • √ Easier: Reverse the number and then compare
      • Actually, you can just reverse half of the digits, the loop condition is that the reversed number < remaining reversed number
        • But be careful: Odd digit cases; cases where the last digit is 0
  • Enumerate all products of three-digit numbers, check for palindromes, find the maximum
• Code
  • 
  • Use time *./a.out to calculate the time taken for each pair combination

• • j starts from i to avoid duplicate products
  • C++ has a built-in max function
  • Additionally, using short-circuit principles can optimize B, speed can be improved: 0.004s

Euler-6: Difference between the square of the sum and the sum of the squares#

• Idea
  • Simple loop: Calculate the sum of squares from 1 to 100 and the sum, then use the square of the sum - sum of squares
• Code

Euler-8: Largest Product in a Series#

• Idea
  • First, copy the data and save it locally as a string
    • Check the format after copying: remove spaces and newlines
    • Store in an array when reading, convert each digit to a number when reading (- '0')
  • Sliding window method
    • Static window: Fixed window size
    • Dynamic window: Generally referred to as two pointers
  • Solution: Use the sliding window method — static window
    • Only consider the number coming into the window and going out of the window, which can reduce the number of calculations
      • Out: divide
      • In: multiply
      • Be careful if the value is 0
  • Code
    • 
    • The first 13 digits do not contain 0, can calculate now directly
    • Be careful of 0 in the window
      • ❗ Define a counter for 0
      • ❌ Can encountering 0 change the product to 1?
        • No, need to store the product of numbers excluding 0
      • ❌ Can 0 be changed directly to 1? It can reduce the number of checks, only need to check the incoming value for 0
        • But this is not possible, as there may be large numbers between two 0s that do not fill 13 digits
        • For example, 11022340111111111111111111
    • Runtime error: floating point exception
      • Dividing by 0 may cause this error
    • Misestimated the upper bound, 9^13 definitely exceeds the upper limit of int type, so use long long

Euler-11: Largest Product in a Grid#

• Idea
  • Direction array
    • Calculate the coordinates of a number in a certain direction based on the coordinates of a number in the matrix
  • Calculate the product of four consecutive numbers in each direction for a number, find the maximum
    • Calculation problem: Only need to take consecutive four directions to calculate. Avoid duplicate calculations
    • Boundary problem: ① Check boundaries; √② Fill boundaries with 0 (at least 3 circles of 0). Solve the out-of-bounds problem
• Code
  • 
  • Learn to define direction arrays
    • Use variable l to control the l-th position in a certain direction
  • In C language loops, the variable declaration statement is created only once by the compiler. For example, lines 32 and 33
    • Refer to C language repeated variable declaration-CSDN

Euler-14: Longest Collatz Sequence (Memoization Array)#

• 

• Fibonacci Sequence

  • Two methods: Recursion, Iteration
  • Recursion
    • Regular
      • Very slow, due to repeated calculations, but there is an optimized version 👇
    • Use a memoization array
      • Recursion + memoization ≈ Iteration
      • 
      • Before memoization → after: 1.804s → 0.002s
  • Iteration: Fast, but also consumes space, can we use the two variables from euler2 to alternate?
    • Array storage; num[i] = num[i - 1] + num[i - 2];

• Idea

  • Also use recursion + memoization
  • Note the note in the question: after the sequence starts generating, items can exceed one million
  • No extra counter is needed, can add 1 each time calculating the next number

• Code

  • 
  • See annotations for details
    • The larger the num array length, the faster the speed, but the larger the space consumption
    • Use t to record the function result, good to make a check before storing in the array
    • Store the func(ans) value in the main function can speed up

Euler-13: Large Sum (Large Integer Addition)#

• Idea
  • Refer to large integer addition
• Code
  • Refer to large integer addition

➕ Large Integer Addition#

• Large integers: Cannot be stored with long long, generally stored as strings
• ⭐ Array Method
  • 
  • Store large numbers in two arrays in reverse, the first position of the array stores the number of digits of the large number 👉
    • If not stored in reverse, it is difficult to handle when there is a carry in the highest position? It can also be output directly without processing
    • But not storing in reverse will have low position alignment issues, which are difficult to handle
  • Sum the values in each index, the number of digits of the sum takes the maximum of the two large numbers' digits 👉
  • Handle carry, if there is a carry in the last position, remember to add 1 to the number of digits of the sum 👉
  • Output in reverse
• Code
  • 
  • Can ignore the case of carry in the highest position, when there is a carry in the highest position directly output a two-digit number for the first time
    • For example: Input 888 + 222; Output 11 1 0
    • 
    • However, for multiple numbers added together, this may not be universally applicable! Storing one digit per index is the safest

Euler-25: The First Fibonacci Number with 1000 Digits (Large Integer Addition)#

• 

• Idea
  * Loop adding large integers in two variables
  * int num[2] = {1}; // The rest automatically filled with 0

• Code

• 

✖ Large Integer Multiplication#

• Idea
  • Similar to large integer addition
  • The position of the product result of each digit is: i + j - 1
• Code
  • 
  • The element type of the answer array should be at least int
  • The length of the answer array should take the shorter length of possible results
  • Be careful about the position of cumulative multiplication~
• You can try to do Euler problems 16 and 20

➗ Large Integer Division#

• Both the divisor and the dividend are large integers
• Idea
  • 
  • First check if the dividend is greater than the divisor
  • Then keep subtracting the divisor from the dividend until it cannot be subtracted anymore, at most 9 times
  • The divisor can also be a large integer, so the dividend is also a large integer: this can make the code very complex
• You can try HZOJ problems 475 and 476

Euler-15: Lattice Paths (Iteration, General Formula)#

• Idea
  • Method 1: Iteration (Dynamic Programming)
    • 
    • Current number of solutions = number of solutions from above + number of solutions from the left
    • Use the zero-padding method: start storing from point (1, 1)
    • Note the boundary: For a 2 * 2 grid, the top left and bottom right are points (1, 1) and (3, 3)
    • PS: You can also use recursion + memoization, somewhat similar
  • Method 2: Use the general formula, permutations and combinations!
    • For a 2 * 2 grid
    • The total number of steps down and to the right is 4, with 2 steps down and 2 steps to the right
    • This is actually a permutation and combination problem, C(4)2 = 4! / [2! * (4 - 2)!]
    • So this problem is C(40)20
• Code
  • 
  • Method 1 needs to remember to specially handle the first point (1, 1)
  • Method 2 avoids overflow by multiplying and dividing, multiplying first and dividing will not have decimal situations

Euler-18: Maximum Path Sum (Triangle Problem)#

• 

• Idea

  • Iteration (Dynamic Programming)
    • Top-down
      • dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j]
      • Traverse the last row, output the maximum value
    • Bottom-up
      • dp[i][j] = max(dp[i + 1][j + 1], dp[i + 1][j]) + num[i][j]
      • No need to traverse at the end, the topmost is the maximum value
  • Zero-padding!

• Code

  • 
  • The i-th row has i values
  • The main difference between the top-down and bottom-up methods is the determination of the position of the maximum value

HZOJ-590: Tree Tower Rhapsody#

Sample Input

5 3
1
3 8
2 5 0
1 4 3 8
1 4 2 5 0
2 2
5 4
1 1

Sample Output

17
22
-1

• Idea

  • ❌ Each time a special point is processed, recalculate
  • Record the maximum path sum and the second maximum path sum for each point
    • The maximum value obtainable by passing through a certain point: top-down + bottom-up - current value
    • Time and space overhead are both O(N^2)
    • Idea diagram as follows
• 

• Code

  • 
  • 
  • Find the pattern of the maximum path sum passing through a certain point
  • Consider the situation of updating the second maximum value thoroughly
  • Record the coordinates of the maximum value and the second maximum value
  • Check if the banned point is the maximum point or the top left first point
  • Used scanf
    • Faster than cin, see additional knowledge point 2

Euler-22: Name Scores#

• 

• Idea

  • First process the txt file
    • All letters are uppercase
    • Globally replace "," with a space " ", to facilitate data input

:%s /","/ /g

• • Read the string → sort in dictionary order → calculate the letter value of each name, multiply by its position after sorting, get the score → accumulate the score
• Code
  • 
  • Return value of cin
    • istream& type
    • In most cases, its return value is cin itself (non-zero), only when encountering EOF input, the return value is 0
    • Refer to About C++ cin Return Value
  • String class
    • Overloaded less than sign, can directly sort in ascending order
    • Does not support scanf
    • Can use .size() to get string length = number of characters = number of bytes
  • Termination condition can use .size(), or use name[i] to check if it is "\0"
  • Two functions can be directly replaced with two for loops

Euler-32: Pandigital Products#

• 

• Idea

  • Pandigital concept: xx * xxx = xxxx, contains each digit from 1 to 9 exactly once
    • No 0!
  • Avoid duplicate calculations
    • The first number is smaller than the second number
    • First number: range 1 to 100, when it is 100, the second number must be at least 100, and the total number of digits exceeds 9
    • Second number: Stop condition is that the total number of digits of the three numbers exceeds 9
    • Use log10 to determine the number of digits: log10floor + 1
      • For positive numbers, converting to int and flooring has the same effect, flooring and then getting double still needs to convert to int
  • How to determine pandigital
    • <9 does not need to be checked, only =9 needs to be checked, >9 stops
    • Use num[10] to store the state of the 9 digits
  • The product can be obtained from multiple multiplication equations, but only need to sum once
    • Use a marking array, if previously stored, skip

• Code

• 
• 

Euler-33: Digit Cancelling Fractions#

• 

• Idea

  • Interesting
  • There are four non-trivial examples, find the denominator value after the product of the four fractions is simplified
    • Do not consider trivial solutions, i.e., where 0 exists, do not need to consider too detailed, can directly require each digit to be non-zero
  • Both numerator and denominator are two-digit numbers, with the denominator larger than the numerator
    • Numerator: 11 - 99; Denominator: numerator + i
  • Four ways to cancel digits
    • Numerator1 = Denominator1; Numerator1 = Denominator2; Numerator2 = Denominator1; Numerator2 = Denominator2
    • Cross multiplication to check equality before and after cancellation

• Code

  • 
  • Cross multiplication method to check if fractions are equal
  • Use common divisors to get the simplest fraction

Euler-36: Double-base Palindromes#

• 

• Idea

  • Leading zeros: For example, 0012332100, do not count as a palindrome

int num;
cin >> num;
// 00123 is normally read as 123

• • Both decimal and binary can be integrated into N-base

• Code

• 

Euler-30: Sum of the Fifth Powers of Its Digits#

• 

• Idea

  • Key point: What is the maximum range of the sum of the fifth powers?

Let X be the number of digits
The maximum sum of fifth powers is 9^5 * X
The upper limit for X digits is 10^X
Estimate the intersection of the two values, i.e., 9^5 * X = 10^X, X is approximately 5.xxx
So the maximum for X is 6

• • • Enumerate from 10 to 1000000
  • ⭐ Pre-calculate the fifth powers of 1 to 9 and store them!

• Code

  • 
  • The key is the enumeration range!
  • Pre-storing the fifth powers of 1 to 9 avoids duplicate calculations

Euler-34: Sum of Factorials of Its Digits#

• 

• Idea

  • Key point: What is the maximum range of the sum of factorials?

(Same as the previous question)
Let X be the number of digits
The maximum sum of factorials is 9! * X
The upper limit for X digits is 10^X
Estimate the intersection of the two values, i.e., 9! * X = 10^X, X is approximately 6.xxx
So the maximum for X is 7

• • • Enumerate from 10 to 10000000
  • Similarly, ⭐ Pre-calculate the factorials of 1 to 9 and store them!
• Code

Additional Knowledge Points#

• Global variables are automatically initialized to 0
• scanf is faster than cin, refer to
  • cin and cout can be very slow because they need to maintain synchronization with the underlying C library
    • Turning off synchronization will speed it up, but it is still slower than C's input and output functions
  • How much slower is using cin and cout for input and output than using scanf and printf during algorithm competitions?-Zhihu
  • Is scanf() faster than using cin in C++ programs?-Tencent Cloud

Points to Consider#

• Tips#

• The language used is C++, but the differences from C only involve cin and cout

• time ./a.out can display the execution time of the code

Course Notes#