Bo2SS

Euler-1: Multiples of 3 or 5#

• Idea

  • ① Ordinary solution: Traverse 1-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 duplicate calculations
      • 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

  • Ordinary 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 a is not needed)
    • 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 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 3-digit numbers, check for palindromes, find the maximum
• Code
  • 
  • Use time *./a.out to calculate the time cost of each pair combination

• • j starts from i to avoid duplicate products
  • C++ has a built-in max function
  • Additionally, using short-circuit principles can also optimize B, speeding it up to: 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, and convert to numbers when reading each digit (- '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 numbers coming in and out of the window, which can reduce the number of operations
      • Out: divide
      • In: multiply
      • Be careful if the value is 0
  • Code
    • 
    • The first 13 digits do not contain 0, so you can directly calculate now
    • Be careful with the case of 0 in the window
      • ❗ Define a counter for 0
      • ❌ Can encountering 0 change the product to 1?
        • No, you need to store the product of numbers excluding 0
      • ❌ Can you directly change 0 to 1? This can reduce the number of checks, only needing 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
    • Use the coordinates of a number in the matrix to deduce the coordinates of numbers in a certain direction
  • Calculate the product of four consecutive numbers in each direction for a number, find the maximum
    • Calculation issue: Only need to take consecutive four directions to calculate. Avoid duplicate calculations
    • Boundary issue: ① 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
    • Reference C language duplicate variable declaration-CSDN

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

• 

• Fibonacci Sequence

  • Two methods: Recursion, Iteration
  • Recursion
    • Conventional
      • Very slow due to duplicate 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 the two variables from euler2 be used to alternate?
    • Store in an array; num[i] = num[i - 1] + num[i - 2];

• Idea

  • Similarly use recursion + memoization array
  • Note in the problem: After the sequence starts generating, items can exceed one million
  • No extra counter is needed; can increment by 1 each time the next number is calculated

• 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, which is good for making a check before storing in the array
    • In the main function, storing the value of func(ans) first can speed up the process

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 using strings
• ⭐ Array method
  • 
  • Store large numbers in two arrays in reverse, with the first position of the array storing 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
    • However, not storing in reverse will have low position alignment issues, which are difficult to handle
  • Sum the values in each index, taking the maximum digit count of the two large numbers 👉
  • Handle carries; if there is a carry in the last position, remember to add 1 to the digit count of the sum 👉
  • Output in reverse
• Code
  • 
  • You can ignore the case of handling the highest position carry; if there is a carry in the highest position, directly output a two-digit number the first time
    • For example: Input 888 + 222; Output 11 1 0
    • 
    • However, for adding multiple numbers, this may not be universally applicable! Storing one-digit numbers in an index is the safest

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

• 

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

• Code

• 

✖ Large Integer Multiplication#

• Idea
  • Similar to large integer addition
  • The position of the product result for 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 the possible result
  • Be careful with the position of cumulative multiplication~
• You can try Euler problems 16 and 20

➗ Large Integer Division#

• Both the divisor and 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 can no longer be subtracted, 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 schemes = number of schemes coming from above + number of schemes coming from the left
    • Zero padding method: Start storing from point (1, 1)
    • Note the boundary: For a 2 * 2 grid, the upper left and lower right corners are points (1, 1) and (3, 3)
    • PS: You can also use recursion + memoization, which is somewhat similar
  • Method 2: Use a general formula, combinatorics!
    • 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 combinatorial 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)
  • In method 2, multiplying and dividing simultaneously will not go out of bounds; multiplying first and then 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]
      • Finally, no need to traverse, the topmost value is the maximum
  • 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
    • Both time and space overhead are O(N^2)
    • The idea diagram is 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
  • Determine if the banned point is the maximum point or the first point in the upper left corner
  • 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 lexicographical order → calculate the letter value of each name, multiply by its position after sorting, obtain the score → accumulate the score
• Code
  • 
  • The return value of cin
    • istream& type
    • In most cases, its return value is cin itself (non-zero value), only when encountering EOF input, the return value is 0
    • Reference About C++ cin return value
  • String class
    • Overloaded the less-than operator, can directly sort from small to large
    • Does not support scanf
    • You can use .size() to get string length = character count = byte count
  • Termination conditions 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-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 when 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 gives the same effect; flooring and then getting double still needs to be converted 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 needs to be summed once
    • Use a marking array; if it has been stored before, skip it

• 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., when 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
    • Check equality before and after cancellation: Cross multiplication

• Code

  • 
  • Cross multiplication method to check if fractions are equal
  • Use common divisors to obtain 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: Digit Fifth Powers#

• 

• Idea

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

Let X be the number of digits
Its maximum sum of fifth powers is 9^5 * X
X digit upper limit 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 X is 6

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

• Code

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

Euler-34: Digit Factorials#

• 

• 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
Its maximum factorial sum is 9! * X
X digit upper limit is 10^X
Estimate the intersection of the two values, i.e., 9! * X = 10^X, X is approximately 6.xxx
So the maximum 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, reference
  • The performance of cin and cout can be very slow because they need to maintain synchronization with the underlying C library
    • Turning off synchronization can speed it up, but it is still not as fast as C's input and output functions
  • How much slower is using cin and cout for input and output compared to scanf and printf during algorithm competitions?-Zhihu
  • Is using scanf() faster than using cin in C++ programs?-Tencent Cloud

Points for Consideration#

• Tips#

• The programming language 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#