2023-2024年USACO首次月考題目出爐！銀組第三題真題及解析
2023-2024賽季UASCO首場月賽已經(jīng)圓滿結(jié)束，晉級賽的最新試題也已經(jīng)公布。沒能當(dāng)場晉級的同學(xué)們可以耐心等待一周，一周內(nèi)USACO官方將會公布本次晉級賽成績。如果沒有晉級，12月可以當(dāng)做一個(gè)練手+熟悉賽制的環(huán)節(jié)，1、2月的月賽持續(xù)發(fā)力，USACO可以重復(fù)挑戰(zhàn)。
今天給大家分享銀級試題和解析，參賽的同學(xué)來看看解題思路，沒參賽的同學(xué)來看看難度如何？
銀組第三題
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時(shí)可以擊中多少個(gè)目標(biāo)。答案在change[1]-change[5]。再用hit[1-5][位置]記錄每個(gè)位置被擊中了多少次。
然后i從左往右一位位求i之前已經(jīng)固定，i改變以后，能擊中多少次；
這樣求完以后只需要把第i位固定帶來的影響，更新到change和hit里就可以了。
i從左往右固定過程中，如果這一位是L和R只影響位置p；
但如果這一位是F，那么固定以后，就要更新hit里的次數(shù)。因?yàn)樗?2 -1 +1 +2都不可能發(fā)生了。
所以更新了兩部分內(nèi)容。
1. 當(dāng)前位置p，如果之后的F因?yàn)?2 -1 +1 +2擊中過它，現(xiàn)在應(yīng)該i已經(jīng)固定，它一定會被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0，change對應(yīng)更新。
2. 當(dāng)前位置p，-2 -1 +1 +2以后的位置的hit數(shù)減少1次，如果減到0就更新change
最終就是，確定會擊中的數(shù)量cnt，和change數(shù)組維護(hù)的i之后的-2 -1 +1 +2以后的4種不同擊中數(shù)量，根據(jù)L->R R->L之類的變化情況相加。
時(shí)間復(fù)雜度： O(n)
知識點(diǎn)：思維難題
USACO歷年真題及參考書，掃碼領(lǐng)取！【翰林提供報(bào)名指導(dǎo)服務(wù)】
USACO歷年真題及參考書
2023-2024年USACO活動時(shí)間
第一次月賽：2023年12月15日-18日
第二次月賽：2024年1月26日-29日
第三次月賽：2024年2月16日-19日
美國公開賽：2024年3月15日-18日
（中國學(xué)生只能參加到公開賽）
集訓(xùn)營：2024年5月23日-6月1日
EGOI：2024年7月21日-27日（荷蘭）
IOI：2024年9月1日-8日（埃及）
報(bào)名方式：參賽者可隨時(shí)在官網(wǎng)注冊賬號，注冊。報(bào)名，只需在活動時(shí)間登陸完成答題即可。
官網(wǎng)地址：usaco.org
提交之后，官網(wǎng)會發(fā)送一份郵件到您郵箱，郵件中有賬號密碼
利用已知的賬號于密碼，登錄USACO賬號，即可開始考試
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費(fèi)領(lǐng)取
