作者： chenchen

2022 年 12 月的比赛以算法编程问题为特色，涵盖了广泛的技术和难度级别。
在为期 4 天的比赛中，共有 14719 名不同的用户登录。共有 11798 名参与者提交了至少一个解决方案，来自 88 个不同的国家：
5378 USA 4259 CHN 444 CAN 332 KOR 142 IND 125 ROU 88 MYS
77 SGP 72 TWN 64 VNM 61 HKG 55 GEO 50 GBR 47 IRN
46 DEU 40 POL 36 ARM 28 FRA 28 EGY 25 AUS 21 AZE
18 ISR 18 BLR 17 UKR 17 KAZ 15 GRC 14 HRV 14 BGD
13 SLV 13 NZL 12 TUR 12 TUN 12 THA 12 CHE 12 BRA
10 KGZ 10 JPN 10 IDN 8 RUS 8 NLD 7 ZAF 7 SWE
7 SRB 7 MNG 7 ESP 7 BGR 6 SYR 6 PHL 5 MEX
5 LTU 5 COL 5 ARE 4 TKM 4 PER 4 NPL 4 EST
3 SVK 3 NGA 2 PRK 2 MDA 2 MAR 2 LUX 2 KHM
2 ITA 2 IRL 2 CYP 2 CUB 1 VEN 1 UZB 1 TJK
1 SHN 1 PRT 1 PAK 1 MLT 1 MAC 1 LVA 1 IRQ
1 HUN 1 GUM 1 FIN 1 DOM 1 CZE 1 CHL 1 BOL
1 BEL 1 AUT 1 ARG 1 AFG
总共有 26969 份评分提交，按语言细分如下：
12396 C++17
6423 C++11
4386 Java
3561 Python 3.6.9
178 C
25 Python 2.7.17
以下是白金、黄金、白银和铜牌比赛的详细结果。您还将找到每个问题的解决方案和测试数据，并且通过单击任何问题，您可以练习在“分析模式”下重新提交解决方案。 如果您已登录，您还将在下方看到您自己的具体结果以及您参加的比赛。

　　USACO 2022 年 12 月学术活动，白金

白金组共有412人参加，其中247人为预科生。我们在本次比赛中看到了相当多的满分，其中有4个来自美国。最佳得分手的结果在这里。祝贺所有优秀选手取得的优异成绩！
1  Breakdown
查看问题 | 测试数据 | 解决方案
2  Making Friends
查看问题 | 测试数据 | 解决方案
3  Palindromes
查看问题 | 测试数据 | 解决方案

　　USACO 2022 年 12 月学术活动，金奖

黄金组共有1035人参加，其中预科生721人。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋升为白金组别。所有晋升者的详细结果都在这里。
1  Bribing Friends
查看问题 | 测试数据 | 解决方案
2  Mountains
问题 | 测试数据 | 解决方案
3  Strongest Friendship Group
查看问题 | 测试数据 | 解决方案

　　USACO 2022 年 12 月学术活动，银牌

银牌组共有2972人参加，其中预科生2216人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为黄金组。
1 Barn Tree
视图问题 | 测试数据 | 解决方案
2 Circular Barn
视图问题 | 测试数据 | 解决方案
3 Range Reconstruction
查看问题 | 测试数据 | 解决方案

　　USACO 2022 年 12 月学术活动，铜奖

青铜组总参赛人数10226人，其中预科生8057人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为银牌组。
1  Cow College
查看问题 | 测试数据 | 解决方案
2  Feeding the Cows
查看问题 | 测试数据 | 解决方案
3  Reverse Engineering
查看问题 | 测试数据 | 解决方案

最后的评论

