历年考研参考(历年考研参考及答案)

历年考研真题，历年考研真题及答案

USACO赛季即将开始

相信大家都很熟悉

小编整理了USACO赛季

近两年青铜、银组真题

下面就让带大家一起了解吧~

青铜组真题

Problem1. Herdle

题解

Problem2.Non-Transitive Dice

题解

Problem3. Drought

题解

2021.12银组真题

Problem1.Closest cow wins

Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are KK grassy patches (1≤K≤2⋅1051≤K≤2⋅105); the ii-th patch is located at position pipi and has an associated tastiness value titi (0≤ti≤1090≤ti≤109). Farmer John’s nemesis, Farmer Nhoj, has already situated his MM cows (1≤M≤2⋅1051≤M≤2⋅105) at locations f1…fMf1…fM. All K+MK+M of these locations are distinct integers in the range [0,109][0,109].

Farmer John needs to pick NN (1≤N≤2⋅1051≤N≤2⋅105) locations (not necessarily integers) for his cows to be located. These must be distinct from those already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership of that patch. If there are two cows from rival farmers equally close to the patch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj’s cows and the locations and tastiness values of the grassy patches, determine the maximum total tastiness Farmer John’s cows can claim if optimally positioned.

拥有最靠近某个草地的奶牛的农夫拥有这一草地。如果来自两方农夫的两头奶牛距这一草地相等，则 Farmer Nhoj 拥有该草地。给定 Farmer Nhoj 的奶牛的位置以及草地的位置和美味值，求 Farmer John 的奶牛以最优方式放置时可以达到的最大总美味值。

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains K, M, and N.

第一行输入K，M，和N

The next KK lines each contain two space-separated integers pipi and titi.

后面K行输入pi和ti

The next MM lines each contain a single integer fifi.

后面M行输入fi

OUTPUT FORMAT (print output to the terminal / stdout):

An integer denoting the maximum total tastiness. Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., “long long”s in C or C++).

SAMPLE INPUT:

6 5 2

0 4

4 6

8 10

10 8

12 12

13 14

SAMPLE OUTPUT:

If Farmer John places cows at positions 11.511.5 and 88 then he can claim a total tastiness of 10+12+14=3610+12+14=36.

题解

Problem2.Connecting Two Barns

Farmer John’s farm consists of a set of NN fields (1≤N≤105)(1≤N≤105), conveniently numbered 1…N1…N. Between these fields are MM bi-directed paths (0≤M≤105)(0≤M≤105), each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field NN. Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields ii and jj is (i−j)2(i−j)2.

Please help Farmer John determine the minimum cost needed such that barns 11 and NN become reachable from each-other.

农场有两个牛棚，一个在田地 1 中，另一个在田地 NN 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地 ii 和 jj 之间建造新道路的花费是 (i−j)2(i−j)2。

请帮助 Farmer John 求出使得牛棚 11 和 NN 可以相互到达所需要的最小花费。

INPUT FORMAT (input arrives from the terminal / stdin):

Each input test case contains TT sub-cases (1≤T≤201≤T≤20), all of which must be solved correctly to solve the input case.

The first line of input contains TT, after which TT sub-test cases follow.

Each sub-test case starts with two integers, NN and MM. Next, MM lines follow, each one containing two integers ii and jj, indicating a path between two different fields ii and jj. It is guaranteed that there is at most one path between any two fields, and that the sum of N+MN+M over all sub-test cases is at most 5⋅1055⋅105.

OUTPUT FORMAT (print output to the terminal / stdout):

Output TT lines. The iith line should contain a single integer giving the minimum cost for the iith sub-test case.

SAMPLE INPUT:

5 2

1 2

4 5

5 3

1 2

2 3

4 5

SAMPLE OUTPUT:

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

Test case 2 satisfies N≤20N≤20.

Test cases 3-5 satisfy N≤103N≤103.

Test cases 6-10 satisfy no additional constraints.

题解

Problem3.Convoluted

Intervals

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of NN intervals (1≤N≤2⋅1051≤N≤2⋅105), where the iith interval starts at position aiai on the number line and ends at position bi≥aibi≥ai. Both aiai and bibi are integers in the range 0…M0…M, where 1≤M≤50001≤M≤5000.

To play the game, Bessie chooses some interval (say, the iith interval) and her cousin Elsie chooses some interval (say, the jjth interval, possibly the same as Bessie’s interval). Given some value kk, they win if ai+aj≤k≤bi+bjai+aj≤k≤bi+bj.

For every value of kk in the range 0…2M0…2M, please count the number of ordered pairs (i,j)(i,j) for which Bessie and Elsie can win the game.

奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 N 个区间（1≤N≤2⋅1051≤N≤2⋅105）有关，其中第 ii 个区间从数轴上的 ai 位置开始，并在位置 bi≥aibi≥ai 结束。aiai 和 bibi 均为 0…M 范围内的整数，其中 1≤M≤50001≤M≤5000。对范围 0…2M0…2M 内的每个值 kk，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 (i,j)(i,j) 的数量。

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN and MM. Each of the next NN lines describes an interval in terms of integers aiai and bibi.

第一行输入N和M

后面每N行是ai和bi的区间值

OUTPUT FORMAT (print output to the terminal / stdout):

Please print 2M+12M+1 lines as output, one for each value of kk in the range 0…2M0…2M.

SAMPLE INPUT:

2 5

1 3

2 5

SAMPLE OUTPUT:

In this example, for just k=3k=3, there are three ordered pairs that will allow Bessie and Elie to win: (1,1)(1,1), (1,2),(1,2), and (2,1)(2,1).

SCORING:

Test cases 1-2 satisfy N≤100,M≤100N≤100,M≤100.

Test cases 3-5 satisfy N≤5000N≤5000.

Test cases 6-20 satisfy no additional constraints.

Note that output values might be too large to fit into a 32-bit integer, so you may want to use 64-bit integers (e.g., “long long” ints in C or C++).

题解

2022.1银组真题

Problem1.Searching for soulmates

Farmer John’s cows each want to find their soulmate — another cow with similar characteristics with whom they are maximally compatible. Each cow’s personality is described by an integer pipi (1≤pi≤1018). Two cows with the same personality are soulmates. A cow can change her personality via a “change operation” by multiplying by 2, dividing by 2 (if pi is even), or adding 1.

Farmer John initially pairs his cows up in an arbitrary way. He is curious how many change operations would be needed to make each pair of cows into soulmates. For each pairing, decide the minimum number of change operations the first cow in the pair must make to become soulmates with the second cow.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N (1≤N≤10), the number of pairs of cows. Each of the remaining N lines describes a pair of cows in terms of two integers giving their personalities. The first number indicates the personality of the cow that must be changed to match the second.

OUTPUT FORMAT (print output to the terminal / stdout):

Please write N lines of output. For each pair, print the minimum number of operations required for the first cow to make her personality match that of the second.

SAMPLE INPUT:

31 13

12 8

25 6

10 24

1 1

997 120

SAMPLE OUTPUT:

For the first test case, an optimal sequence of changes is 31⟹32⟹16⟹8⟹9⟹10⟹11⟹12⟹1331⟹32⟹16⟹8⟹9⟹10⟹11⟹12⟹13.

For the second test case, an optimal sequence of changes is 12⟹6⟹7⟹812⟹6⟹7⟹8.

SCORING:

Test cases 1-4 satisfy pi≤10.

Test cases 5-12 satisfy no additional constraints.

题解

Problem 2. Cow Frisbee

Farmer John’s NN cows (N≤3×105)N≤3×105) have heights 1,2,…,N1,2,…,N. One day, the cows are standing in a line in some order playing frisbee; let h1…hNh1…hN denote the heights of the cows in this order (so the hh’s are a permutation of 1…N1…N).

Two cows at positions ii and jj in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than min(hi,hj)min(hi,hj).

Please compute the sum of distances between all pairs of locations i

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains a single integer NN. The next line of input contains h1…hNh1…hN, separated by spaces.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the sum of distances of all pairs of locations at which there are cows that can throw the frisbee back and forth. Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).

SAMPLE INPUT:

4 3 1 2 5 6 7

SAMPLE OUTPUT:

The pairs of successful locations in this example are as follows:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

SCORING

Test cases 1-3 satisfy N≤5000N≤5000.

Test cases 4-11 satisfy no additional constraints.

Two cows at positions ii and jj in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than min(hi,hj)min(hi,hj).

Please compute the sum of distances between all pairs of locations i

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains a single integer NN. The next line of input contains h1…hNh1…hN, separated by spaces.

OUTPUT FORMAT (print output to the terminal / stdout):

SAMPLE INPUT:

4 3 1 2 5 6 7

SAMPLE OUTPUT:

The pairs of successful locations in this example are as follows:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

SCORING

Test cases 1-3 satisfy N≤5000N≤5000.

Test cases 4-11 satisfy no additional constraints.

题解

Problem3.Cereal 2

Farmer John’s cows like nothing more than cereal for breakfast! In fact, the cows have such large appetites that they will each eat an entire box of cereal for a single meal.

The farm has recently received a shipment with MM different types of cereal (2≤M≤105)(2≤M≤105). Unfortunately, there is only one box of each cereal! Each of the NN cows (1≤N≤105)(1≤N≤105) has a favorite cereal and a second favorite cereal. When given a selection of cereals to choose from, a cow performs the following process:

If the box of her favorite cereal is still available, take it and leave.

Otherwise, if the box of her second-favorite cereal is still available, take it and leave.

Otherwise, she will moo with disappointment and leave without taking any cereal.

Find the minimum number of cows that go hungry if you permute them optimally. Also, find any permutation of the NN cows that achieves this minimum.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains two space-separated integers NN and M.M.

For each 1≤i≤N,1≤i≤N, the ii-th line contains two space-separated integers fifi and sisi (1≤fi,si≤M1≤fi,si≤M and fi≠sifi≠si) denoting the favorite and second-favorite cereals of the ii-th cow.

OUTPUT FORMAT (print output to the terminal / stdout):

Print the minimum number of cows that go hungry, followed by any permutation of 1…N1…N that achieves this minimum. If there are multiple permutations, any one will be accepted.

SAMPLE INPUT:

8 10

2 1

3 4

2 3

6 5

7 8

6 7

7 5

5 8

SAMPLE OUTPUT:

In this example, there are 88 cows and 1010 types of cereal.

Note that we can effectively solve for the first three cows independently of the last five, since they share no favorite cereals in common.

If the first three cows choose in the order [1,2,3][1,2,3], then cow 11 will choose cereal 22, cow 22 will choose cereal 33, and cow 33 will go hungry.

If the first three cows choose in the order [1,3,2][1,3,2], then cow 11 will choose cereal 22, cow 33 will choose cereal 33, and cow 22 will choose cereal 44; none of these cows will go hungry.

Of course, there are other permutations that result in none of the first three cows going hungry. For example, if the first three cows choose in the order [3,1,2][3,1,2] then cow 33 will choose cereal 22, cow 11 will choose cereal 11, and cow 22 will choose cereal 33; again, none of cows [1,2,3][1,2,3] will go hungry.

It can be shown that out of the last five cows, at least one must go hungry.

SCORING:

In 44 out of 1414 test cases, N,M≤100N,M≤100.

题解

这就是关于USACO赛季部分历年真题

大家有什么想法呢

欢迎在评论区告诉小编一起讨论哦！

温馨提示：北京青少年程序设计展示活动于今日上午正式开始，报名的同学们不要错过活动时间哦！

声明:以上题解来源于博主GeekAlice，感谢分享！

来源：网络，所有图文仅供学习交流使用，如有侵权烦请告知，我们会立即删除.

公众号｜huimingkeji

联系电话｜010-57110625

历年考研参考(历年考研参考及答案)