Bo2SS

HZOJ-599: Two Sum 1#

Sample Input

6 15
1 5 6 7 10 26

Sample Output

1 4

• Idea

• Two Pointers

• Array is sorted

• Similarly, for three sums, four sums...

  • Add one more loop

• Code

• 

HZOJ-600: Young Table#

Sample Input

3 4
1 2 3 4
5 6 15 20
7 10 20 25
15

Sample Output

2 3

• Idea
  • Start from the bottom left or the top right
    • Gradually move the x or y coordinate by one unit
    • Time Complexity: O(n + m)
  • Similar to the two-pointer idea from the previous problem~
    • 
    • Conversion between two-dimensional space and one-dimensional space!
• Code
  • 
  • There are still 2 tests that time out, is there a faster method?
    • No, it's due to the fluctuations of the OJ platform.

HZOJ-477: Vowel Letters#

Sample Input

ABCDEFGIKJUMNBZZ

Sample Output

44

• Idea
  • Find the position of the last vowel letter
  • Traverse the positions of the subsequent vowel letters
  • Calculate the distance, update the answer
• Code
  • 
  • Stop when s[i] is \0
  • last initialized to -1, so when finding the first vowel, do not calculate the distance, just update last

HZOJ-479: Ping Pong#

Sample Input

WWWWWWWWWWWWWWWWWWWW
WWLWE

Sample Output

11:0
11:0
1:1
21:0
2:1

• Idea
  • Given a scoring result, output the match results under both 11-point and 21-point systems
    • Output the score for each game
  • According to the input data, each line has at most 25 letters, with a maximum of 2500 lines
    • Get 2500 * 25 points, /11 or /21
    • Get at most 6000 games under the 11-point system, and at most 3000 games under the 21-point system
    • Determine the size of the array to be opened
• Code
  • 
  • cin input rules
    • Input ends when encountering spaces, newlines, and tabs, leaving the end character (Enter, Space, Tab) in the buffer to be ignored at the start of the next cin>>
    • Encountering EOF returns 1

HZOJ-480: Bowling#

Sample Input

/ / / 72 9/ 81 8/ / 9/ / 8/

Sample Output

192

• Idea
  • The key is the text in the red box
  • Three scoring situations
    • Directly clear: 10 points this round + scores from the next two balls
    • Indirectly clear: 10 points this round + scores from the next one ball
    • Not cleared: score for this round
  • One game consists of ten rounds
  • 👌 Use structures
    • Character array: score string corresponding to each round 8/
    • Score after the first throw
    • Score after the second throw: final score for this round, cleverly set according to the problem
    • Flag: which of the above situations it belongs to
• Code
  • 
  • The key is to understand the rules and cleverly use structures!
  • The s array opens 4, originally at most 2 characters + \0, but due to byte alignment, opening 3 or 4 is the same, so open 4
  • In the terminal, use ctrl + d to end the cin loop

HZOJ-481: Curling Competition#

Sample Input

8
5 20 18 19 3 15 13 3
20 2 17 12 5 18 10 11
20 3 4 1 2 11 9 2
1 15 19 9 8 14 11 10
15 2 10 1 19 14 3 18
15 17 21 19 24 32 19 26
-1

Sample Output

0:1
0:0
3:0
3:1

• Idea
  • Who can score: The team whose curling stone is closest to the center can score
  • How many points: Within radius r, how many curling stones from the opposing team closest to the center are within the circle
    • 
    • The green team can score 2 points
    • From Captain Tian's notes~
  • At most 10 rounds, 20 lines + 1
  • First output the score for each round, then the total score
• Code
  • 
  • Using sort makes it easier to find the winning side and score, with little consumption

HZOJ-484: Histogram#

Sample Input

ABC ABC.DEF()G GCC XY
354342aaaCaa aaaaaaaabcdbcd

Sample Output

    *
    *
    *
* * *       *
* * * * * * *                                 * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