我们的 2022-2023 赛季看起来有了一个良好的开端，12 月的比赛参与人数创下了纪录！
对于那些尚未晋升的人，请记住，您练习得越多，您的算法编码技能就会越好——请坚持下去！USACO 比赛旨在挑战最优秀的学生，要想在比赛中脱颖而出，需要付出大量的努力。为了帮助您修复代码中的任何错误，您现在可以重新提交您的解决方案并使用“分析模式”从评审服务器获得反馈。
关于学术诚信在我们比赛中的重要性的简短说明：数百名参赛者因在本次比赛中作弊而被取消资格。作弊会被终身取消 USACO 晋级资格，教师、校长和大学招生人员通常不喜欢被告知在我们的比赛中作弊的学生（过去曾有学生因作弊而被学校开除）在 USACO 比赛中）。请尊重我们比赛的完整性。处理作弊是导致比赛结果发布时间过长的主要原因之一。
许多人为 USACO 比赛的质量和成功做出了贡献。为本次比赛提供帮助的人包括 Benjamin Qi、Freddie Tang、Mythreya Dharani、Timothy Feng、Nathan Wang、Sam Zhang、Joe Li、Larry Xing、Aryansh Shrivastava、Chongtian Ma、Jesse Choe、Yuval Vaknin、Danny Mittal、Nick Wu、Spencer Compton、Riya Arora、Jonathan Paulson、Claire Zhang、Andi Qu、Richard Qi、David Hu、Mark Chen、Daniel Zhang 和 Timothy Qian。还要感谢我们的翻译人员和克莱姆森 CCIT 为我们提供比赛基础设施。最后，我们感谢 USACO 赞助商对 Citadel、Ansatz、X-Camp、TwoSigma、EasyFunCoding 和 Jump Trading 的慷慨支持。

Bessie the cow is trying to walk from her favorite pasture back to her barn.

The pasture and farm are on an N×N grid (2≤N≤50), with her pasture in the top-left corner and the barn in the bottom-right corner. Bessie wants to get home as soon as possible, so she will only walk down and to the right. There are haybales in some locations that Bessie cannot walk through; she must walk around them.

Bessie is feeling a little tired today, so she wants to change the direction she walks at most K times (1≤K≤3) .

How many distinct paths can Bessie walk from her favorite pasture to the barn? Two paths are distinct if Bessie walks in a square in one path but not in the other.

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

The input for each test case contains T sub-test cases, each describing a different farm and each of which must be answered correctly to pass the full test case. The first line of input contains T (1≤T≤50). Each of the T sub-test cases follow.

Each sub-test case starts with a line containing N and K.

The next N lines each contain a string of N characters. Each character is either . if it is empty or H if it has a haybale. It is guaranteed the top-left and bottom-right corners of the farm will not contain haybales.

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

Output T lines, the ith line containing the number of distinct paths Bessie can take in the ith sub-test case.

SAMPLE INPUT:

7

3 1

...

...

...

3 2

...

...

...

3 3

...

...

...

3 3

...

.H.

...

3 2

.HH

HHH

HH.

3 3

.H.

H..

...

4 3

...H

.H..

....

H...

SAMPLE OUTPUT:

2

4

6

2

0

0

6

We'll denote Bessie's possible paths as strings of D's and R's, indicating that Bessie moved either down or right, respectively.

In the first sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the second sub-test case, Bessie's four possible walks are DDRR, DRRD, RDDR, and RRDD.

In the third sub-test case, Bessie's six possible walks are DDRR, DRDR, DRRD, RDDR, RDRD, and RRDD.

In the fourth sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the fifth and sixth sub-test cases, it is impossible for Bessie to walk back to the barn.

In the seventh sub-test case, Bessie's six possible walks are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD.

SCORING:

Test case 2 satisfies K=1.

Test cases 3-5 satisfy K=2.

Test cases 6-10 satisfy K=3

Farmer John's cows N are very particular about the room temperature in their barn. Some cows like the temperature to be on the cooler side, while others prefer more warmth.

Farmer John's barn contains a sequence of N stalls, numbered 1…N, each containing a single cow. The i-th cow prefers the temperature of her stall to be pi, and right now the temperature in her stall is ti. In order to make sure every cow is comfortable, Farmer John installs a new air conditioning system that is controlled in a somewhat interesting way. He can send commands to the system telling it to either raise or lower the temperature in a consecutive series of stalls by 1 unit --- for example "raise the temperature in stalls 5…8 by 1 unit". The series of stalls could be as short as just a single stall.

Please help Farmer John determine the minimum number of commands he needs to send his new air conditioning system so that every cow's stall is at the ideal temperature for its resident cow.

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

The first line of input contains N. The next line contains the N non-negative integers p1…pN, separated by spaces. The final line contains the N non-negative integers t1…tN.

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

Please write a single integer as output containing the minimum number of commands Farmer John needs to use.

SAMPLE INPUT:

5

1 5 3 3 4

1 2 2 2 1

SAMPLE OUTPUT:

5

One optimal set of commands Farmer John can use might be the following:

Initial temperatures: 1 2 2 2 1

Increase stalls 2..5: 1 3 3 3 2

Increase stalls 2..5: 1 4 4 4 3

