DOCSEARCHbyAlgolia
Submit Docs

Linho's Learning Notes

website·Indexed 31 days ago

https://notes.linho.cc

A collection of personal study notes covering competitive programming algorithms (Graph Theory, String Hashing, Manacher, AC Automaton, KMP, Tarjan), C++ language fundamentals (const, tuple types, cout formatting), mathematics (Order Theory, Chinese Remainder Theorem, Linear Algebra), and high school physics.

Tokens
280K
Snippets
570
Records
1.9K
Agent score
50%

What's inside Linho Notes

  1. Overview of algorithm competitions for CS undergraduates

    Key competitions for students interested in competitive programming include:

    • Freshman Contest (新生赛): Single-person event in November; top performers often gain entry to the university team.
    • University Contest (校赛): Single-person event in April/May; open to all undergraduates.
    • XCPC (ICPC and CCPC): Three-person team competitions. ICPC regional gold medals are highly valued for academic distinctions.
    • Shaanxi Provincial Programming Contest: Three-person team event, generally lower entry barrier, useful for comprehensive evaluation points.
    • CCF-CSP Certification: A single-person certification (500-point scale) held four times a year. Scores of 300+ are beneficial for postgraduate recommendation (保研) summer camps.

  2. Overview of CS undergraduate competitions at XDU

    Common competitions for CS students include:

    • Spark Cup (星火杯): A XDU-specific competition for freshmen held 1-2 months after admission; beginner-friendly.
    • Mathematical Modeling (数学建模): High cost-performance for points. Includes school competitions (May), National competitions (September), and MCM/ICM (February). Elective courses and training camps are available.
    • Mathematics Competition (数学竞赛): Preliminaries usually in November. Non-math majors focus on Higher Mathematics.
    • English Competition (大学生英语竞赛): Usually held around April/May.
    • ACM/ICPC: High barrier to entry. Most top performers have prior NOIP experience. Benefits include scholarships, Baoyan points, and big-tech offers, but requires significant time investment compared to GPA or internships.

  3. Overview of Weight Segment Trees (Value Range Segment Trees)

    A Weight Segment Tree (or Value Range Segment Tree) is a variation of a segment tree where the nodes represent the frequency of values within a specific range (value domain) rather than indices of an array. While a standard segment tree might maintain the sum of a subarray, a Weight Segment Tree maintains the count of elements appearing within a specific value range. Because the value domain can be extremely large, these trees typically require discretization or dynamic node allocation to manage memory.

  4. Overview of the founding of the Communist Party of China (CPC)

    The Communist Party of China was formally established during its First National Congress, held from July 23 to August 3, 1921. From its inception, the party defined socialism and communism as its primary struggle goals. Li Dazhao played a primary role in the early dissemination of Marxist thought in China.

  5. Overview of Global Navigation Satellite Systems (GNSS)

    GNSS (Global Navigation Satellite System) provides positioning, navigation, and timing services by extending control points from the ground to space. The four major global systems are:

    • GPS (USA)
    • GLONASS (Russia)
    • Galileo (EU)
    • BeiDou/BDS (China)

    Regional systems, such as QZSS (Japan) and IRNSS (India), provide additional regional enhancement services.

  6. Overview of Prüfer Sequences

    A Prüfer sequence is a unique integer sequence used to represent a labeled tree with $n$ nodes. It establishes a bijection between labeled trees of $n$ nodes and sequences of length $n-2$ where each element is an integer from the set $[1, n]$. This representation is primarily used in combinatorial counting problems and to prove Cayley's formula.

  7. Overview of Intersection Methods for Point Determination

    Intersection methods are used to calculate the coordinates of a target point by observing angles and distances from known control points. This is typically used to add new control points in partially obstructed areas after a control traverse has been established. The fundamental process involves determining the relationship between direction and side length, then converting these into coordinate increments.

  8. Overview of Non-rotating Treaps

    Non-rotating Treaps (also known as Split-Merge Treaps) avoid rotations and instead rely on two core operations: Split and Merge. This architecture makes them naturally suited for maintaining sequences and implementing persistence. A 'Split by Value' operation divides a Treap into two: one containing all nodes with values less than or equal to a key, and another containing all nodes with values greater than the key.

  9. Overview of Remainder Shortest Path technique

    The Remainder Shortest Path technique is used to solve problems where you need to find how many integers can be formed by a set of given integers (with repetition), the smallest/largest integer that cannot be formed, or the minimum number of operations to reach a value with a specific remainder. It optimizes space complexity by constructing states based on modulo arithmetic, treating these states as nodes in a single-source shortest path problem. The state transition typically follows the form: $dist[ (i + w) mod M ] = ext{min}(dist[ (i + w) mod M ], dist[i] + w)$.

  10. Overview of Heavy-Light Decomposition (HLD)

    Heavy-Light Decomposition is a technique used to decompose a tree into several disjoint chains (heavy chains) to maintain information on tree paths. By transforming the tree into a linear structure, it allows the use of sequence-based data structures (like Segment Trees or Fenwick Trees) to perform path updates and queries efficiently.

    Key capabilities include:

    1. Modifying all node values on a path between two nodes.
    2. Querying path sums, maximums, or other mergeable information between two nodes.
    3. Efficiently finding the Lowest Common Ancestor (LCA).

  11. Overview of Manacher's Algorithm for Palindromic Substrings

    Manacher's Algorithm is used to find all palindromic substrings within a string of length $n$ in $O(n)$ time and space. Instead of listing every palindrome, it computes two arrays: $d1[i]$ (the radius of the longest odd-length palindrome centered at position $i$) and $d2[i]$ (the radius of the longest even-length palindrome centered at position $i$). The radius is defined as the number of characters from the center to the rightmost edge, including the center character for odd lengths.

  12. Overview of the Chinese Driver's License Examination Subjects (科目)

    The driving test is divided into four subjects (科目), combining theory and practical skills:

    • Subject 1 (科目一): Theory exam on traffic laws and regulations. Consists of 100 multiple-choice or true/false questions (100 points total). Passing score is 90. Time limit: 45 minutes.
    • Subject 2 (科目二): Field driving test.
      • C2 requirements: Curve driving, reverse parking, side parking, and right-angle turns.
      • C1 requirements: All C2 requirements plus slope point parking.
    • Subject 3 (科目三): Road driving test. Includes tasks such as starting, straight-line driving, lane changing, pulling over, turning at intersections, and overtaking. (Note: C1 requires gear shifting/changing).
    • Subject 4 (科目四): Theory exam on safety and civilized common sense. Consists of 50 multiple-choice or true/false questions (100 points total). Time limit: 45 minutes. Unlike Subject 1, it includes case analysis and multiple-answer questions, but excludes specific penalty/fine/sentence amounts and animation questions.