2023年USACO公開賽銅組P1題目全解析

2023年3月USACO公開賽難度如何？2023年3月USACO公開賽真題解析哪裏有？2023US.OPEN美國公開賽難度是月賽的1.5倍，題目難度較大。同時，近三年公開賽的難度是逐年遞增的。USACO想要拿獎，還是不建議自學，那麽(me) USACO培訓課程哪裏好？

2023年USACO考情回顧

2023年3月24-27日 USACO US.OPEN美國公開賽順利結束。大家感覺怎麽(me) 樣呢？

本次US.OPEN美國公開賽難度是月賽的1.5倍，題目難度較大。同時，近三年公開賽的難度是逐年遞增的。

本次考試還是以暴力搜索和模擬為(wei) 主，尤其是第二題，需要仔細審題，如果不理解題意會(hui) 很難下手。與(yu) 我們(men) 考前預測是一致的USACO 3月公開賽獨家考情預測！

銅組第1、2題都考察了字符串的知識點，如果對字符串知識點不了解的學生就要多加小心了。

第3題是一道邏輯題目，有點類似2020年2月銅組P3 swapity swap。

USACO教研組老師為(wei) 大家解析了本次公開賽銅組的題目。我們(men) 一起來看看~

2023 USACO公開賽銅組P1

數理邏輯題，需注意問題轉化

P1題目：

P1 FEB:

Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over (1 <= N <= 2 * 10 5) text messages. Their conversation can be represented by a string S of length N where Is is either B or E, meaning the ith message was sent by Bessie or Elsie, respectively.

However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of S are F, meaning Farmer John obfuscated the message and the sender is unknown.

The excitement level of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring BB or EE in S. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of S.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line will consist of one integer N.

The next line contains S

OUTPUT FORMAT (print output to the terminal / stdout):

First output K, the number of distinct excitement levels possible. On the next K lines, output the excitement levels, in increasing order.

SAMPLE INPUT:

4

BEEF

SAMPLE OUTPUT:

2

1

2

SAMPLE INPUT:

9

FEBFEBFEB

SAMPLE OUTPUT:

2

2

3

SAMPLE INPUT:

10

BFFFFFEBFE

SAMPLE OUTPUT:

3

2

4

6

SCORING:

      • Inputs 4-8: N ≤ 10

      • Inputs 9-20: No additional constraints.

題目解析

USACO的第一道題目需要分析出題目的性質，分為(wei) F左右都有元素和F隻有一邊有元素進行討論,問題轉化之後就比較簡單了。

考慮每一段"XFF...FFY"可以產(chan) 生多少貢獻

結論是如果X=Y,能產(chan) 生0,2,4,6,...的貢獻

否則能產(chan) 生1,3,5,7,...的貢獻

對於(yu) 下麵的情況,整體(ti) 減一可以得到和上麵一樣的結論

再考慮邊緣,FF...FFY可以產(chan) 生多少貢獻

發現能產(chan) 生0,1,2,...的貢獻

於(yu) 是我們(men) 可以分別統計這兩(liang) 種，加上初始答案即可

代碼如下：

#include <iosestream>using namespace std;#define rep(i,h,t) for (int i=h;i<=t;i++)#define dep(i,t,h) for (int i=t;i>=h;i--)int n;char s[200010];bool t[200010];int main(){    scanf("%d",&n);    scanf("%s",s+1);    int O=0;    rep(i,1,n)      if (s[i]==s[i-1]&&s[i]!='F') O++;    int Q1=0,Q2=0;    rep(i,1,n)    {        if (s[i]=='F')        {            int j=i;            while (s[j]=='F'&&j<=n) j++;            j--;            int num=j-i+1;            if (i!=1&&j!=n)            {                if (s[i-1]==s[j+1]) num++;                O+=num%2;                Q1+=num/2;            } else Q2+=num;            i=j;        }    }    rep(i,0,Q1)      rep(j,0,Q2)        t[i*2+j+O]=1;    int OO=0;    rep(i,0,n-1)      if (t[i]) OO++;    cout<<OO<<endl;    rep(i,0,n-1)      if (t[i]) cout<<i<<endl;    return 0;