Increase stalls 2..5: 1 5 5 5 4

Decrease stalls 3..4: 1 5 4 4 4

Decrease stalls 3..4: 1 5 3 3 4

SCORING:

Test cases 2-5 satisfy N≤100.

Test cases 6-8 satisfy N≤1000.

Test cases 9-10 satisfy N≤100,000.

In test cases 1-6 and 9, temperature values are at most 100.

In test cases 7-8 and 10, temperature values are at most 10,000.

Farmer John has recently acquired N new cows (3≤N≤5×10^5), each of whose breed is either Guernsey or Holstein.

The cows are currently standing in a line, and Farmer John wants take a photo of every sequence of three or more consecutive cows. However, he doesn't want to take a photo in which there is exactly one cow whose breed is Guernsey or exactly one cow whose breed is Holstein --- he reckons this singular cow would feel isolated and self-conscious. After taking a photo of every sequence of three or more cows, he throws out all of these so-called "lonely" photos, in which there is exactly one Guernsey or exactly one Holstein.

Given the lineup of cows, please help Farmer John determine how many lonely photos he will throw out. Two photos are different if they start or end at different cows in the lineup.

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

The first line of input contains N.

The second line contains a string of N characters. The ith character is G if the ith cow in the line is a Guernsey. Otherwise, it will be an H and the ith cow is a Holstein.

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

Please print the number of photos Farmer John will throw out because they are lonely.

SAMPLE INPUT:

5

GHGHG

SAMPLE OUTPUT:

3

Every substring of length 3 in this example contains exactly one cow whose breed is Guernsey or exactly one cow whose breed is Holstein --- so these substrings represent lonely photos and would be thrown out by Farmer John. All longer substrings (GHGH, HGHG, and GHGHG) are acceptable to him.

SCORING:

Test cases 2 through 4 have N≤50.

Test cases 5 through 10 have N≤5000.

For a bit more challenge, test case 11 has no other constraints. Note that the answer for this case might be too large to fit into a standard 32-bit integer, and might require use of larger integer types (e.g., a 64-bit "long long int" type in C++).

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of N intervals (1≤N≤2·10^5), where the ith interval starts at position ai on the number line and ends at position bi≥ai. Both ai and bi are integers in the range 0…M, where 1≤M≤5000.

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

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

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

The first line of input contains N and M. Each of the next N lines describes an interval in terms of integers ai and bi.

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

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

SAMPLE INPUT:

2 5

1 3

2 5

SAMPLE OUTPUT:

0

0

1

3

4

4

4

3

3

1

1

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

SCORING:

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

Test cases 3-5 satisfy N≤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++).

Farmer John's farm consists of a set of N fields (1≤N≤10^5), conveniently numbered 1…N. Between these fields are M bi-directed paths (0≤M≤10^5), each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field N. 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 i and j is (i−j)2.

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

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

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

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

Each sub-test case starts with two integers, N and M. Next, M lines follow, each one containing two integers i and j, indicating a path between two different fields i and j. It is guaranteed that there is at most one path between any two fields, and that the sum of N+M over all sub-test cases is at most 5·10^5.

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

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

SAMPLE INPUT:

2

5 2

1 2

4 5

5 3

1 2

2 3

4 5

SAMPLE OUTPUT:

2

1

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≤20.

Test cases 3-5 satisfy N≤10^3.

Test cases 6-10 satisfy no additional constraints.

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 K grassy patches (1≤K≤2·10^5); the i-th patch is located at position pi and has an associated tastiness value ti (0≤ti≤109). Farmer John's nemesis, Farmer Nhoj, has already situated his M cows (1≤M≤2·10^5) at locations f1…fM. All K+M of these locations are distinct integers in the range [0,10^9].
Farmer John needs to pick N (1≤N≤2·10^5) 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.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains K, M, and N.
The next K lines each contain two space-separated integers pi and ti.

The next M lines each contain a single integer 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
2
3
5
7
11
SAMPLE OUTPUT:
36
If Farmer John places cows at positions 11.5 and 8 then he can claim a total tastiness of 10+12+14=36.

Problem credits: Brian Dean

Bessie the cow enjoys arts and crafts. In her free time, she has made N (1≤N≤50) bracelets, conveniently numbered 1…N. The ith bracelet is painted color i out of a set of N different colors. After constructing the bracelets, Bessie placed them on a table for display (which we can think of as the 2D plane). She was careful to arrange the bracelets to satisfy the following three conditions:

