暑假集训CSP提高模拟16
组题人： @Muel_imj
\(T1\) P216. 九次九日九重色 \(100pts\)
- 部分分
- \(30pts\) ：设 \(f_{i,j}\) 表示当前处理到 \(P\) 的第 \(i\) 位，\(Q\) 的第 \(j\) 位时最大的 \(k\) ，状态转移方程为 \(f_{i,j}=\begin{cases} \max(f_{i,j-1},f_{i-1,j}) & p_{i} \nmid q_{j} \\ \max(f_{i,j-1},f_{i-1,j},f_{i-1,j-1}+1) & p_{i}|q_{j} \end{cases}\) 。最终，有 \(f_{n,n}\) 即为所求。
- 正解
-
尝试转化到最长公共子序列上去。
-
发现能对答案产生贡献的只有 \(p_{i}|q_{j}\) 的关键点，对关键点的转移只有 \(f_{i-1,j-1}\) 有用。
-
记录关键点的位置，树状数组维护前缀 \(\max\) 即可，做法同 luogu P4303 [AHOI2006] 基因匹配 。
点击查看代码
int p[200010],q[200010],f[200010]; vector<int>pos[200010]; struct BIT { int c[200010]; int lowbit(int x) { return(x&(-x)); } void add(int n,int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) { c[i]=max(c[i],val); } } int getsum(int x) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) { ans=max(ans,c[i]); } return ans; } }T; int main() { int n,ans=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>p[i]; for(j=1;j*p[i]<=n;j++) { pos[j*p[i]].push_back(i); } } for(i=1;i<=n;i++) { cin>>q[i]; } for(i=1;i<=n;i++) { if(pos[q[i]].size()>=1) { for(j=pos[q[i]].size()-1;j>=0;j--)//防止有后效性 { f[pos[q[i]][j]]=T.getsum(pos[q[i]][j]-1)+1;//因为转移过程是单调不降的，所以不用取 max T.add(n,pos[q[i]][j],f[pos[q[i]][j]]); } } } for(i=1;i<=n;i++) { ans=max(ans,f[i]); } cout<<ans<<endl; return 0; } -
官方题解写的也很抽象，挂一下吧。
-
\(T2\) P217. 天色天歌天籁音 \(80pts\)
-
部分分
-
\(10pts\) ：输出 \(-1\) 。
-
-
正解
-
懒得复制一遍了，直接粘自己当时写的 题解链接 了。
点击查看代码
int a[200010],b[200010],pos[200010],L[200010],R[200010],ans[200010],num[200010],cnt[200010],klen,ksum; struct ask { int l,r,id; }q[200010]; bool q_cmp(ask a,ask b) { return (pos[a.l]==pos[b.l])?((pos[a.l]%2==1)?(a.r<b.r):(a.r>b.r)):(a.l<b.l); } void init(int n,int m) { klen=n/sqrt(m)+1; ksum=n/klen; for(int i=1;i<=ksum;i++) { L[i]=R[i-1]+1; R[i]=R[i-1]+klen; } if(R[ksum]<n) { ksum++; L[ksum]=R[ksum-1]+1; R[ksum]=n; } for(int i=1;i<=ksum;i++) { for(int j=L[i];j<=R[i];j++) { pos[j]=i; } } } void add(int x,int &sum) { num[cnt[a[x]]]--; cnt[a[x]]++; num[cnt[a[x]]]++; sum=max(sum,cnt[a[x]]); } void del(int x,int &sum) { num[cnt[a[x]]]--; sum-=(sum==cnt[a[x]]&&num[cnt[a[x]]]==0); cnt[a[x]]--; num[cnt[a[x]]]++; } int main() { int n,m,l=1,r=0,sum=0,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+1+n); b[0]=unique(b+1,b+1+n)-(b+1); for(i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+b[0],a[i])-b; } init(n,m); for(i=1;i<=m;i++) { cin>>q[i].l>>q[i].r; q[i].id=i; } sort(q+1,q+1+m,q_cmp); for(i=1;i<=m;i++) { while(l>q[i].l) { l--; add(l,sum); } while(r<q[i].r) { r++; add(r,sum); } while(l<q[i].l) { del(l,sum); l++; } while(r>q[i].r) { del(r,sum); r--; } ans[q[i].id]=-sum; } for(i=1;i<=m;i++) { cout<<ans[i]<<endl; } return 0; }
-
\(T3\) P218. 春色春恋春熙风 \(20pts\)
- 原题： CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
- 字符重排后可以形成回文串当且仅当至多有一个字符的出现次数为奇数。
- 部分分
- \(20pts\) ：\(O(n^{2}|\sum|)\) 预处理出任意两点间是否存在「春」，转成 \(DFS\) 序后查询时等价于查询一个矩阵的最大值，暴力枚举即可。
\(T4\) P219. 雪色雪花雪余痕 \(10pts\)
- 部分分
- \(10pts\) ：暴搜。
- 正解
- 移项有 \(a_{i}-a_{i-1} \le a_{i+1}-a_{i}\) 。
- 得到差分序列 \(\begin{cases} b_{1}=a_{1} \\ b_{i}=a_{i}-a_{i-1}(i \in [2,n-1]) \end{cases}\) ，此时通过统计差分序列 \(\{\}\) 的个数一定程度上可以反映 \(a\) 的个数。
- 题意转化为求 \(\sum\limits_{i=1}^{n-1}b_{i}(n-i+1)=m\) 且 \(\forall i \in [2,n-2],b_{i} \le b_{i+1}\) 的个数。
总结
- 赛时历程：莫名觉得 \(T1\) 不可做，所以先开 \(T2\) 。\(20 \min\) 码完怕拿首切没敢立刻交，大样例过了就没管。然后写 \(T3,T4\) 的部分分。给 \(T1\) 留了 \(1h+40 \min\) 的时间，结果想 \(40pts\) 的部分分就想了 \(30 \min\) ，然后在犹豫能不能和最长公共子序列一个做法，改完后发现过样例了就交上去了。
- \(T2\) \(n,m\) 写反了，挂了 \(20pts\) 。
后记
-
\(T2\) 改后的题面还是很抽象。
