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 layer of 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 corner or from the top right corner
    • Gradually move one unit in the x or y direction
    • Time Complexity: O(n + m)
  • Similar to the two-pointer idea from the previous problem~
    • 
    • Conversion between two-dimensional 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 and update the answer
• Code
  • 
  • Stop when s[i] is \0
  • last initialized to -1, so that when the first vowel is found, the distance is not calculated, only last is updated

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 symbol (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 part 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
  • Use ctrl + d in the terminal 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 stones are closest to the center can score
  • How many points: within radius r, how many stones of the scoring team are within the circle formed by the opponent's closest stones to the center
    • 
    • 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 output 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 positions that meet the condition
      • First get the last character that outputs * in each row, checking from Z to A to see if it meets the condition
    • Inner loop: from A to ind, need to count which is the last character in each row
  • Note the output conditions for * and spaces
    • Just check if the character count is greater than the required number of * to be output in that row
• Code
  • 
  • The logic needs to be clear~
  • Opening the num array to 130 is clever, corresponding to the ASCII code range, so no need to check during 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 to get the expected number of cards in each pile
  • Just gather to the average from one direction
    • From left to right
    • Borrow if not enough, it's fine if the right side becomes negative
    • Essentially the same as gathering 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 (Do it Yourself)#

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 the algorithm in five minutes
  • Process:
    • Scan the large integer to get the string
      • Use the string class, it can be 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 that the dictionary order after string concatenation is maximized
    • Ensure that for any two elements, the concatenation of the former is greater than the latter
    • Use sort
  • Ineffective methods
    • Sort by dictionary order 121 12 96 👉 9612112
    • For the same high digits, judge length, the shorter one goes first 129 12 96 👉 9612129
• Code
  • 
  • The string class can use + to concatenate automatically
    • Read in as a string
  • ❗ Change > to >= in OJ, the second test will time out
    • The difference between the two is whether = returns true or false in the case, which is unrelated to 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 to a process crash caused by an STL 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 the person carrying the flashlight must be the fastest
      • ② The efficiency of crossing the bridge is highest (when the fast and slow are very different)
      • Each time find the fastest situation for two people crossing
      • 
• Code
  • 
  • The clever part is calculating in pairs, taking the minimum of the two methods

HZOJ-509: Intellectual 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 occupation situation of each time period
    • Try to complete each task as late as possible
• Code

HZOJ-518: Gold 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 is a non-brute force solution
• Code
  • 
  • Remember to initialize ans~
  • If there is only ++ operation in if, it can be combined

HZOJ-514: Matchstick Equation#

Sample Input

14

Sample Output

2

• Idea
  • The number of matchsticks corresponding to each number is fixed
  • Estimate the range (at most 24 matchsticks)
    • 111 + 111 what is the largest number on the left?
    • Actually, it can also be paired with 0, 1
    • The range will be larger: 0 ~ 2000
    • Addend 1, addend 2 can be repeated
  • 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 coprimeness, if it exists, there must be a previous coprime answer that satisfies the condition
  • 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 up to this position
      • Suffix sum: how many W's from this position
    • Scan the array again to find O O(N)
      • ans + number of C's before * number of W's 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, finding 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 duplicate triangles
    • Determine the enumeration method, enumerate by the smallest side
    • 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 smallest side is determined, duplicates can be avoided
• Code
  • 
  • Enumerate the shortest side → second shortest side to ensure 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 enumerating directly and then checking if it's 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): if X equals Y, then continue
    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
  • 
  • Cleverly 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 that 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
  • This should be noted later

Tips#

Course Summary#

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