Home » 国际竞赛 » Details

2023-2024年USACO首次月考题目出炉！金级第一题真题及解析

Category: 国际竞赛, 翰林严选, 计算机国际竞赛 Date: 2024年1月2日上午10:47

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：

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历年真题及参考书，扫码领取！【翰林提供报名指导服务】USACO历年真题及参考书