2023-2024年USACO首次月考題目出爐！銀組第二題真題及解析

2023-2024賽季UASCO首場月賽已經圓滿結束，晉級賽的最新試題也已經公布。沒能當場晉級的同學們可以耐心等待一周，一周內USACO官方將會公布本次晉級賽成績。如果沒有晉級，12月可以當做一個練手+熟悉賽制的環節，1、2月的月賽持續發力，USACO可以重復挑戰。

今天給大家分享銀級試題和解析，參賽的同學來看看解題思路，沒參賽的同學來看看難度如何？

銀組第二題

INPUT FORMAT（pipe stdin）：

The first line contains N and K.

The next line contains a1,…,aK.

The next line contains b1,…,bK.

OUTPUT FORMAT (pipe stdout)：

The maximum number of fixed points.

SAMPLE INPUT：

6 3

1 2 3

2 3 1

SAMPLE OUTPUT：

6

Annabelle and Bessie could have assigned the same label to every barn.

SAMPLE INPUT：

6 3

1 2 3

4 5 6

SAMPLE OUTPUT：

0

Annabelle and Bessie could not have assigned the same label to any barn.

SAMPLE INPUT：

6 4

1 2 3 4

4 3 2 5

SAMPLE OUTPUT：

4

Annabelle and Bessie could have assigned labels 2,3,4,6 to the same barns.

SCORING：

● Inputs 4-5： N≤8

● Inputs 6-8： N≤5000

● Inputs 9-15： No additional constraints

試題解析

A與B最多有多少元素相同其實就是看兩個環最多能有多少個位置能匹配。

匹配的定義是：環A和環B按某種順序按位匹配后相同數字最多是多少個。

我們可以考慮讓A環不動，B環循環右移，對于每一種字符計算出需要將環循環右移多少步得到，最終查詢哪個步數出現次數最多即可。

注意我們還要考慮環外點最多有多少匹配：這個比較簡單，我們只需要統計剩下元素里有多少種類A與B是相同的即可。

時間復雜度：O(n)

知識點：環，計數

USACO歷年真題及參考書，掃碼領??！【翰林提供報名指導服務】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賬號，即可開始考試