2023年3月24-27日 USACO US.OPEN美國公開賽順利結束。大家感覺怎麽(me) 樣？
本次US.OPEN美國公開賽難度是月賽的1.5倍，題目難度較大。同時，近三年公開賽的難度是逐年遞增的。
本次考試還是以暴力搜索和模擬為(wei) 主，尤其是第二題，需要仔細審題，如果不理解題意會(hui) 很難下手。
銅組第1、2題都考察了字符串的知識點，如果對字符串知識點不了解的學生就要多加小心了。
第3題是一道邏輯題目，有點類似2020年2月銅組P3 swapity swap。
USACO教研組老師為(wei) 大家解析了本次公開賽銅組的題目。
2023年USACO公開賽銅組P1
數理邏輯題，需注意問題轉化
P1題目：
題目解析
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) 種，加上初始答案即可
代碼如下：
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的第二道題目是一個(ge) 模擬題，比較考驗選手的代碼能力。選手需要有清晰的思路分析問題的先後性，明白先確定什麽(me) 值再確定什麽(me) 值。
分類討論題
首先我們(men) 可以去考慮conjunction的數量，這個(ge) 不能超過.的數量
其次考慮短句的數量，這個(ge) 不能超過conjunction的數量+.的數量
然後我們(men) 可以通過枚舉(ju) transitive-verb的數量和intransitive-verb的數量來確定單詞的最多個(ge) 數
接著我們(men) 依次將相應的單詞拚接成短句,顯然多出來的noun會(hui) 添加在"transitive-verb"的後麵
最後我們(men) 將短句拚接成句子，如果有多的"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的第三道題目也是一個(ge) 性質題，初看這個(ge) 問題很難解決(jue) ，仔細觀察可以發現對於(yu) 每個(ge) 點它的移動是具有周期性的，發現了這個(ge) 代碼就比較簡單了。
考慮一個(ge) 位置上的值p假如從(cong) a[i]位置移動到a[i+1]位置,那麽(me) 下一次對他進行變化一定是由當前a[i]移動過去造成下一次修改的
所以每個(ge) 點的運動都具有周期性，每經過t秒，就會(hui) 往後移動t的距離
其中t=a[i+1]-a[i],特殊的,我們(men) 令a[k+1]=a[1]+n
因此可以計算每個(ge) 點進行了幾輪移動進行模擬
代碼如下：
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;}
【競賽報名/項目谘詢+微信：mollywei007】
評論已經被關(guan) 閉。