由于学校要求，过来打 USACO。
似乎要求起码升到白金？
由于是第一次打，只有从铜组开始了。
Brouze
简单题，就给核心代码。
30min AK。
Leaders
http://usaco.org/current/index.php?page=viewproblem&cpid=1263
chr C[100005];uint R[100005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u%s",&n,C);for(uint i=0;i<n;i++)scanf("%u",R+i);
chr c=*C;uint p=0;while(C[p]==c)p++;
uint ans=0;for(uint i=0;i<p;i++)ans+=R[i]>p;
bol ok=R[0]==p;for(uint i=p;i<n;i++)ok&=C[i]!=c;
ans+=ok;
printf("%u\n",ans);
return 0;
}
Air Cownditioning II
http://usaco.org/current/index.php?page=viewproblem&cpid=1264
uint L[25],R[25],C[25],A[25],B[25],P[25],M[25],Cnt[105];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n,m;scanf("%u%u",&n,&m);
for(uint i=0;i<n;i++)scanf("%u%u%u",L+i,R+i,C+i),L[i]--;
for(uint i=0;i<m;i++)scanf("%u%u%u%u",A+i,B+i,P+i,M+i),A[i]--;
uint ans=-1;
for(uint i=0;i<(1u<<m);i++){
for(uint i=0;i<100;i++)Cnt[i]=0;
uint wil=0;
for(uint j=0;j<m;j++)if(i>>j&1){
wil+=M[j];for(uint k=A[j];k<B[j];k++)Cnt[k]+=P[j];
}
bol ok=1;
for(uint j=0;j<n;j++)for(uint k=L[j];k<R[j];k++)ok&=Cnt[k]>=C[j];
if(ok)_min(ans,wil);
}
printf("%u\n",ans);
return 0;
}
Moo Operations
http://usaco.org/current/index.php?page=viewproblem&cpid=1265
chr C[105];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint t;scanf("%u",&t);
while(t--){
uint n=0;scanf("%s",C);while(C[n])n++;
uint ans=-1;
for(uint i=1;i+1<n;i++)if(C[i]=='O')
_min(ans,n-1-(C[i-1]=='M')-(C[i+1]=='O'));
printf("%d\n",(int)ans);
}
return 0;
}
Silver
1h30min AK。
Find and Replace
http://usaco.org/current/index.php?page=viewproblem&cpid=1266
恶心的题目，做了 1h。
基环树和环的答案是不同的！！！
由于只能变字母，要特判 \(52\rightarrow52\) 的全环情况！！！
chr A[100005],B[100005],To[128];
bol Gone[128];
voi solve(){
for(uint i=0;i<=127;i++)Gone[i]=0;
uint ans=0;scanf("%s%s",A,B);
for(uint i=0;A[i];i++){
if(!Gone[(uint)A[i]])To[(uint)A[i]]=B[i],Gone[(uint)A[i]]=1,ans+=A[i]!=B[i];
if(To[(uint)A[i]]!=B[i]){puts("-1");return;}
}
if(ans){
std::set<uint>S1,S2;
for(uint c=0;c<=127;c++)if(Gone[c])S1.insert(c),S2.insert(To[c]);
if(S1.size()==52&&S2.size()==52){puts("-1");return;}
for(uint c:S1)if((uint)To[c]==c)Gone[c]=false;
for(uint p:S1)if(Gone[p]&&!S2.count(p)){
std::vector<uint>V;
while(Gone[p])Gone[p]=false,V.push_back(p),p=To[p];
}
for(uint p:S1)if(Gone[p]&&S2.count(p)){
std::vector<uint>V;
while(Gone[p])Gone[p]=false,V.push_back(p),p=To[p];
for(auto s:V)if(s==p)ans++;
}
}
printf("%u\n",ans);
}
Following Directions
http://usaco.org/current/index.php?page=viewproblem&cpid=1267
注意到形成树的结构，直接记录每个子树大小即可。
线段树分治可以做，但没有必要。
chr C[2005][2005];
uint R[2005],D[2005];
uint V[2005][2005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n,q;scanf("%u",&n);
for(uint i=0;i<n;i++)scanf("%s%u",C[i],R+i);
for(uint i=0;i<n;i++)scanf("%u",D+i);
for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)V[i][j]=1;
for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)(C[i][j]=='R'?V[i][j+1]:V[i+1][j])+=V[i][j];
uint sum=0;
for(uint i=0;i<n;i++)sum+=V[i][n]*R[i]+V[n][i]*D[i];
printf("%u\n",sum);
scanf("%u",&q);
while(q--){
uint x,y;scanf("%u%u",&x,&y),x--,y--;
for(uint i=x,j=y;;){
C[i][j]=='R'?j++:i++,V[i][j]-=V[x][y];
if(i==n){sum-=V[x][y]*D[j];break;}
if(j==n){sum-=V[x][y]*R[i];break;}
}
C[x][y]^='R'^'D';
for(uint i=x,j=y;;){
C[i][j]=='R'?j++:i++,V[i][j]+=V[x][y];
if(i==n){sum+=V[x][y]*D[j];break;}
if(j==n){sum+=V[x][y]*R[i];break;}
}
printf("%u\n",sum);
}
return 0;
}
Moo Route
http://usaco.org/current/index.php?page=viewproblem&cpid=1268
画个图就做完了。
uint A[100005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u",&n);
for(uint i=0;i<n;i++)scanf("%u",A+i),A[i]--;
for(uint p=0;A[p];)
{
while(!p||A[p]>A[p-1])--A[p++],putchar('R');
while(p&&A[p-1])--A[--p],putchar('L');
}
for(uint i=0;i<n;i++)putchar('L');
putchar('\n');
return 0;
}
Gold
2h AK。
Find and Replace
http://usaco.org/index.php?page=viewproblem&cpid=1269
考虑动态维护每个串的每个字母会被哪个规则替换，则加入一条新规则时，其将作用于之前所有未被替换的某个字母。
这个可以拿 \(26\) 个 vector 直接维护。
记录下来后，整个结构是一张 DAG，把每个串串长记录下来即可。
然后如果直接在 DAG 上 dfs，很容易卡到 \(O(nq)\)（\(n\) 表示查询区间长度）：
1 200000 200000
a aa
a aa
a aa
a aa
...
a aa
a b
b a
a b
b a
...
b a
这个东西每找一个字符都会跑满整一层，不优。
考虑在 DAG 的每个节点处，若其对应串长不超过 \(B\)，则把其整个字符串记录下来。
查询时如果串长不超过 \(B\)，就不再往下递归，直接输出这段区间。
容易分析这样的总复杂度为 \(O(q(B+\frac nB))\)，取 \(B=\sqrt n\)，得复杂度为 \(O(q\sqrt n)\)。
由于这个东西非常跑不满，直接取 \(B=20\) 即可通过。
（当然也不排除可以进一步分析出 \(O(q(B+\frac n{B^2}))\) 等更紧的界，因为我会构造的最坏数据只能达到这个复杂度级别，那样的平衡复杂度就是 \(O(q\ {}^3\!\!\!\!\sqrt n)\)）
std::vector<std::pair<uint,uint> >Find[26];
std::vector<chr>S[200005],S2[200005];
std::vector<uint>To[200005];
chr C[200005];
ullt Len[200005];
voi dfs(uint q,ullt l,ullt r){
if(S2[q].size()){
for(uint i=l;i<r;i++)putchar(S2[q][i]);
return;
}
for(uint i=0;i<To[q].size()&&l<r;i++)
if(~To[q][i])
if(l<Len[To[q][i]])
if(r<=Len[To[q][i]])dfs(To[q][i],l,r),l=r=0;
else dfs(To[q][i],l,Len[To[q][i]]),r-=Len[To[q][i]],l=0;
else r-=Len[To[q][i]],l-=Len[To[q][i]];
else
{
if(!l)putchar(S[q][i]);else l--;
r--;
}
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
ullt l,r;uint q;scanf("%llu%llu%u",&l,&r,&q);
S[0]={'a'},To[0]={-1u},Find[0].push_back({0,0});
for(uint i=1;i<=q;i++){
scanf("%s",C);for(auto s:Find[*C-'a'])To[s.first][s.second]=i;
Find[*C-'a'].clear(),scanf("%s",C);
for(uint j=0;C[j];j++)S[i].push_back(C[j]),Find[C[j]-'a'].push_back({i,j});
To[i].resize(S[i].size(),-1);
}
for(uint i=q;~i;i--){
for(uint j=0;j<To[i].size();j++)
if(~To[i][j])_min(Len[i]+=Len[To[i][j]],2000000000000000000llu);
else _min(++Len[i],2000000000000000000llu);
if(Len[i]<=20)for(uint j=0;j<To[i].size();j++){
if(~To[i][j])S2[i].insert(S2[i].end(),S2[To[i][j]].begin(),S2[To[i][j]].end());
else S2[i].push_back(S[i][j]);
}
}
dfs(0,l-1,r),putchar('\n');
return 0;
}
Lights Off
http://usaco.org/index.php?page=viewproblem&cpid=1270
感觉题目里给的这个 move 操作很奇怪，数据范围也很怪（\(n\) 很小但 \(T\) 很大），时限也给了 \(4s\)，考虑大胆猜结论：答案很小，是 \(O(n)\) 或者类似的级别，可以暴力枚举；但是信息的预处理复杂度与 \(2^n\) 有关。
考虑把对答案的贡献拆分，发现操作了 \(a\) 步时，原有的开关串会带来其旋转 \(0,1,2,\dots,a-1\) 步后的结果的贡献，自己扭动的开关会带来长度为 \(1,2,3,\dots,a\) 的连续 \(1\) 的贡献。
我们由于在暴力枚举答案，前面的贡献容易直接算掉，考虑判断剩下部分的贡献是否可以用由长度为 \(1,2,3,\dots,a\) 的连续 \(1\) 的贡献异或而成。
这个东西我们考虑 dp 预处理，设 \(f_{a,v}=\tt true\) 表示 \(v\) 可以由长度为 \(1,2,3,\dots,a\) 的连续 \(1\) 的贡献异或而成，反之则不能。
容易有一个 \(O(na2^n)\) 复杂度的 dp。
把 \(a\) 取遍 \(0\sim n\) 甚至 \(0\sim n+5\)，把结果打个表观察一下，容易发现，\(k>n/2\) 时总有 \(f_{k,v}=f_{k+4,v}\)。
证明感觉很复杂，我不会证，但是我把 \(n=2,\dots,20\) 中随机取了几个验证了一下，似乎都是对的。那就当做这是对的吧。
因此 \(a\) 更大的时候可以直接调用 \(a\) 很小的值，于是直接把 \(a\) 预处理到 \(n/2+4\) 是可行的！
总复杂度不会分析，但是应该是 \(O(n^22^n+Tn)\) 的，实测可以通过。
uint n;chr C[25];
bol Ok[21][1u<<20|1];
inline uint nxt(uint v){return(v<<1&((1u<<n)-1))|(v>>(n-1)&1);}
voi solve(){
uint a=0,b=0;
scanf("%s",C);for(uint i=0;i<n;i++)a|=(C[i]=='1')<<i;
scanf("%s",C);for(uint i=0;i<n;i++)b|=(C[i]=='1')<<i;
uint ans=0;
while(!Ok[ans<=n/2?ans:(ans-n/2-1)%4+n/2+1][a])ans++,a^=b,b=nxt(b);
printf("%u\n",ans);
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint t;scanf("%u%u",&t,&n);
Ok[0][0]=1;
for(uint i=1,v=1,t=1;i<=n/2+4;i++,v^=t=nxt(t))
for(uint t=0;t<n;t++,v=nxt(v))for(uint j=0;j<(1u<<n);j++)
Ok[i][j]|=Ok[i-1][j^v];
// for(uint i=1;i<=n/2+4;i++,putchar('\n'))
// for(uint j=0;j<(1u<<n);j++)
// putchar('0'+Ok[i][j]);
while(t--)solve();
return 0;
}
Moo Route
http://usaco.org/index.php?page=viewproblem&cpid=1271
银组对应题目的计数版本！
把 \(a\) 除二，仅仅考虑向右的路径。
显然我们可以把向右的路径自上而下排成一排，使得上一行的右端点大于下一行的左端点。
对这些路径从左往右扫描，当前列应当剩下恰好 \(a\) 条路径。
假设扫描过程中某一步 \(a\) 变成了 \(a'\)。
当 \(a'>a\) 时，你要在之前的路径基础上增加 \(a'-a\) 条，并且均放在之前的某些路径的下面，方案数为 \(\binom{a'-1}{a-1}\)；之所以不能放在最上面一条路径的上面，是因为上一行的右端点应大于下一行的左端点。
当 \(a'\le a\) 时，你要从之前的路径中选出 \(a'\) 条留下，其余的删除，有 \(\binom a{a'}\) 种方案；这个不会影响后续插入时对方案数的分析，因为任意一个被删除的路径下面之后也不能再有路径了。
于是答案即为
\[\prod_{i=1}^{N-1}\begin{cases}\binom{A_i-1}{A_{i-1}-1}&(A_i>A_{i-1})\\\binom{A_{i-1}}{A_i}&(A_i\le A_{i-1})\end{cases} \]总复杂度 \(O(T)\)。（其中 \(T=\sum A\)）
（从某种角度上来看，这种做法其实质是构造了一个双射）
const ullt Mod=1e9+7;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
modint P[4000005],Q[4000005];
uint A[100005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
P[0]=1;for(uint i=1;i<=4000000;i++)P[i]=P[i-1]*i;
Q[4000000]=P[4000000].inv();for(uint i=4000000;i;i--)Q[i-1]=Q[i]*i;
uint n;scanf("%u",&n);for(uint i=0;i<n;i++)scanf("%u",A+i),A[i]>>=1;
// modint ans=Q[A[0]]*P[A[0]-1];
modint ans=1;
for(uint i=1;i<n;i++)
if(A[i]<=A[i-1])ans*=P[A[i-1]]*Q[A[i]]*Q[A[i-1]-A[i]];
else ans*=P[A[i]-1]*Q[A[i-1]-1]*Q[A[i]-A[i-1]];
ans.println();
return 0;
}
Platinum
力不从心，打不起哩。
标签：index,QAQ,USACO2023Jan,usaco,uint,freopen,org,游记 From： https://www.cnblogs.com/myee/p/USACO2023Jan.html