Bo2SS

Default based on C++11 standard

0228#

Implementing a Complex Number Class in C++#

Requirements:
(1) Ensure data safety
(2) Assign values to the real and imaginary parts directly through the constructor
(3) Complete addition, subtraction, multiplication, and division operations for complex numbers

Analyze Requirements#

(1): All data should be defined as private type

(2): Initialization list can be used

(3): Pay attention to division details

Code Implementation#

• Familiarize with initialization lists, operator overloading, friend functions, etc.
• Division operation details
  • Rationalizing the denominator [The numerator's complex multiplication can utilize the implemented complex multiplication operation]
  • Division may produce decimals, so the data type within the class should directly use double type
• Integrate test cases to simplify the testing process
• [PS] The logic for friendly output of complex numbers is not aesthetically pleasing; it's unclear if there is a better way to determine positive or negative.

Test Results#

• Mainly test operations between real numbers, pure imaginary numbers, integer complex numbers, and decimal complex numbers
• Calculation results are correct and generally meet the above requirements

0227#

Usage and Techniques of nth_element Function#

Usage#

Header file: <algorithm>

🔺 void nth_element

(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

• Function: Correctly sorts a specific element within a range
  • Rearranges the elements in the range $[first, last)$ so that the element at the nth position is exactly the element that would be at index nth if the range were sorted in ascending order
• Parameter list
  • first​, last: Random access iterators RandomAccessIterator for the start and end positions of the sequence to be processed [excluding the element at the end position]
  • nth: The random access iterator RandomAccessIterator for the element that you want to be correctly sorted
• PS
  • All pointers are valid RandomAccessIterator
  • Correctly sorted: Its position index matches its size order
  • Other elements have no specific order, but within the range $[first, last)$, all elements to the left of nth​ are $\le$ it, and all elements to the right are $\ge$ it

🔺 void nth_element

(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

• Adds parameter comp​: for custom sorting rules
  • bool cmp(const Type1 &a, const Type2 &b);
  • From C++11 onwards, using Type1 & and Type1 is not allowed
  • ❗ Defines the less-than rule, corresponding to sorting from smallest to largest
  • When passing this parameter, it can be either a function pointer or a function object

Techniques#

• When not all elements need to be sorted, but only the element at a certain sorted position needs to be extracted, using this method saves time

• Average time complexity: $O(N)$

• Based on Quick Select Algorithm — Zhihu: It borrows the partition process from quicksort but does not sort the entire sequence

⭕ Reference std::nth_element — cplusplus

Basic Operations of string#

Including find / insert / substr functions and three additional methods
string is a class; header file: <string>

find#

🔺 size_t find (const string& str, size_t pos = 0) const;

• Function: Search within a string
  • Starting from the pos position of the string that calls this method, search and return the index of the first occurrence of the string str
• Parameter list
  • str: The string to search for
  • pos: The starting position for the search; defaults to 0, searching the entire string
• Return value: If not found, returns string::npos
• PS
  • Similarly, can search for char *, char types
  • The rfind() method searches from the end, with pos defaulting to npos

insert#

🔺 string& insert (size_t pos, const string& str);

• Function: Insert into a string
  • Inserts the additional string str before the pos position of the string that calls this method
• Parameter list
  • pos: The position to insert, starting from 0
  • str: The string to insert
• Return value: A reference to the string being inserted, so this operation is done in place
• PS: The inserted string is a copy

substr#

🔺 string substr (size_t pos = 0, size_t len = npos) const;

• Function: Generate a substring
  • Returns a copy of a substring of the string that calls this method, starting from the pos position and taking len length [or until the end of the string]
• Parameter list
  • pos: The position of the first character to be copied from the substring
  • len: The length of the substring to copy [note the length of the original string]
• PS: len defaults to npos, indicating that the substring goes directly to the end of the string

replace#

🔺 string& replace (size_t pos, size_t len, const string& str);

• Function: Replace a part of the string
  • Replaces a part of the string that calls this method, starting from the pos position and taking len length, with the string str
• Parameter list
  • pos: The position of the first character in the original string to be replaced
  • len: The length of the part to be replaced [same as substr, note the length of the original string]
  • str: The string to replace with
• Return value: The original string itself
• PS: The string str will be copied before replacement

size#

🔺 size_t size() const noexcept;

• Function: Return the length of the string [unit: bytes]
• PS
  • Does not count the trailing null character '\0'
  • Synonymous with the length() method

c_str#

🔺 const char* c_str() const noexcept;

• Function: Obtain an equivalent C-style character array
  • Returns a pointer to an equivalent character array, which includes a null character '\0' at the end of the array
• PS: In C++11, synonymous with the data() method

at#

🔺 char& at (size_t pos); const char& at (size_t pos) const;

• Function: Return a reference to the character at position pos in the string
• Parameter pos: The index of the character to retrieve, starting from 0
• PS: Compared to the subscript operator [], this method
  • Checks if the index is valid; if not, it throws an out_of_range exception
  • The position of the trailing '\0' character is invalid

⭕ Reference std::string — cplusplus

Relationship Between HZOJ-287 Merging Fruits and Huffman Coding#

Huffman Coding Process#

1. First, count the probability of each character $p_i\ |\ 1\le i\le n$
2. Build a Huffman tree with the $n$ characters
   • Each time, take the two characters with the smallest probabilities as nodes $p_{min1}$, $p_{min2}$, merge them to form a new node $p_j$ [ $=p_{min1}+p_{min2}$ ]
   • Continue the previous step among the remaining nodes, merging $n-1$ times until only one node remains, completing the tree construction
3. Read the encoding in some form [e.g., left branch 0, right branch 1], obtaining the encoding $code_i$ for each character

⭐ Moreover, since Huffman coding is the optimal variable-length coding, the average coding length $\sum_{i=1}^n(len(code_i)\times p_i)$ is minimized

[PS] $len(code_i)$ represents the length of the encoding $code_i$

HZOJ-287#

According to the problem description, the steps to solve should be:

1. Given the weight of each pile of fruits $w_i\ |\ 1\le i\le n$ [equivalent to the stamina consumed]
2. Merge the $n$ piles of fruits in pairs according to the above rules
   • It is important to understand that the $i$-th pile of fruits may be merged multiple times
   • Assuming the $i$-th pile of fruits has undergone $time_i$ merges, the total stamina consumed is $\sum_{i=1}^n(time_i\times w_i)$

⭐ The problem requires minimizing the total stamina consumed, i.e., minimizing $\sum_{i=1}^n(time_i\times w_i)$

Further Observation#

【Optimization Targets of Both】

1. Huffman Coding — Average coding length: $\sum_{i=1}^n(len(code_i)\times p_i)$

2. HZOJ-287 — Total stamina consumed: $\sum_{i=1}^n(time_i\times w_i)$

❗ Let $time_i$ correspond to $len(code_i)$, and $w_i$ correspond to $p_i$; the two formulas are completely consistent

And Huffman coding can minimize its optimization target; similarly, the idea of Huffman coding can be used to minimize the optimization target of HZOJ-287

👉 The larger the pile of fruits $w_i$, the later it should be merged, i.e., keep the corresponding $time_i$ as small as possible

👉👉 Merging principle: Each time, take the two piles of fruits with the smallest weights $w_{min1}$, $w_{min2}$ to merge

In summary, the process of merging fruits in HZOJ-287 is essentially a Huffman coding process!