Home » 國際競賽 » Details

2023-2024年USACO首次月考題目出爐！金級第二題真題及解析

Category: 國際競賽, 翰林嚴選, 計算機國際競賽 Date: 2024年1月2日上午10:58

2023-2024賽季的USACO考試已于12月18日正式結束，晉級賽的最新試題也已經公布。近日，USACO官方公布了2023-2024賽季首場月賽的晉級分數線。如果沒有晉級，12月可以當做一個練手+熟悉賽制的環節，1、2月的月賽持續發力，USACO可以重復挑戰。

今天給大家分享金級試題和解析，參賽的同學來看看解題思路，沒參賽的同學來看看難度如何？

USACO 2023年12月金級第二題

Bessie is going on a trip in Cowland, which has N (2≤N≤2?10⁵) towns numbered from 1 to N and M (1≤M≤4?10⁵) one-way roads. The ith road runs from town a_i
to town b_i and has label li (1≤a_{i ,}?b_i≤N, 1≤l_i≤109).

A trip of length k starting at town x₀ is a sequence of towns x₀,x₁,…,x_k, such that there is a road from town x_i to town x_i+1 for all 0≤i<k. It is guaranteed that there are no trips of infinite length in Cowland, and that no two roads connect the same pair of towns.

For each town, Bessie wants to know the longest possible trip starting at it. For some starting towns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.

INPUT FORMAT (pipe stdin)：

The first line contains N and M.

The next M lines each contain three integers a_{i ,}?b_i and l_i, denoting a road from a_i
to b_i with label l_i.

OUTPUT FORMAT (pipe stdout)：

Output N lines. The ith should contain two space-separated integers, the length and sum of road labels of Bessie's preferred trip starting at town i.

SAMPLE INPUT：

4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 10

SAMPLE OUTPUT：

0 0
1 10
1 10
2 20

SAMPLE INPUT：

4 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 1

SAMPLE OUTPUT：

0 0
1 10
1 5
2 12

In the following explanation, we let represent the road from a_ito b_iwith label l_i.

There are several trips starting from vertex 4, including and are the longest. These trips each have length 2, and their road label sequences are [4,5]
and [2,10], respectively. [2,10] is the lexicographically smaller sequence, and its sum is 12.

SAMPLE INPUT：

4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 1

SAMPLE OUTPUT：

0 0
1 10
1 5
2 7

SAMPLE INPUT：

4 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 1

SAMPLE OUTPUT：

0 0
1 5
1 10
2 7

SCORING：

Inputs 5-6： All labels are the same.
Inputs 7-8： All labels are distinct.
Inputs 9-10： N,M≤5000
Inputs 11-20： No additional constraints.
Problem credits： Claire Zhang and Spencer Compton

題意：給定一個n個點m條邊的有向無環圖（DAG)，計算從每個點出發最長的鏈的長度和總長度。如果有多個路徑長度都最大，取路徑上邊長序列字典序最小的鏈。

題解：?

1.40分解法：

拓撲排序，從出度為0的點去搜索。先把每個點深度定為0，嘗試用下面的點去更新上面的深度，記錄每個點的最長鏈上的前一個點。當前深度更大的話就更新最長路徑，遇到深度相同的時候把之前的鏈和現在的鏈暴力比較，就是暴力判斷兩條鏈的第一個不同的位置，當前路徑字典序更小的話就更新。

2.滿分解法：

比較字典序的邏輯改成倍增維護后綴哈希值，每次二分不同位置，去找第一個不同的邊比大小。

USACO歷年真題及參考書，掃碼領取！【翰林提供報名指導服務】USACO歷年真題及參考書