12月USACO竞赛黄金组别真题解析~USACO竞赛冲刺班招生中

Bessie recently discovered that her favorite pop artist, Elsie Swift, is performing in her new Eras Tour! Unfortunately, tickets are selling out fast, so Bessie is thinking of flying to another city to attend the concert. The Eras tour is happening in N(2≤N≤750) cities labelled 1…N, and for each pair of cities (i,j) with i<j there either exists a single direct flight from i to j or not.

A flight route from city a to city b (a<b) is a sequence of k≥2 cities a=c1<c2<⋯<ck=b such that for each 1≤i<k, there is a direct flight from city ci to city ci+1. For every pair of cities (i,j) with i<j, you are given the parity of the number of flight routes between them (0 for even, 1 for odd).

While planning her travel itinerary, Bessie got distracted and now wants to know how many pairs of cities have direct flights between them. It can be shown that the answer is uniquely determined.

考情分析

从相邻位置来考虑比较简单，如果i到i+1路径为奇数，说明i到i+1有边，反之没有。

考虑任意点i和j的时候，只需要利用区间dp的思想计算出i到j除了直接到达的路径有多少条，看一下是否满足奇偶性即可。

时间复杂度:   O(n^3)

知识点：区间dp

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10^5) towns numbered from 1 to N and M (1≤M≤4⋅10^5) one-way roads. The i-th road runs from town ai to town bi and has label li 

(1≤ai,bi≤N, 1≤li≤10^9).

A trip of length k starting at town x0 is a sequence of towns x0,x1,…,xk, such that there is a road from town xi to town xi+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.

考情分析

首先题目保证给出图是DAG，那么我们要求最长路的话就可以利用拓扑排序/bfs来解决。

难点在于题目要求字典序最小，考虑如何快速比较两条出边的字典序大小

由于题目权值可以相同暴力走下去比较时间复杂度会被卡到$O(n^2)$

为了优化比较过程，我们希望能够快速得到两个最长路相同的点他们之间的字典序关系。

所以我们可以动态地对最长路相同的点的内部做一个排序，比较的时候就只需要拿出之前维护好的排序结果去做判断，判断时间复杂度就可以做到O(1)

总时间复杂度：O(nlogn)

知识点：拓扑排序，字典序

Farmer John is distributing haybales across the farm!

Farmer John's farm has N (1≤N≤2⋅10^5) barns, located at integer points x1,…,xN (0≤xi≤10^6) on the number line. Farmer John's plan is to first have N shipments of haybales delivered to some integer point y (0≤y≤10^6) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In particular, for some ai and bi

(1≤ai,bi≤10^6), ai haybales are wasted per unit of distance left each shipment is transported, and bi haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point y to a barn at point x, the number of haybales wasted is given by

Given Q (1≤Q≤2⋅10^5) independent queries each consisting of possible values of (ai,bi), please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses y optimally.

考情分析

观察1：查询的次数很多，可以考虑预处理，由于不需要频繁修改区间，使用前缀和即可。

观察2：题目保证数轴x1...xN上存在一个极小值点y，通过等式变形/反证法可以证明y必定为x1...xN中的一点，同时路径总和f(y)是一个两边往中间递减的单峰函数，可以使用三分法快速逼近y的最优值，三分法模板。

时间复杂度: O(Tlogn)

知识点：三分