Home » 國際競(jìng)賽 » Details

2023-2024年USACO首次月考題目出爐！白金級(jí)第一題真題及解析

Category: 國際競(jìng)賽, 翰林嚴(yán)選, 計(jì)算機(jī)國際競(jìng)賽 Date: 2024年1月2日上午11:14

2023-2024賽季的USACO考試已于12月18日正式結(jié)束，晉級(jí)賽的最新試題也已經(jīng)公布。近日，USACO官方公布了2023-2024賽季首場(chǎng)月賽的晉級(jí)分?jǐn)?shù)線。如果沒有晉級(jí)，12月可以當(dāng)做一個(gè)練手+熟悉賽制的環(huán)節(jié)，1、2月的月賽持續(xù)發(fā)力，USACO可以重復(fù)挑戰(zhàn)。

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

USACO 2023年12月白金級(jí)第一題

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

部分代碼截圖：