Every bracelet was a single closed polygonal chain -- a series of vertices (points) connected sequentially by line segments, where the first and last points are the same (Feel welcome to consult the wikipedia page for more detail: polygonal chain),

No bracelet intersected itself (this corresponds to a "simple" polygonal chain); and

No two bracelets intersected.

Unfortunately, right after Bessie arranged the bracelets in such a careful manner, Farmer John drove by in his tractor, shaking the table and causing the bracelets to shift around and possibly break into multiple (not necessarily closed or simple) polygonal chains! Afterward, Bessie wanted to check whether the three conditions above still held. However, it was dark, so she couldn't see the bracelets anymore.

Fortunately, Bessie had a flashlight. She chose M (1≤M≤50) vertical lines x=1,x=2,…,x=M and for each line, she swept the beam of the flashlight along that line from y=?∞ to y=∞, recording the colors of all bracelets she saw in the order they appeared. Luckily, no beam crossed over any vertex of any polygonal chain or two line segments at the same time. Furthermore, for each beam, every color that appeared appeared exactly twice.

Can you help Bessie use this information to determine whether it is possible that the bracelets still satisfy all three of the conditions above?

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

Each input case contains T sub-cases (1≤T≤50) that must all solved independently to solve the full input case. Consecutive test cases are separated by newlines.

The first line of the input contains T. Each of the T sub-test cases then follow.

The first line of each sub-test case contains two integers N and M. Each sub-test case then contains M additional lines. For each i from 1 to M, the i-th additional line contains an integer ki (0≤ki≤2N, ki even), followed by ki integers ci1,ci2,…,ciki (cij∈[1,N], every cij appears zero or two times). This means that when Bessie swept her flashlight from (i,?∞) to (i,∞), she encountered the colors ci1,ci2,…,ciki in that order.

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

For each sub-test case, print YES if it is possible for the three conditions above to be satisfied. Otherwise, print NO.

SAMPLE INPUT:

5

1 2

2 1 1

2 1 1

1 3

2 1 1

0

2 1 1

2 1

4 1 2 1 2

4 2

6 1 2 2 3 3 1

6 1 2 4 4 2 1

2 2

4 1 1 2 2

4 2 2 1 1

SAMPLE OUTPUT:

YES

NO

NO

YES

NO

An example of a feasible bracelet configuration for the first sub-case is:

For the fourth sub-case, a feasible arrangement is the following:

SCORING:

Test case 2 satisfies N=1.

Test cases 3-5 satisfy N=2.

Test cases 6-8 satisfy M=1.

Test cases 9-14 satisfy M=2.

Test cases 15-20 satisfy no additional constraints.

Bessie knows a number x+0.5 where x is some integer between 0 to N, inclusive (1≤N≤2·10^5).

Elsie is trying to guess this number. She can ask questions of the form "is i high or low?" for some integer i between 1 and N, inclusive. Bessie responds by saying "HI" if i is greater than x+0.5, or "LO" if i is less than x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once (in other words, the list is a permutation of size N). Then she goes through the list, guessing numbers that appear in the list in order.

However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number i and Elsie previously guessed some j<i and Bessie responded with "HI", Elsie will not guess i and will move on to the next number in the list. Similarly, if she is about to guess some number i and she previously guessed some j>i and Bessie responded with "LO", Elsie will not guess i and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines x regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string S, then the number of times Bessie says "HILO" is the number of length 4 substrings of S that are equal to "HILO."

Bessie knows that Elsie will use this strategy; furthermore, she also knows the exact permutation that Elsie will use. However, Bessie has not decided on what value of x to choose.

Help Bessie determine how many times she will say "HILO" for each value of x.

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

The first line contains N.

The second line contains Elsie's permutation of size N.

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

For each x from 0 to N, inclusive, output the number of times Bessie will say HILO on a new line.

SAMPLE INPUT:

5

5 1 2 4 3

SAMPLE OUTPUT:

0

1

1

2

1

0

For x=0, Bessie will say "HIHI," for a total of zero "HILO"s.

For x=2, Bessie will say "HILOLOHIHI," for a total of one "HILO".

For x=3, Bessie will say "HILOLOHILO", for a total of two "HILO"s.

SCORING:

Tests 1 to 4 satisfy N≤5000.

Tests 5 to 8 have a uniformly random permutation.

Tests 9 to 20 satisfy no further constraints.