2023 USACO 3月公开赛铜组赛后总结

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

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

本次考试还是以暴力搜索和模拟为主，尤其是第二题，需要仔细审题，如果不理解题意会很难下手。

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

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

USACO教研组老师为大家解析了本次公开赛铜组的题目。

2023年USACO公开赛铜组P1

数理逻辑题，需注意问题转化

P1题目：

题目解析

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;}

2023年USACO公开赛铜组P2

模拟题，需分析问题先后性

P2题目：

题目解析

USACO的第二道题目是一个模拟题，比较考验选手的代码能力。选手需要有清晰的思路分析问题的先后性，明白先确定什么值再确定什么值。

分类讨论题

首先我们可以去考虑conjunction的数量，这个不能超过.的数量

其次考虑短句的数量，这个不能超过conjunction的数量+.的数量

然后我们可以通过枚举transitive-verb的数量和intransitive-verb的数量来确定单词的最多个数

接着我们依次将相应的单词拼接成短句,显然多出来的noun会添加在"transitive-verb"的后面

最后我们将短句拼接成句子，如果有多的"conjunction"符号就用它连接起来

代码如下：

#include#include#definerep(i,h,t) for (int i=h;i<=t;i++)#definedep(i,t,h) for (int i=t;i>=h;i--)usingnamespacestd;structnd{inta,b,c,d;booloperator<(constnd x)const{returnd>x.d;}};intmain(){intT;cin>>T;while(T--){intn,c,p;cin>>n>>c>>p;stringA,B;vector<string> Q1,Q2,Q3,Q4;//¥Ê¥¢4÷÷µ•¥rep(i,1,n){cin>>A>>B;if(B=="noun") Q1.push_back(A);if(B=="intransitive-verb") Q2.push_back(A);if(B=="transitive-verb") Q3.push_back(A);if(B=="conjunction") Q4.push_back(A);}intmaxand=min((int)(Q4.size()),p);intmaxword=maxand+p;vector ans;rep(s1,0,Q3.size())//√∂æŸ ˝¡ø{ints2=min((int)(Q2.size()),maxword-s1);s2=min(s2,(int)(Q1.size())-2*s1);ints3=min(c,(int)(Q1.size())-2*s1-s2);if(!s1)while(s3>0) s3--;if(s1<0||s2<0||s3<0)continue;ans.push_back({s1,s2,s3,3*s1+2*s2+s3});}sort(ans.begin(),ans.end());ints1=0,s2=0,s3=0,O=0;//µ√≥ˆ◊Ó”≈µƒ«Èøˆif(ans.size()){s1=ans[0].a,s2=ans[0].b,s3=ans[0].c,O=ans[0].d;}vector<string> Q;//¥¶¿Ì≥ˆ∂‘”¶µƒæ‰◊”rep(i,1,s2){Q.push_back(Q1.back()+" "+Q2.back());Q1.pop_back(); Q2.pop_back();}rep(i,1,s1){strings=Q1.back()+" "+Q3.back();Q1.pop_back(); Q3.pop_back();s+=" "+Q1.back();Q1.pop_back();if(i==1){while(s3--){s+=", "+Q1.back();Q1.pop_back();}}Q.push_back(s);}intround=min((int)(Q4.size()),(int)(Q.size())/2);cout<endl;stringW;//Ω´æ‰◊”¡¨Ω”∫Û ‰≥ˆrep(i,0,round-1){W+=Q[i*2]+" "+Q4.back()+" "+Q[i*2+1]+". ";Q4.pop_back();}for(inti=round*2;iW+=Q[i]+". ";for(inti=0;i+1cout<cout<<endl;}return0;}

2023年USACO公开赛铜组P3

数理逻辑题，总结样例规律

P3题目：

题目解析

USACO的第三道题目也是一个性质题，初看这个问题很难解决，仔细观察可以发现对于每个点它的移动是具有周期性的，发现了这个代码就比较简单了。

考虑一个位置上的值p假如从a[i]位置移动到a[i+1]位置,那么下一次对他进行变化一定是由当前a[i]移动过去造成下一次修改的

所以每个点的运动都具有周期性，每经过t秒，就会往后移动t的距离

其中t=a[i+1]-a[i],特殊的,我们令a[k+1]=a[1]+n

因此可以计算每个点进行了几轮移动进行模拟

代码如下：

#include#includeusingnamespacestd;#definerep(i,h,t) for (int i=h;i<=t;i++)#definedep(i,t,h) for (int i=t;i>=h;i--)intn,k,t;intmain(){cin>>n>>k>>t;vector<int> a(n+10),L(n+10),R(n+10),p(n+10);vector<bool> h(n+10);rep(i,1,k)cin>>a[i];a[k+1]=a[1]+n;rep(i,1,k) h[a[i]]=1;rep(i,0,n-1)if(h[i]) L[i]=i;elseL[i]=L[i-1];rep(i,1,k) R[a[i]]=a[i+1]-a[i];rep(i,0,n-1){inttim=t-i+L[i];intround=tim/R[L[i]];if(tim%R[L[i]]!=0) round++;p[(i+round*R[L[i]])%n]=i;}rep(i,0,n-2)cout<" ";cout<-1];return0;}