发布时间:2023-03-29 18:13:10
编辑:小妹来源:网络浏览:次
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,...的贡献
于是我们可以分别统计这两种,加上初始答案即可
代码如下:
using namespace std;
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;
}
2023年USACO公开赛铜组P2
模拟题,需分析问题先后性
P2题目:
向下滑动查看
题目解析
USACO的第二道题目是一个模拟题,比较考验选手的代码能力。选手需要有清晰的思路分析问题的先后性,明白先确定什么值再确定什么值。
分类讨论题
首先我们可以去考虑conjunction的数量,这个不能超过.的数量
其次考虑短句的数量,这个不能超过conjunction的数量+.的数量
然后我们可以通过枚举transitive-verb的数量和intransitive-verb的数量来确定单词的最多个数
接着我们依次将相应的单词拼接成短句,显然多出来的noun会添加在"transitive-verb"的后面
最后我们将短句拼接成句子,如果有多的"conjunction"符号就用它连接起来
代码如下:
using namespace std;
struct nd{
int a,b,c,d;
bool operator <(const nd x)const{
return d>x.d;
}
};
int main()
{
int T;
cin>>T;
while (T--)
{
int n,c,p;
cin>>n>>c>>p;
string A,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);
}
int maxand=min((int)(Q4.size()),p);
int maxword=maxand+p;
vector<nd> ans;
rep(s1,0,Q3.size()) //√∂æŸ ˝¡ø
{
int s2=min((int)(Q2.size()),maxword-s1);
s2=min(s2,(int)(Q1.size())-2*s1);
int s3=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());
int s1=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)
{
string s=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);
}
int round=min((int)(Q4.size()),(int)(Q.size())/2);
cout<<O+round<<endl;
string W; //Ω´æ‰◊”¡¨Ω”∫Û ‰≥ˆ
rep(i,0,round-1)
{
W+=Q[i*2]+" "+Q4.back()+" "+Q[i*2+1]+". ";
Q4.pop_back();
}
for (int i=round*2;i<Q.size();i++)
W+=Q[i]+". ";
for (int i=0;i+1<W.length();i++)
cout<<W[i];
cout<<endl;
}
return 0;
}
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
因此可以计算每个点进行了几轮移动进行模拟
代码如下:
using namespace std;
int n,k,t;
int main()
{
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; else L[i]=L[i-1];
rep(i,1,k) R[a[i]]=a[i+1]-a[i];
rep(i,0,n-1)
{
int tim=t-i+L[i];
int round=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<<p[i]<<" ";
cout<<p[n-1];
return 0;
}
广子来了
犀牛计算机教研组以USACO组织推荐的官方网站USACO guide上的知识点为主,对各组别算法进行了整理和更新,并创作了500+的模拟真题,助力学生冲击USACO金银成绩!
USACO竞赛冲冲冲!
AP03-08
IBDP03-07
小托福04-03
美国留学04-05
微信咨询
支付二维码