CSP2024 前集训：csp-s模拟11

前言

T1 挂了，后面几道赛时都不那么可做，T2 读假题了浪费太多时间，T3 没调出来。

T4 是原，但是整个机房只有一个人当时改了，所以还是没人写，因为 T4 是原，还加了个 T5，也不太可做。

T1 玩水

对于一个点 \((i,j)\)，若 \(s_{i+1,j}=s_{i,j+1}\) 则称其为分点，若一个分店后面还有分点或两个分点相邻则有解，二维前缀和维护即可。

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1010;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=true;register char c=getchar_unlocked();for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int T,n,m,ans,sum[N][N]; char s[N][N]; bitset<N>spl[N];
int calc(int x1,int y1,int x2,int y2) 
{return x1--,y1--,sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];}
signed main()
{freopen("water.in","r",stdin),freopen("water.out","w",stdout);for(read(T);T;T--,ans=0,memset(sum,0,sizeof(sum))){read(n,m); for(int i=1;i<=n;i++) spl[i].reset();for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)for(s[i][j]=getchar_unlocked();s[i][j]<'a'||s[i][j]>'z';s[i][j]=getchar_unlocked());for(int i=1;i<=n-1;i++) for(int j=1;j<=m-1;j++)if(s[i][j+1]==s[i+1][j]) spl[i][j]=1;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+spl[i][j];for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if((spl[i][j]&&spl[i][j+1])||(spl[i][j]&&spl[i+1][j])||(spl[i-1][j-1]&&calc(i,j,n,m))){ans=1; break;}write(ans),puts("");}
}

T2 AVL 树

中序遍历最小等价于前序遍历最小，因为一个点选了他的父亲必选。

那么贪心，若当前点为其父亲的左二子，则计算出其右儿子最少需要多少节点，若计算出的 \(\le k\) 就保留当前点即可。

具体实现挺屎的不想说了，统计最小最大深度，找一下规律维护。

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e5+10;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=true;register char c=getchar_unlocked();for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,rt,sum,f[30],h[N],fa[N],ls[N],rs[N],dep[N],lim[N],used[N]; bitset<N>ans;
void dfs(int x)
{if(!x) return ; h[x]=dep[x]=dep[fa[x]]+1;dfs(ls[x]),dfs(rs[x]),h[x]=max({h[x],h[ls[x]],h[rs[x]]});
}
bool check(int x)
{sum=lim[0]=0; for(int i=x;i;sum+=!ans[i],i=fa[i]) if(ls[fa[i]]==i)sum+=f[max({used[fa[i]]-1,dep[x]-1,lim[rs[fa[i]]]})-dep[fa[i]]];return sum<=m;
}
void insert(int x)
{used[x]=max(used[x],dep[x]); for(int i=x,tmp;i;i=fa[i]){m-=!ans[i],ans.set(i),used[fa[i]]=max(used[fa[i]],dep[x]);if(ls[fa[i]]==i&&(tmp=rs[fa[i]])) lim[tmp]=max(lim[tmp],used[fa[i]]-1);}
}
void solve(int x)
{if(!x) return ; if(check(x)) insert(x);if(!ls[x]||!rs[x]) lim[ls[x]+rs[x]]=max(lim[ls[x]+rs[x]],lim[x]);else if(h[ls[x]]>=lim[x])lim[ls[x]]=max(lim[ls[x]],lim[x]),lim[rs[x]]=max(lim[rs[x]],lim[x]-1);else lim[ls[x]]=max(lim[ls[x]],lim[x]-1),lim[rs[x]]=max(lim[rs[x]],lim[x]);solve(ls[x]),solve(rs[x]);
}
signed main()
{freopen("avl.in","r",stdin),freopen("avl.out","w",stdout);read(n,m); for(int i=1;i<=n;i++) read(fa[i]),fa[i]==-1?fa[rt=i]=0:(i<fa[i]?ls[fa[i]]=i:rs[fa[i]]=i);dfs(rt); f[1]=1; for(int i=2;i<=h[rt];i++) f[i]=f[i-1]+f[i-2]+1;solve(rt); for(int i=1;i<=n;i++) write(ans[i]);
}

T3 暴雨

