暑假集训CSP提高模拟4
\(T1\) P134. White and Black \(0pts\)
-
翻转方式：从根节点进行 \(DFS\) ，若遇到黑点就进行翻转。最后一定能使全树均为白点，即不存在无解的情况。进而有每个点仅会被主动翻转一次，且翻转顺序与最终结果无关。
-
观察到 \(\sum\limits_{i=1}^{q}m_{i} \le 2 \times 10^{5}\) ，考虑枚举黑点。
-
若点 \(x\) 与父亲节点颜色不同，则会贡献一次翻转；否则则桶记录下每个节点子节点中有多少个黑点，最后减去即可。
点击查看代码
struct node { int nxt,to; }e[400010]; int head[400010],fa[400010],son[400010],dep[400010],vis[400010],sum[400010],s[400010],cnt=0; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x,int father) { fa[x]=father; dep[x]=dep[father]+1; for(int i=head[x];i!=0;i=e[i].nxt) { son[x]++; dfs(e[i].to,x); } } bool cmp(int a,int b) { return dep[a]>dep[b]; } int main() { int n,q,u,v,m,ans,i,j; cin>>n>>q; for(i=2;i<=n;i++) { cin>>u; v=i; add(u,v); } dfs(1,0); for(i=1;i<=q;i++) { cin>>m; ans=0; for(j=1;j<=m;j++) { cin>>s[j]; vis[s[j]]=1; } sort(s+1,s+1+m,cmp);//从深到浅处理，好像不排序也行 for(j=1;j<=m;j++) { if(vis[fa[s[j]]]==1) { sum[fa[s[j]]]++;//统计黑点个数 } else { ans++; } } for(j=1;j<=m;j++) { ans+=son[s[j]]-sum[s[j]];//统计因翻转变成黑点的白点 vis[s[j]]=sum[s[j]]=0; } cout<<ans<<endl; } return 0; }
\(T2\) P137. White and White \(0pts\)
-
令 \(sum_{i}=\sum\limits_{j=1}^{i}a_{j}\) ，设 \(f_{i,j}\) 表示把前 \(i\) 个数分成 \(j\) 段时的最小价值总和，状态转移方程为 \(f_{i,j}=\min\limits_{h=j-1}^{i-1} \{ f_{h,j-1}+(sum_{i}-sum_{h}) \bmod p \}\) ，边界为 \(f_{0,0}=0\) 。
- 直接暴力转移的话时间复杂度为 \(O(n^{2}k)\) ，更改枚举顺序加滚动数组优化后仅能通过 \(Subtask1\) 。
-
题面隐含着一个 \(f_{i,j} \equiv sum_{i} \pmod{p}\) 。进而有对于 \(f_{i,j}\) 的两个决策 \(x,y(x \ne y)\) 一定有 \(f_{x,j-1}+sum_{i}-sum_{x} \equiv f_{y,j-1}+sum_{i}-sum_{y} \equiv sum_{i} \pmod{p}\) ，进而有 \(f_{x,j-1}+(sum_{i}-sum_{x}) \bmod p \equiv f_{y,j-1}+(sum_{i}-sum_{y}) \bmod p \pmod{p}\)
-
若 \(f_{x,j-1}<f_{y,j-1}\) ，又因为 \(\begin{cases} (sum_{i}-sum_{x}) \bmod p \in [0,p) \\ (sum_{i}-sum_{y}) \bmod p \in [0,p) \end{cases}\) ，有 \(f_{x,j-1}+(sum_{i}-sum_{x}) \bmod p \le f_{y,j-1}+(sum_{i}-sum_{y}) \bmod p\) 。所以取使 \(f_{h,j-1}\) 最小的 \(h\) 进行转移即可。
- 反证法即可证明。
-
最终有 \(f_{n,k}\) 即为所求。
点击查看代码
ll a[500010],sum[500010],f[500010][2]; int main() { ll n,k,p,minn,pos,i,j; scanf("%lld%lld%lld",&n,&k,&p); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } f[0][0]=0; for(j=1;j<=k;j++) { minn=f[j-1][(j-1)&1]; pos=j-1; for(i=j;i<=n;i++) { f[i][j&1]=f[pos][(j-1)&1]+(sum[i]-sum[pos])%p; if(f[i][(j-1)&1]<minn) { minn=f[i][(j-1)&1]; pos=i; } } } printf("%lld\n",f[n][k&1]); return 0; }
\(T3\) P132. Black and Black \(0pts\)
-
因要满足 \(|b_{i}| \le 2 \times 10^{12}\) ，考虑尽量减小 \(|b_{i}|\) 着填。
-
先将 \(1 \sim n\) 填入 \(b\) ，记 \(s=\sum\limits_{i=1}^{n}a_{i}b_{i}\) ， 然后考虑调整。
-
当 \(s>0\) 时， 若 \(\{ a \}\) 存在一个前缀和为正数或存在一个后缀和为负数则一定有解。
- 存在一个前缀和为正数则一定存在一个前缀和等于 \(1\) 。接着将这个前缀减去 \(s\) 就会满足题意。
- 存在一个后缀和为负数则一定存在一个后缀和等于 \(-1\) 。接着将这个后缀加上 \(s\) 就会满足题意。
-
当 \(s=0\) 时，直接输出 \(\{ b \}\) 。
-
当 \(s<0\) 时，同理。
点击查看代码
ll a[200010],b[200010],pre[200010],suf[200010]; int main() { ll n,sum=0,flag=0,pos=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; b[i]=i; sum+=a[i]*b[i]; pre[i]=pre[i-1]+a[i]; } for(i=n;i>=1;i--) { suf[i]=suf[i+1]+a[i]; } if(sum==0) { cout<<"Yes"<<endl; for(i=1;i<=n;i++) { cout<<b[i]<<" "; } } else { if(sum>0) { for(i=1;i<=n;i++) { flag|=(pre[i]>=1||suf[i]<=-1); } if(flag==0) { cout<<"No"<<endl; } else { for(i=1;i<=n;i++) { if(pre[i]==1) { pos=i; break; } } if(pos==0) { for(i=n;i>=1;i--) { if(suf[i]==-1) { pos=i; break; } } for(i=pos;i<=n;i++) { b[i]+=sum; } } else { for(i=1;i<=pos;i++) { b[i]-=sum; } } cout<<"Yes"<<endl; for(i=1;i<=n;i++) { cout<<b[i]<<" "; } } } else { for(i=1;i<=n;i++) { flag|=(pre[i]<=-1||suf[i]>=1); } if(flag==0) { cout<<"No"<<endl; } else { for(i=1;i<=n;i++) { if(pre[i]==-1) { pos=i; break; } } if(pos==0) { for(i=n;i>=1;i--) { if(suf[i]==1) { pos=i; break; } } for(i=pos;i<=n;i++) { b[i]-=sum; } } else { for(i=1;i<=pos;i++) { b[i]+=sum; } } cout<<"Yes"<<endl; for(i=1;i<=n;i++) { cout<<b[i]<<" "; } } } } return 0; }
\(T4\) P136. Black and White \(0pts\)
总结
- \(T1\) 以为翻转顺序会影响最终答案，所以要用 \(DP\) 。想到正解后又被自己 \(Pass\) 了。
- \(T2\)
- 三个 \(Subtask\) 数据范围有较大差别，以为会像 LibreOJ 6560. 小奇取石子 一样面向数据点分治。
- 空间又开大了，加上没有进行滚动数组优化，挂了 \(10pts\) 。
- \(T3\) 赛时以为是类似 初三奥赛模拟测试1 T3 混乱邪恶 一样的高级构造，遂没写。
后记
- \(T2\) 赛时进行改数据（不捆绑到捆绑）和时限（ \(1.5s\) 到 \(0.5s\) ），卡掉了树状数组和一些常数大点的正解做法。
- \(T3\) 直接下发了可执行文件 \(checker\) ，在 \(Windows\) 下可以正常用，但 \(Linux\) 下少权限，需要 【数据删除】 来获得权限。