Блог пользователя NaoJoeMiao

Автор NaoJoeMiao, история, 2 года назад, По-английски

4A. Maximum Average Segment

HINT 1
HINT 2
HINT 3

4B. Minimum Average Path

HINT 1
HINT 2
HINT 3
HINT 4

4C. Pair Selection

HINT 1
HINT 2

5A. K-th Number in the Union of Segments

HINT 1

5B. Multiplication Table

HINT 1
HINT 2

5C. K-th Sum

HINT 1
HINT 2

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

Автор NaoJoeMiao, 3 года назад, По-английски

The idea is to do a topsort on just directed edges, if there is a loop, then output NO.

If three is no loop, we can always find a solution. All we need to do is make sure the direction we add is following the top sort order.

So we assign an id for topsort results and use this determine which should come first.

You can view this question as adding more edges to a DAG and not creating loops, how to add those edges?

Things I learned:

  1. Use scanf printf and puts instead of cin/cout.

  2. memset is costly, not O(1). Avoid at all cost.

  3. Use BFS to do top sort instead of DFS to avoid stack overflow.

Submission

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится