分类： 赛事资讯

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 labeled 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=c₁<c₂<⋯<c_k=b such that for each 1≤i<k, there is a direct flight from city c_i to city c_i+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.

INPUT FORMAT (pipe stdin):

The first line contains N.

Then follow N−1 lines. The ith line contains N−i integers. The j th integer of the i
th line is equal to the parity of the number of flight routes from i to i+j.

OUTPUT FORMAT (pipe stdout):

Output the number of pairs of cities with direct flights between them.

SAMPLE INPUT:

3
11
1

SAMPLE OUTPUT:

2

There are two direct flights: 1→2 and 2→3. There is one flight route from 1
to 2 and 2 to 3, each consisting of a single direct flight. There is one flight route from 1 to 3(1→2→3).

SAMPLE INPUT:

5
1111
101
01
1

SAMPLE OUTPUT:

6
There are six direct flights 1→2,1→4,1→5,2→3,3→5,4→5. These result in the following numbers of flight routes:

Flight Route Counts:

dest
1 2 3 4 5

1 0 1 1 1 3
2 0 0 1 0 1
source 3 0 0 0 0 1
4 0 0 0 0 1
5 0 0 0 0 0

which is equivalent to the sample input after taking all the numbers (mod2).

SCORING:

Inputs 3-4: N≤6
Inputs 5-12: N≤100
Inputs 13-22: No additional constraints.
Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie has taken on a new job as a train dispatcher! There are two train stations:A and B. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time t, then it will arrive at the other station at time t+T(1≤T≤10¹²).

There are N (1≤N≤5000) trains whose departure times need to be scheduled. The i th train must leave station s_i at time t_i or later (s_i∈{A,B},0≤t_i≤10¹²). It is not permitted to have trains going in opposite directions along the track at the same time (since they would crash). However, it is permitted to have many trains on the track going in the same direction at the same time (assume trains have negligible size).

Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train i is scheduled to leave at time a_i≥s_i, the total delay is defined as

INPUT FORMAT (pipe stdin):

The first line contains N and T.

Then N lines follow, where the ith line contains the station s_i,
and time t_i corresponding to the ith train.

OUTPUT FORMAT (pipe stdout):

The minimum possible total delay over all valid schedules.

SAMPLE INPUT:

1 95
B 63

SAMPLE OUTPUT:

0

The only train leaves on time.

SAMPLE INPUT:

4 1
B 3
B 2
A 1
A 3

SAMPLE OUTPUT:

1
There are two optimal schedules. One option is to have trains 2,3,4 leave on time and train 1 leave after a one-minute delay. Another is to have trains 1,2,3 leave on time and train 4 leave after a one-minute delay.

SAMPLE INPUT:

4 10
A 1
B 2
A 3
A 21

SAMPLE OUTPUT:

13
The optimal schedule is to have trains 1and 3 leave on time, train 2 leave at time 13, and train 4 leave at time 23. The total delay is 0+11+0+2=13.

SAMPLE INPUT:

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

SAMPLE OUTPUT:

548047356974

SCORING:

Inputs 5-6: N≤15
Inputs 7-10: N≤100
Inputs 11-14: N≤500
Inputs 15-18: N≤2000
Inputs 19-24: No additional constraints
Problem credits: Brandon Wang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

To improve her mathematical knowledge, Bessie has been taking a graph theory course and finds herself stumped by the following problem. Please help her!

You are given a connected, undirected graph with vertices labeled 1…N and edges labeled 1…M(2≤N≤2⋅10⁵, N−1≤M≤4⋅10⁵). For each vertex v in the graph, the following process is conducted:​

Let S={v}and h=0.

While |S|<N,​

1.Out of all edges with exactly one endpoint in S, let e be the edge with the minimum label.
2.Add the endpoint of e not in S to S.
3.Set h=10h+e.
​
Return h ( mod 10⁹+7).
​
Determine all the return values of this process.​

INPUT FORMAT (pipe stdin):

The first line contains N and M .​Then follow M lines, the eth containing the endpoints (a_e,b_e) of the eth edge (1≤a_e<b_e≤N). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.
​
OUTPUT FORMAT (pipe stdout):

Output N lines, where the ith line should contain the return value of the process starting at vertex i.

SAMPLE INPUT:

3 2
1 2
2 3

SAMPLE OUTPUT:

12
12
21

SAMPLE INPUT:

5 6
1 2
3 4
2 4
2 3
2 5
1 5

SAMPLE OUTPUT:

1325
1325
2315
2315
5132

Consider starting at i=3. First, we choose edge 2, after which S={3,4} and h=2.Second, we choose edge 3, after which S={2,3,4}and h=23. Third, we choose edge 1, after which S={1,2,3,4} and h=231. Finally, we choose edge 5, after which S={1,2,3,4,5}and h=2315. The answer for i=3 is therefore 2315.

SAMPLE INPUT:

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15

SAMPLE OUTPUT:

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Make sure to output the answers modulo 109+7.

SCORING:

Input 4: N,M≤2000
Inputs 5-6: N≤2000
Inputs 7-10: N≤10000
Inputs 11-14: a_e+1=b_e
for all e
Inputs 15-23: No additional constraints.

Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John has N (2≤N≤10⁵) cows labeled 1…N, where the connections between cows are described by a tree. Unfortunately, there is a sickness spreading throughout.

Initially, some cows start off infected. Every night, an infected cow spreads the sickness to their neighbors. Once a cow is infected, she stays infected. After some amount of nights, Farmer John realizes that there is an issue so he tests his cows to determine who has the sickness.

You are given Q(1≤Q≤20) different values for the number of nights, each an integer in the range [0,N]
. For each number of nights, determine the minimum number of cows that could have started with the illness, or that the number of nights is inconsistent with the given information.

INPUT FORMAT (pipe stdin):

The first line contains N.

The next line contains a bit string of length N, where the ith bit is 1 if the ith cow is infected and 0 otherwise. At least one cow is infected.

The next N−1 lines contain the edges of the tree.

Then Q, followed by the Q values for the number of nights.

OUTPUT FORMAT (pipe stdout):

Q lines, the answers for each number of nights, or −1 if impossible.

SAMPLE INPUT:

5
11111
1 2
2 3
3 4
4 5
6
5
4
3
2
1
0

SAMPLE OUTPUT:

1
1
1
1
2
5

For the first four queries, one possibility is that just cow 3 started with the illness. For the fifth query (1 night), one possibility is that cows 2 and 4 started with the illness. For the sixth query (0 nights), one possibility is that all five cows started with the illness.

SAMPLE INPUT:

10
1111111111
1 2
2 3
2 4
2 5
2 6
6 7
7 8
8 9
9 10
11
0
1
2
3
4
5
6
7
8
9
10

SAMPLE OUTPUT:

10
3
2
1
1
1
1
1
1
1
1

For the first query (0 nights), one possibility is that all ten cows started with the illness. For the second query (1 night), one possibility is that cows 2, 7, and 9 started with the illness. For the third query (2 nights), one possibility is that cows 2 and 9 started with the illness. For the fourth to eleventh queries, one possibility is that just cow 7 started with the illness.

SAMPLE INPUT:

5
11100
1 2
2 3
3 4
4 5
6
0
1
2
3
4
5

SAMPLE OUTPUT:

3
1
1
-1
-1
-1

For the first query (0 nights), one possibility is that cows 1, 2, and 3 started with the illness. For the second query (1 night), one possibility is that just cow 2 started with the illness. For the third query (2 nights), one possibility is that just cow 1 started with the illness. For the fourth through sixth queries, there is no consistent possibility.

SCORING:

Inputs 4-5: N≤10
Inputs 6-8: All cows are infected.
Inputs 9-11: N≤400
Inputs 12-23: No additional restrictions.
Problem credits: Suhas Nagar and Brandon Wang

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划