暑假集训CSP提高模拟13
暑假集训CSP提高模拟13
组题人: @joke3579
\(T1\) P185. 小孩召开法 1 \(43pts\)
-
部分分
- 未知 \(pts\) :乱搞。
-
正解
- 状压加记忆化搜索。
- 记录所选字符串的状态及上一个选择的字符串。当存在对方必败时自己必胜。
点击查看代码
int f[1<<18][18]; string s[20]; bool dfs(int x,int last,int n) { if(f[x][last]==-1) { f[x][last]=0; for(int i=0;i<=n-1;i++) { if(((x>>i)&1)==0) { if(last==0||s[last][s[last].size()-1]==s[i+1][0]) { if(dfs(x|(1<<i),i+1,n)==0) { f[x][last]=1; break; } } } } } return f[x][last]; } int main() { int n,i; cin>>n; for(i=1;i<=n;i++) { cin>>s[i]; } memset(f,-1,sizeof(f)); if(dfs(0,0,n)==1) { cout<<"First"<<endl; } else { cout<<"Second"<<endl; } return 0; }
\(T2\) P188. 小孩召开法 2 \(20pts\)
-
部分分
- \(20pts\) :乱搞。
-
正解
- 由数据范围,猜测询问次数介于 \(O(n) \sim O(n \log n)\) 之间。
- \(n-1\) 次询问处理出每个点的深度,然后从小到大枚举深度进行处理。
- 接下来对 \(x,y\) 的询问,由 \(dis_{x,y}=dep_{x}+dep_{y}-2dep_{\operatorname{LCA}(x,y)}\) ,我们就可以得到 \(\operatorname{LCA}(x,y)\) 的深度。
- 设当前已经建出了深度为 \(0 \sim d-1\) 层的二叉树,未知点为 \(x\) ,已知点为 \(y\) 。询问得到 \(\operatorname{LCA}(x,y)\) 的深度后,我们就可以知道 \(\operatorname{LCA}(x,y)\) 是哪个节点。由于是二叉树, \(x,y\) 一定位于 \(\operatorname{LCA}(x,y)\) 的两棵子树内,那么 \(x\) 的父亲节点一定位于 \(\operatorname{LCA}(x,y)\) 除 \(y\) 所在子树内的另一棵子树。
- 令 \(y\) 初始为根节点, \(z\) 为 \(y\) 所在的重链的末端点,此时 \(\operatorname{LCA}(x,z)\) 一定在 \(y\) 所在的重链上,从 \(y\) 开始往下跳重儿子直至 \(\operatorname{LCA}(x,z)\) ,然后走到轻子树,接着令 \(y\) 是这棵轻子树的根节点,重复上述过程直至 \(dep_{y}=dep_{x}-1\) 。
- 连上边后再往上跳更新轻重儿子。
- 最后的询问次数为 \(O(n \log n)\) ,因为常数很小所以可以通过。
点击查看代码
int fa[3010],dep[3010],son[3010],siz[3010],bot[3010]; vector<int>pos[3010],e[3010]; void dfs(int x) { siz[x]=1; son[x]=0; bot[x]=x; for(int i=0;i<e[x].size();i++) { dfs(e[x][i]); siz[x]+=siz[e[x][i]]; son[x]=(siz[e[x][i]]>siz[son[x]])?e[x][i]:son[x]; bot[x]=bot[son[x]]; } } void solve(int x) { int y=1,d; while(dep[y]!=dep[x]-1) { cout<<"? "<<x<<" "<<bot[y]<<endl; cin>>d; d=(dep[x]+dep[bot[y]]-d)/2; while(dep[y]<d) { y=son[y];//跳重儿子 } if(dep[y]!=dep[x]-1) { y=e[y][0]^e[y][1]^son[y];//取轻儿子 //因为一定有轻儿子,所以不用担心会 RE } } fa[x]=y; e[y].push_back(x); } int main() { int n,i,j; cin>>n; for(i=2;i<=n;i++) { cout<<"? "<<1<<" "<<i<<endl; cin>>dep[i]; pos[dep[i]].push_back(i); } for(i=1;i<=n;i++) { dfs(1); for(j=0;j<pos[i].size();j++) { solve(pos[i][j]); } } cout<<"! "; for(i=2;i<=n;i++) { cout<<fa[i]<<" "; } cout<<endl; return 0; }
\(T3\) T176. 小孩召开法 3 \(30pts\)
-
部分分
- \(30pts\) :每组询问跑一遍 \(01\) 背包。
-
正解
- 将询问离线下来,然后进行分治。
- 考虑猫树分治,只单独处理跨过中点的询问,其他询问下放至左右递归中。特判叶子节点的处理。
- 因过程和猫树很像,所以被称作猫树分治。
- 对于跨过中点的询问,暴力进行背包合并即可。
点击查看代码
struct node { ll l,t,id; }; ll h[40010],w[40010],ans[200010],f[40010][210]; vector<node>q[40010]; void solve(ll l,ll r) { if(l==r) { for(ll i=0;i<q[r].size();i++) { if(q[r][i].l==l) { ans[q[r][i].id]=(q[r][i].t>=h[l])*w[l]; } } return; } ll mid=(l+r)/2; memset(f[mid],0,sizeof(f[mid]));//注意清空 f[mid][h[mid]]=w[mid]; for(ll i=mid-1;i>=l;i--) { for(ll j=1;j<=200;j++) { f[i][j]=f[i+1][j]; if(j-h[i]>=0) { f[i][j]=max(f[i][j],f[i+1][j-h[i]]+w[i]); } } } memset(f[mid+1],0,sizeof(f[mid+1]));//注意清空 f[mid+1][h[mid+1]]=w[mid+1]; for(ll i=mid+2;i<=r;i++) { for(ll j=1;j<=200;j++) { f[i][j]=f[i-1][j]; if(j-h[i]>=0) { f[i][j]=max(f[i][j],f[i-1][j-h[i]]+w[i]); } } } for(ll i=l;i<=r;i++) { for(ll j=1;j<=200;j++) { f[i][j]=max(f[i][j],f[i][j-1]); } } for(ll i=mid+1;i<=r;i++) { for(ll j=0;j<q[i].size();j++) { if(l<=q[i][j].l&&q[i][j].l<=mid) { for(ll k=0;k<=q[i][j].t;k++) { ans[q[i][j].id]=max(ans[q[i][j].id],f[i][k]+f[q[i][j].l][q[i][j].t-k]); } } } } solve(l,mid); solve(mid+1,r); } int main() { ll n,m,l,r,t,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>h[i]; } for(i=1;i<=n;i++) { cin>>w[i]; } for(i=1;i<=m;i++) { cin>>l>>r>>t; q[r].push_back((node){l,t,i}); } solve(1,n); for(i=1;i<=m;i++) { cout<<ans[i]<<endl; } return 0; }
\(T4\) T177. 小孩召开法 4 \(5pts\)
- 原题: [AGC056B] Range Argmax
- 部分分
- \(5pts\) :输出样例 \(1\) 。
- 正解
- 过于抽象,直接贺官方题解了。
同一个 \(x\) 可能对应多个 \(p\),因此这样计数比较困难。
考虑反过来计数。
对于给定的 \(x\),我们将按照以下的方式构造 \(p\):
- 令 \(p = (-1,-1,\cdots,-1)\) 。
- 我们从 \(n\) 开始依次递减地考虑每个值 \(v\)。对于每个值,我们找到 \(v\) 能放的最左侧的位置,放进去。
计数可以通过这种方式生成的 \(p\) 。
设当前最值为 \(v\)。我们首先确定下标 \(m\),使得 \(p_m = v\)。对于所有包含 \(m\) 的区间 \(i\),有 \(x_i = m\)。删除这些包含 \(m\) 的区间后,我们可以分别考虑位于 \(m\) 左右两侧的区间。由于 \(m\) 为最左侧的可以放 \(v\) 的位置,右侧的数均小于左侧的数,这部分是和原问题等价但规模更小的子问题。
现在考虑左侧。我们令 \(k\) 为 \(m\) 左侧最大元素对应的下标。有:必定存在一个左侧区间同时包含 \(k\) 和 \(m\)。
考虑反证。如果左侧没有区间同时包含 \(k\) 和 \(m\),那我们可以令 \(p_k = v\),这必定是更优且满足要求的。这与假设矛盾,因此必定存在同时包含 \(k\) 和 \(m\) 的左侧区间。
因此,左侧区间所填的数的最大值必定大于等于 \(v\)。考虑区间 dp。我们设 \(f(l,r,m)\) 为 \([l,r]\) 区间满足最大值的下标大于等于 \(m\) 的方案数。可以通过枚举中点以及预处理区间最大值的方式转移。转移时加入后缀和即可快速得到最终答案。
时间复杂度 \(O(n^3)\)。
总结
- \(T4\) 赛时没读懂题。
后记
-
比赛头图。
-
题目背景均来自或改编自 LibreOJ 6731. 「2019 山东一轮集训 Day3」小孩召开法 。