2023年USACO公开赛铜组P1题目全解析

2023年3月USACO公开赛难度如何？2023年3月USACO公开赛真题解析哪里有？2023US.OPEN美国公开赛难度是月赛的1.5倍，题目难度较大。同时，近三年公开赛的难度是逐年递增的。USACO想要拿奖，还是不建议自学，那么USACO培训课程哪里好？

2023年USACO考情回顾

2023年3月24-27日 USACO US.OPEN美国公开赛顺利结束。大家感觉怎么样呢？

本次US.OPEN美国公开赛难度是月赛的1.5倍，题目难度较大。同时，近三年公开赛的难度是逐年递增的。

本次考试还是以暴力搜索和模拟为主，尤其是第二题，需要仔细审题，如果不理解题意会很难下手。与我们考前预测是一致的USACO 3月公开赛独家考情预测！

铜组第1、2题都考察了字符串的知识点，如果对字符串知识点不了解的学生就要多加小心了。

第3题是一道逻辑题目，有点类似2020年2月铜组P3 swapity swap。

USACO教研组老师为大家解析了本次公开赛铜组的题目。我们一起来看看~

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的第一道题目需要分析出题目的性质，分为F左右都有元素和F只有一边有元素进行讨论,问题转化之后就比较简单了。

考虑每一段"XFF...FFY"可以产生多少贡献

结论是如果X=Y,能产生0,2,4,6,...的贡献

否则能产生1,3,5,7,...的贡献

对于下面的情况,整体减一可以得到和上面一样的结论

再考虑边缘,FF...FFY可以产生多少贡献

发现能产生0,1,2,...的贡献

于是我们可以分别统计这两种，加上初始答案即可

代码如下：

#includeusingnamespacestd;#definerep(i,h,t) for (int i=h;i<=t;i++)#definedep(i,t,h) for (int i=t;i>=h;i--)intn;chars[200010];boolt[200010];intmain(){scanf("%d",&n);scanf("%s",s+1);intO=0;rep(i,1,n)if(s[i]==s[i-1]&&s[i]!='F') O++;intQ1=0,Q2=0;rep(i,1,n){if(s[i]=='F'){intj=i;while(s[j]=='F'&&j<=n) j++;j--;intnum=j-i+1;if(i!=1&&j!=n){if(s[i-1]==s[j+1]) num++;O+=num%2;Q1+=num/2;}elseQ2+=num;i=j;}}rep(i,0,Q1)rep(j,0,Q2)t[i*2+j+O]=1;intOO=0;rep(i,0,n-1)if(t[i]) OO++;cout<endl;rep(i,0,n-1)if(t[i])cout<endl;return0;