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賬號，即可開始考試
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