• Idea
  • Simple: Count the number of uppercase letters
  • Difficulty: No extra spaces in each line; output by column
  • Process
    • Need to count the number of rows based on the maximum character occurrence
    • Outer loop: from mmax to 1, output * at the character position that meets the condition
      • First get the last character that outputs * in each row, judging from Z to A whether it meets the condition
    • Inner loop: from A to ind, need to count which character is the last in each row
  • Note the output conditions for * and spaces
    • Just check if the character count is greater than the number of * to be output in that row
• Code
  • 
  • The logic needs to be clear~
  • Opening the num array with 130 is clever, corresponding to the ASCII code range, so no need to check while counting
  • The first position check: to avoid extra spaces

HZOJ-485: Equal Distribution of Cards#

Sample Input

4
9 8 17 6

Sample Output

3

• Idea
  • Can only move to adjacent piles
  • First calculate the average, get the expected number of cards in each pile
  • Just adjust to the average from one direction
    • From left to right
    • If not enough, borrowing from the right is fine
    • Essentially the same as adjusting from both directions!
• Code
  • 
  • The last pile of cards does not need to be considered
  • Just update one number on the right, the formula holds whether adding or subtracting

HZOJ-503: Canoeing (Self-made)#

Sample Input

100
9
90
20
20
30
50
60
70
80
90

Sample Output

6

• Idea
  • Sort and then traverse to judge
• Code

HZOJ-504: Delete Numbers ⭐#

Sample Input

179566
4

Sample Output

15

• Idea
  • Large integers
  • Essence: The smaller the number is, the smaller the overall number will be
    • If there are large numbers in front and small numbers behind, delete the large numbers
    • Directly deleting large numbers is not feasible
    • Monotonic stack knowledge? Refer to What is a Monotonic Stack? - Learn algorithms in five minutes
  • Process:
    • Scan the large integer to get the string
      • Use the string class, it can be more convenient to delete numbers
      • string.replace()
    • Traverse every two digits
    • Loop delete s times
    • Output
      • Ignore leading zeros, must have a flag, just check leading zeros, do not omit other zeros
  • Extension: Delete letters to make the dictionary order as small as possible
• Code
  • 
  • ind defaults to the last digit! That is the maximum number, because it is arranged from small to large
  • str.replace operation, refer to std::string::replace - cplusplus
  • Handling leading zeros: define a flag

HZOJ-505: Maximum Integer#

Sample Input

3
121 12 96

Sample Output

9612121

• Idea
  • ⭐ Ensure the dictionary order is maximized after string concatenation
    • Ensure that the connection of any two elements has the preceding dictionary order greater than the latter
    • Use sort
  • Ineffective methods
    • Sort by dictionary order 121 12 96 👉 9612112
    • Compare lengths when the first few digits are the same, shorter goes first 129 12 96 👉 9612129
• Code
  • 
  • String class can use + to concatenate automatically
    • Read in as a string
  • ❗ Change > to >= will cause the second test to time out in oj
    • The difference between the two is whether to return true or false in the case of =, which has nothing to do with the instability of sort itself~
    • ⭐ The cmp function is not simple
      • Must satisfy Strict Weak Ordering
      • 
      • Brief reference STL sort's comp function notes - CSDN
      • Detailed reference A process crash caused by a sort call - Blog
      • 

HZOJ-508: Two People Cross the River#

Sample Input

4
1
5
2
10

Sample Output

17

• Idea
  • Sort first
  • Four cases
    • 1 person
    • 2 people
    • 3 people: the fastest person acts as a helper
    • 4 people
      • ① The speed of passing the flashlight must be the fastest
      • ② The bridge efficiency is highest (when the current is fast and the next is slow)
      • Each time find the fastest situation for two people crossing
      • 
• Code
  • 
  • The clever part is calculating two people at a time, taking the minimum of two methods

HZOJ-509: Intelligence Surfing#

Sample Input

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

Sample Output

9950

• Idea
  • Sort: deduct money, time ← structure
    • First sort by deduction amount (more in front), then by time (less in front)
  • Time period marking array: record the occupancy of each time period
    • Try to complete each task as late as possible
• Code

HZOJ-518: Coins#

Sample Input

10

Sample Output

30

• Idea
  • Two nested loops: how much money to give (1 ~ x); days (1 ~ i)
