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历年真题及参考书