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账号，即可开始考试