• Code

HZOJ-513: Floor Numbering#

Sample Input

14 3

Sample Output

12

• Idea
  • Enumerate false floors (1 ~ m), can exist as real floor numbers, then add one
  • There are non-brute force solutions
• Code
  • 
  • Remember to initialize ans~
  • If there is only ++ operation in if, it can be integrated

HZOJ-514: Matchstick Equation#

Sample Input

14

Sample Output

2

• Idea
  • Each number corresponds to a fixed number of matchsticks
  • Range estimation (at most 24 matchsticks)
    • 111 + 111, what is the largest number on the left?
    • Actually, it can also pair with 0 and 1
    • The range will be larger: 0 ~ 2000
    • Addend 1, addend 2 can repeat
  • Brute force enumeration
    • Enumerate two addends, check if the sum meets the requirement 👈 transfer function + brute force function
• Code
  • 
  • Enumeration 👉 transfer 👉 brute force

HZOJ-515: Ratio Simplification#

Sample Input

1498 902 10

Sample Output

5 3

• Idea
  • The range is not large, the upper limit of L is 100
  • Enumerate from small to large
    • Two nested loops
    • No need to check coprimality, if it exists, there must be a satisfying coprime answer before it
  • Enumerate → judge → retain → give the most fitting answer
• Code

HZOJ-516: Cow Inscription#

Sample Input

6
COOWWW

Sample Output

6

• Idea
  • Method 1: Direct enumeration, three nested loops? ❌ Too brute force, O(N ^ 3)
  • Method 2: Space for time
    • For each O, the number of COWs that can be formed = the number of C's before * the number of W's after
    • Scan the array twice, record O(N)
      • Prefix sum: How many C's there are up to this position
      • Suffix sum: How many W's there are after this position
    • Scan the array again, find O O(N)
      • ans + number of C before * number of W after
    • Time: O(N) Space: O(N)
  • Extension: Count PUSH, time complexity O(N ^ 2)
    • Scan twice, count prefix sum P, suffix sum H
    • Find U, then find S, count
    • Refer to the "simultaneous search" technique in the later code, which should also save a suffix sum array space, find S after finding U
• Code
  • 
  • Counting suffix sum "simultaneous search" O saves the space of the suffix sum array
  • Be careful of overflow issues when multiplying int types

HZOJ-517: Number of Triangles#

Sample Input

10

Sample Output

2

• Idea
  • The key is no duplicates of triangles
    • Determine the enumeration method, enumerate by the length of the sides
    • Short side i: 1 ~ n / 3
    • Middle side j: i ~ (n - i) / 2
    • Long side: check if n - i - j < i + j, if true then ans++
  • Once the lengths are determined, duplicates can be avoided
• Code
  • 
  • Enumerate the shortest side → second shortest side, ensuring no duplicates

HZOJ-519: Elegant Numbers#

Sample Input

110 133

Sample Output

13

• Idea
  • Elegant numbers: only one digit is different, the rest are the same
  • Enumeration problem
  • ❌ If directly enumerating and then checking if it is an elegant number, the volume is too large! 10 ^ 16
  • First enumerate elegant numbers YYXYYYYY, then check if they are within the range
    • 5 nested loops
    1. Enumerate Y (a bunch of numbers)
    2. Enumerate X (one number): continue if X equals Y
    3. Enumerate number length: 3 ~ 17
    4. Position of X: 1 ~ number length
       • If X or Y has a 0, there can be no leading zeros
       • If X is 0, X cannot be in the first position; if Y is 0, X must be in the first position
    5. Construct elegant numbers and check if they are within the range
• Code
  • 
  • A clever way to enumerate from a different angle
  • A number can be determined by its digits, length, and position.

Additional Knowledge Points#

• If you need to define super large arrays or have other functions that need to use this array, it is best to define it as a global variable and allocate heap space.

Points to Consider#

• string str; // cin >> str is equivalent to cin >> &str[0]
• ❓ For objects, it is best not to use address operations
  • Pay attention to this later

Tips#

Course Notes#

• HZOJ-506
  • 
  • When outputting, use 1.0 to promote type