csp-s模拟11
\(T1\) T2203. 玩水 (water) \(100pts\)
-
定义一个点 \((i,j)\) 是分点当且仅当 \(s_{i,j+1}=s_{i+1,j}\) ，而一个点 \((i,j)\) 是合点当且仅当 \((i-1,j-1)\) 是分点。
-
先考虑若只有两个人时，只要存在一个分点就一定有解。
-
扩展到三个人时，若存在一个合点可以通过向右或向下走到达另外一个分点或存在两个相邻的分点就一定有解，于是就转化为了二维偏序问题，因 \(n,m \le 1000\) 故二维前缀和维护即可。
点击查看代码
int sum[1010][1010],vis[1010][1010]; char c[1010][1010]; int main() { freopen("water.in","r",stdin); freopen("water.out","w",stdout); int t,n,m,flag,i,j,k; cin>>t; for(k=1;k<=t;k++) { flag=0; cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>c[i][j]; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { vis[i][j]=(i+1<=n&&j+1<=m&&c[i+1][j]==c[i][j+1]); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+vis[i][j]; flag|=(vis[i][j]==1&&(vis[i-1][j]==1||vis[i][j-1]==1||sum[i-1][j-1]>=1)); } } cout<<flag<<endl; } fclose(stdin); fclose(stdout); return 0; }
\(T2\) T2212. AVL 树 \(20pts\)
-
部分分
- \(20pts\) ：爆搜。
点击查看代码
int ch[500010][2],fa[500010],vis[500010],h[500010]; vector<int>ans,tmp; bool cmp(vector<int>a,vector<int>b) { if(a.size()<b.size()) { return false; } for(int i=0;i<a.size();i++) { if(a[i]>b[i]) { return false; } if(a[i]<b[i]) { return true; } } return false; } void print(int x) { if(x==0||vis[x]==0) { return; } h[x]=1; print(ch[x][0]); tmp.push_back(x); print(ch[x][1]); h[x]+=max(h[ch[x][0]],h[ch[x][1]]); } void dfs(int pos,int n,int k,int rt) { if(pos==n+1) { if(k==0) { int flag=1; for(int i=1;i<=n;i++) { if(vis[i]==1) { flag&=vis[fa[i]]; } } if(flag==1) { tmp.clear(); memset(h,0,sizeof(h)); print(rt); for(int i=1;i<=n;i++) { if(vis[i]==1) { flag&=(abs(h[ch[i][0]]-h[ch[i][1]])<=1); } } if(flag==1&&cmp(ans,tmp)==false) { ans=tmp; } } } } else { if(k>=1) { vis[pos]=1; dfs(pos+1,n,k-1,rt); } if(pos!=rt) { vis[pos]=0; dfs(pos+1,n,k,rt); } } } int main() { freopen("avl.in","r",stdin); freopen("avl.out","w",stdout); int n,k,rt=0,i; cin>>n>>k; for(i=1;i<=n;i++) { cin>>fa[i]; if(fa[i]==-1) { fa[i]=0; rt=i; } else { ch[fa[i]][fa[i]<i]=i; } } vis[0]=1; dfs(1,n,k,rt); memset(vis,0,sizeof(vis)); for(i=0;i<ans.size();i++) { vis[ans[i]]=1; } for(i=1;i<=n;i++) { cout<<vis[i]; } fclose(stdin); fclose(stdout); return 0; } -
正解
- 左根右的中序遍历在删除整棵子树的情况下，贪心策略为尽可能多地选择左子树的点，优先递归左子树。
- 考虑如何判断当前节点是否可以保留。回溯它的祖先节点直至根，对于该节点是左儿子的情况计算出保留这个节点至少需要右子树中有多少个节点。若剩下的 \(k\) 足够，那么就可以保留。
- 预处理 \(f_{i}\) 表示高度为 \(i\) 的 AVL 树所包含的最少节点数量，递推式为 \(f_{i}=\begin{cases} 1 & i=1 \\ 2 & i=2 \\ f_{i-1}+f_{i-2}+1 & i>2 \end{cases}\) 。
- 同时还需要保证删完后的树是一棵平衡树，故左儿子不能选太多的点。设 \(h_{x}\) 表示以 \(x\) 为根的子树内的最大深度， \(used_{x}\) 表示以 \(x\) 为根的子树内的已经选择过的最大深度， \(lim_{x}\) 表示如果要保留 \(x\) 至少需要的深度。
点击查看代码
int ch[500010][2],fa[500010],f[500010],ans[500010],h[500010],dep[500010],lim[500010],used[500010]; #define lson(rt) (ch[rt][0]) #define rson(rt) (ch[rt][1]) void dfs(int x) { if(x==0) { return; } h[x]=dep[x]=dep[fa[x]]+1; dfs(lson(x)); dfs(rson(x)); h[x]=max(h[x],max(h[lson(x)],h[rson(x)])); } void pushup(int x,int &k) { used[x]=max(used[x],dep[x]); for(int rt=x;rt!=0;rt=fa[rt]) { k-=(ans[rt]==0);//中途往上更新没有选中的点 ans[rt]=1; used[fa[rt]]=max(used[fa[rt]],dep[x]); if(lson(fa[rt])==rt&&rson(fa[rt])!=0) { lim[rson(fa[rt])]=max(lim[rson(fa[rt])],used[fa[rt]]-1);//符合 AVL 树高度的限制 } } } bool check(int x,int k) { int sum=0; for(int rt=x;rt!=0;rt=fa[rt]) { sum+=(ans[rt]==0); if(lson(fa[rt])==rt) { sum+=f[max({used[fa[rt]]-1,dep[x]-1,lim[rson(fa[rt])]})-dep[fa[rt]]];//计算额外需要多少个点 } } return sum<=k; } void solve(int x,int &k) { if(x==0) { return; } if(check(x,k)==true) { pushup(x,k); } if(lson(x)!=0&&rson(x)!=0) { if(h[lson(x)]>=lim[x]) { lim[lson(x)]=max(lim[lson(x)],lim[x]);//左子树已经够了，直接更新左子树 lim[rson(x)]=max(lim[rson(x)],lim[x]-1); } else { lim[lson(x)]=max(lim[lson(x)],lim[x]-1);//左子树不够 lim[rson(x)]=max(lim[rson(x)],lim[x]); } } else { if(lson(x)) { lim[lson(x)]=max(lim[lson(x)],lim[x]); } if(rson(x)) { lim[rson(x)]=max(lim[rson(x)],lim[x]); } } solve(lson(x),k); solve(rson(x),k); } int main() { freopen("avl.in","r",stdin); freopen("avl.out","w",stdout); int n,k,rt=0,i; cin>>n>>k; f[1]=1; for(i=2;i<=30;i++) { f[i]=f[i-1]+f[i-2]+1; } for(i=1;i<=n;i++) { cin>>fa[i]; if(fa[i]==-1) { fa[i]=0; rt=i; } else { ch[fa[i]][fa[i]<i]=i; } } dfs(rt); solve(rt,k); for(i=1;i<=n;i++) { cout<<ans[i]; } fclose(stdin); fclose(stdout); return 0; }
\(T3\) T2211. 暴雨 \(20pts\)
-
部分分
- \(20pts\) ：爆搜。
点击查看代码
const ll p=1000000007; ll h[25010],tmp[25010],lmax[25010],rmax[25010],ans=0; void dfs(ll pos,ll n,ll k) { if(pos==n+1) { if(k==0) { ll sum=0; lmax[0]=rmax[n+1]=0; for(ll i=1;i<=n;i++) { lmax[i]=max(lmax[i-1],tmp[i]); } for(ll i=n;i>=1;i--) { rmax[i]=max(rmax[i+1],tmp[i]); } for(ll i=1;i<=n;i++) { sum^=((min(lmax[i],rmax[i])-tmp[i])&1); } if(sum==0) { ans=(ans+1)%p; } } } else { tmp[pos]=h[pos]; dfs(pos+1,n,k); if(k>=1) { tmp[pos]=0; dfs(pos+1,n,k-1); } } } int main() { freopen("rain.in","r",stdin); freopen("rain.out","w",stdout); ll n,k,i; cin>>n>>k; for(i=1;i<=n;i++) { cin>>h[i]; } dfs(1,n,k); cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T4\) T2197. 置换 \(0pts\)
- 原题： BZOJ4673 置换
- 详见 初三奥赛模拟测试3 T3 置换 。
\(T5\) T2198. 传统题 \(10pts\)
-
部分分
- \(10pts\) ：爆搜。
点击查看代码
ll a[300010],ans=0; void dfs(ll pos,ll n,ll m,ll p) { if(pos==n+1) { ll maxx=0,len=0; for(ll i=1;i<=n;i++) { len=(a[i]==a[i-1])?len+1:1; maxx=max(maxx,len); } ans=(ans+maxx)%p; } else { for(ll i=1;i<=m;i++) { a[pos]=i; dfs(pos+1,n,m,p); } } } int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); ll n,m,p; cin>>n>>m>>p; dfs(1,n,m,p); cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
总结
- 貌似题目出难了，基本上是全程罚坐。
- \(T2\) 第一遍读题时没注意到仍要求是一棵平衡树。
后记
- 因 \(T4\) 之前被出在了 初三奥赛模拟测试3 里，所以 \(huge\) 把 \(T5\) 放了进来，让我们最后再写“我们做过的且码量较大的” \(T4\) 。