水到处流很烦，考虑用一个最高的土地将两边分开，这样只会往一遍流了，这样枚举这个最高的土地已经 \(O(k)\) 了。

然后直接 DP 转移，\(f_{i,j,k,0/1}\) 表示到了第 \(i\) 个土地、最大值位置为 \(j\)、铲了 \(k\) 块、奇偶性时的方案数，直接转移即可，考虑铲 \(k\) 次做多产生 \(k+1\) 个最大值，由此一次 DP 复杂度为 \(O(nk^2)\)。

两遍正序（倒序）各跑一遍合并即可，

细节上，发现 \(j\) 时间是 \(O(k)\)，但空间开了 \(O(n)\) （因为这样好写）会炸，所以 \(i\) 这一维滚一下即可；同时枚举过的最大值视为已经铲掉，不能再铲。

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define mkp make_pair
#define se second
using namespace std;
const int N=25010,M=30,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=true;register char c=getchar_unlocked();for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,ans,a[N],id[N],mx[N][M],cnt1[M][2],cnt2[M][2],f[2][N][M][2];
set<pair<int,int> >s;
void dp(int len,int maxx)
{reverse(a+1,a+1+n),s.clear();memset(f,0,sizeof(f)),f[0][0][0][0]=f[1][1][0][0]=1,f[1][0][1][0]=!!a[1];for(int i=1,j;i<=len;mx[i][++j]=0,i++){for(s.insert(mkp(a[i],i)),j=0;s.size()>maxx+2;s.erase(s.begin()));for(auto it=s.begin();it!=s.end();it++) mx[i][++j]=it->se;}for(int i=2,x=0,y=1;i<=len;i++,x^=1,y^=1){memset(f[x][i],0,sizeof(f[x][i])); for(int j=1,h;j<=maxx+2&&mx[i][j-1];j++){if((h=mx[i][j])==i) continue; bool tmp; memset(f[x][h],0,sizeof(f[x][h]));for(int k=0;k<=min(i,maxx);k++){if(a[i]>=a[h]) (f[x][i][k][0]+=f[y][h][k][0])%=P,(f[x][i][k][1]+=f[y][h][k][1])%=P;else f[x][h][k][0]=f[y][h][k][tmp=(a[h]-a[i])&1],f[x][h][k][1]=f[y][h][k][!tmp];if(k>0&&a[i]) (f[x][h][k][0]+=f[y][h][k-1][tmp=a[h]&1])%=P,(f[x][h][k][1]+=f[y][h][k-1][!tmp])%=P;}}}
}
signed main()
{freopen("rain.in","r",stdin),freopen("rain.out","w",stdout);read(n,m); for(int i=1;i<=n;i++) read(a[i]),id[i]=i,mx[i][0]=-1; mx[0][0]=-1;sort(id+1,id+1+n,[](int x,int y){return a[x]>a[y];}); reverse(a+1,a+1+n);for(int o=m,now;~o;a[n-now+1]=0,o--){now=id[m-o+1],memset(cnt1,0,sizeof(cnt1)),memset(cnt2,0,sizeof(cnt2));dp(now-1,min(now-1,o));for(int i=0;i<=min(now-1,o);i++) for(int j=1;j<=min(now-1,o)+2&&mx[now-1][j-1];j++){(cnt1[i][0]+=f[(now-1)&1][mx[now-1][j]][i][0])%=P;(cnt1[i][1]+=f[(now-1)&1][mx[now-1][j]][i][1])%=P;}dp(n-now,min(n-now,o));for(int i=0;i<=min(n-now,o);i++) for(int j=1;j<=min(n-now,o)+2&&mx[n-now][j-1];j++){(cnt2[i][0]+=f[(n-now)&1][mx[n-now][j]][i][0])%=P;(cnt2[i][1]+=f[(n-now)&1][mx[n-now][j]][i][1])%=P;}for(int i=0;i<=min(now-1,o);i++) (ans+=(1ll*cnt1[i][0]*cnt2[o-i][0]%P+1ll*cnt1[i][1]*cnt2[o-i][1]%P)%P)%=P;}write(ans);
}

T4 置换

抽象题，看 Pursuing_OIer 的博吧。

T5 传统题

懒得改，咕了咕了。