2023-2024年USACO首次月考題目出爐！金級第一題真題及解析
2023-2024賽季的USACO考試已于12月18日正式結束，晉級賽的最新試題也已經公布。近日，USACO官方公布了2023-2024賽季首場月賽的晉級分數線。如果沒有晉級，12月可以當做一個練手+熟悉賽制的環節，1、2月的月賽持續發力，USACO可以重復挑戰。
今天給大家分享金級試題和解析，參賽的同學來看看解題思路，沒參賽的同學來看看難度如何？
USACO 2023年12月金級第一題
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：
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?Qi
題意：給定n個機場，編號1-n，約定只有小的數字到大的數字有航班，而且兩點之間最多只有一趟航班。告知每兩個機場之間總航班數量的奇偶性（奇數個航班用1表示，偶數個用0表示），計算兩點之間有直達航班的數量。
題解：由于航班只會從小編號的點出發到達大編號點，考慮從大到小枚舉點每個點i, 再從小到大枚舉j，同時枚舉直達中轉點k。利用三重循環，枚舉i,j,k，其中i<k<j。計算i->j是否有直達路徑。由于k<j，所以一定在此之前就已經算出來i->k是否有直達路徑，i->j總航班數=i->k是否存在直達航班(0表示沒有或1表示有) * k->j存在的總航班數 + i->j是否存在直達航班，又因為在模二意義（0和1）下計算，所以全程使用異或計算。
USACO歷年真題及參考書，掃碼領?。 竞擦痔峁﹫竺笇Х铡?/strong>
USACO歷年真題及參考書
2023-2024年USACO活動時間
第一次月賽：2023年12月15日-18日
第二次月賽：2024年1月26日-29日
第三次月賽：2024年2月16日-19日
美國公開賽：2024年3月15日-18日
（中國學生只能參加到公開賽）
集訓營：2024年5月23日-6月1日
EGOI：2024年7月21日-27日（荷蘭）
IOI：2024年9月1日-8日（埃及）
報名方式：參賽者可隨時在官網注冊賬號，注冊。報名，只需在活動時間登陸完成答題即可。
官網地址：usaco.org
提交之后，官網會發送一份郵件到您郵箱，郵件中有賬號密碼
利用已知的賬號于密碼，登錄USACO賬號，即可開始考試
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
