2023-2024年USACO首次月考题目出炉！银组第三题真题及解析

2023-2024赛季UASCO首场月赛已经圆满结束，晋级赛的最新试题也已经公布。没能当场晋级的同学们可以耐心等待一周，一周内USACO官方将会公布本次晋级赛成绩。如果没有晋级，12月可以当做一个练手+熟悉赛制的环节，1、2月的月赛持续发力，USACO可以重复挑战。

今天给大家分享银级试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？

银组第三题

INPUT FORMAT (pipe stdin)：

The first line contains T and C.

The next line contains the locations of the T targets, distinct integers in the range [−C,C].

The next line contains the command string of length C, containing only the characters F, L, and R.

OUTPUT FORMAT (pipe stdout)：

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

SAMPLE INPUT：

3 7

0 -1 1

LFFRFRR

SAMPLE OUTPUT：

3

If you make no changes to the string, Bessie will hit two targets：

Command | Position | Total Targets Hit

--------+----------+-------------------

Start | 0 | 0

L | -1 | 0

F | -1 | 1

F | -1 | 1 (can't destroy target more than once)

R | 0 | 1

F | 0 | 2

R | 1 | 2

R | 2 | 2

If you change the last command from R to F, Bessie will hit all three targets：

Command | Position | Total Targets Hit

--------+----------+-------------------

Start | 0 | 0

L | -1 | 0

F | -1 | 1

F | -1 | 1 (can't destroy target more than once)

R | 0 | 1

F | 0 | 2

R | 1 | 2

F | 1 | 3

SAMPLE INPUT：

1 5

0

FFFFF

SAMPLE OUTPUT：

1

If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.

SAMPLE INPUT：

5 6

1 2 3 4 5

FFRFRF

SAMPLE OUTPUT：

3

SCORING：

● Inputs 4-6： T,C≤1000

● Inputs 7-15： No additional constraints.

试题解析

先求所有的步骤整体平移-2,-1,0,+1,+2时可以击中多少个目标。答案在change[1]-change[5]。再用hit[1-5][位置]记录每个位置被击中了多少次。

然后i从左往右一位位求i之前已经固定，i改变以后，能击中多少次；

这样求完以后只需要把第i位固定带来的影响，更新到change和hit里就可以了。

i从左往右固定过程中，如果这一位是L和R只影响位置p；

但如果这一位是F，那么固定以后，就要更新hit里的次数。因为它-2 -1 +1 +2都不可能发生了。

所以更新了两部分内容。

1. 当前位置p，如果之后的F因为-2 -1 +1 +2击中过它，现在应该i已经固定，它一定会被这一次射击击中。所以把-2 -1 +1 +2以后的p位置的hit数都清0，change对应更新。

2. 当前位置p，-2 -1 +1 +2以后的位置的hit数减少1次，如果减到0就更新change

最终就是，确定会击中的数量cnt，和change数组维护的i之后的-2 -1 +1 +2以后的4种不同击中数量，根据L->R R->L之类的变化情况相加。

时间复杂度： 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账号，即可开始考试