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

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

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

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

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

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=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.

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：

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?Qi

題意：給定n個(gè)機(jī)場(chǎng)，編號(hào)1-n，約定只有小的數(shù)字到大的數(shù)字有航班，而且兩點(diǎn)之間最多只有一趟航班。告知每?jī)蓚€(gè)機(jī)場(chǎng)之間總航班數(shù)量的奇偶性（奇數(shù)個(gè)航班用1表示，偶數(shù)個(gè)用0表示），計(jì)算兩點(diǎn)之間有直達(dá)航班的數(shù)量。

題解：由于航班只會(huì)從小編號(hào)的點(diǎn)出發(fā)到達(dá)大編號(hào)點(diǎn)，考慮從大到小枚舉點(diǎn)每個(gè)點(diǎn)i, 再?gòu)男〉酱竺杜ej，同時(shí)枚舉直達(dá)中轉(zhuǎn)點(diǎn)k。利用三重循環(huán)，枚舉i,j,k，其中i<k<j。計(jì)算i->j是否有直達(dá)路徑。由于k<j，所以一定在此之前就已經(jīng)算出來(lái)i->k是否有直達(dá)路徑，i->j總航班數(shù)=i->k是否存在直達(dá)航班(0表示沒(méi)有或1表示有) * k->j存在的總航班數(shù) + i->j是否存在直達(dá)航班，又因?yàn)樵谀６饬x（0和1）下計(jì)算，所以全程使用異或計(jì)算。

USACO歷年真題及參考書，掃碼領(lǐng)取！【翰林提供報(bào)名指導(dǎo)服務(wù)】USACO歷年真題及參考書