暑假集训CSP提高模拟20
组题人： @KafuuChinocpp
\(T1\) 191. Kanon \(0pts\)
\(T2\) P154. Summer Pockets \(0pts\)
\(T3\) 199. 空之境界 \(60pts\)
- 原题： QOJ 1833. Deleting
- 部分分
- \(60pts\)
-
区间 \(DP\) 。设 \(f_{l,r}\) 表示破坏 \([l,r]\) 单次需要输出的最小魔力值，状态转移方程为 \(f_{l,r}=\min\{\max(f_{l+1,r-1},cost_{l,r}), \max\limits_{k=l+1}^{r-1}(f_{l,k},f_{k+1,r}) \}\) 。时间复杂度为 \(O(n^{3})\) ，因只有偶区间才有用所以带 \(\frac{1}{4}\) 的常数。
-
状态转移方程本质上是个让最大值最小的过程，考虑二分答案，仍用区间 \(DP\) 的方式通过 \(0/1\) 进行转移，拿
bitset压一下，时间复杂度为 \(\frac{n^{3} \log n}{w}\) ，带 \(\frac{1}{4}\) 左右的常数。点击查看代码
int cost[4010][4010],f[4010][4010]; int main() { int n,i,j,k,l,r,len; scanf("%d",&n); for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j+=2) { scanf("%d",&cost[i][j]); } } for(len=2;len<=n;len+=2) { for(l=1,r=l+len-1;r<=n;l++,r++) { f[l][r]=max(f[l+1][r-1],cost[l][r]); for(k=l+1;k<=r-1;k+=2) { f[l][r]=min(f[l][r],max(f[l][k],f[k+1][r])); } } } printf("%d\n",f[1][n]); return 0; }
-
- \(60pts\)
- 正解
\(T4\) 128. 穗 \(80pts\)
-
部分分
- \(20 \%\) ：暴力统计。
- 另外 \(20 \%\) ：普通莫队或 \(CDQ\) 分治或扫描线套树状数组或主席树维护，同 luogu P1972 [SDOI2009] HH的项链 | AT_abc174_f [ABC174F] Range Set Query | SP3267 DQUERY - D-query 。
- 另外 \(40 \%\) ：带修莫队或分块或 \(CDQ\) 分治或带修主席树维护，同 luogu P1903 [国家集训队] 数颜色 / 维护队列 | SP30906 ADAUNIQ - Ada and Unique Vegetable | UVA12345 Dynamic len(set(a[L:R])) | BZOJ2453 维护队列 。
点击查看代码
struct node { int pd,l,r,x; }d[200010]; struct ask { int l,r,tim,id; }q[200010]; struct change { int pos,col; }c[200010]; int a[200010],b[200010],cnt[200010],pos[200010],L[200010],R[200010],ans[200010],q_cnt=0,c_cnt=0,klen,ksum; bool q_cmp(ask a,ask b) { return (pos[a.l]==pos[b.l])?((pos[a.r]==pos[b.r])?(a.tim<b.tim):(a.r<b.r)):(a.l<b.l); } void add(int x,int &sum) { cnt[x]++; sum+=(cnt[x]==1); } void del(int x,int &sum) { cnt[x]--; sum-=(cnt[x]==0); } void init(int n) { klen=pow(n,2.0/3); 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; } } } int main() { int n,m,flag=1,l=1,r=0,tim=0,sum=0,i,j; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; b[0]++; b[i]=a[i]; } for(i=1;i<=m;i++) { cin>>d[i].pd>>d[i].l>>d[i].r; if(d[i].pd==1) { cin>>d[i].x; b[0]++; b[b[0]]=d[i].x; flag&=(d[i].l==d[i].r); } } sort(b+1,b+1+b[0]); b[0]=unique(b+1,b+1+b[0])-b; for(i=1;i<=n;i++) { a[i]=lower_bound(b+1,b+1+b[0],a[i])-b; } for(i=1;i<=m;i++) { if(d[i].pd==1) { d[i].x=lower_bound(b+1,b+1+b[0],d[i].x)-b; c_cnt++; c[c_cnt].pos=d[i].l; c[c_cnt].col=d[i].x; } else { q_cnt++; q[q_cnt].l=d[i].l; q[q_cnt].r=d[i].r; q[q_cnt].id=q_cnt; q[q_cnt].tim=c_cnt; } } if(flag==0) { for(i=1;i<=m;i++) { if(d[i].pd==1) { for(j=d[i].l;j<=d[i].r;j++) { a[j]=d[i].x; } } else { sum=0; for(j=d[i].l;j<=d[i].r;j++) { cnt[a[j]]++; sum+=(cnt[a[j]]==1); } for(j=d[i].l;j<=d[i].r;j++) { cnt[a[j]]--; } cout<<sum<<endl; } } } else { init(n); sort(q+1,q+1+q_cnt,q_cmp); for(i=1;i<=m;i++) { while(l>q[i].l) { l--; add(a[l],sum); } while(r<q[i].r) { r++; add(a[r],sum); } while(l<q[i].l) { del(a[l],sum); l++; } while(r>q[i].r) { del(a[r],sum); r--; } while(tim<q[i].tim) { tim++; if(l<=c[tim].pos&&c[tim].pos<=r) { del(a[c[tim].pos],sum); add(c[tim].col,sum); } swap(a[c[tim].pos],c[tim].col); } while(tim>q[i].tim) { if(l<=c[tim].pos&&c[tim].pos<=r) { del(a[c[tim].pos],sum); add(c[tim].col,sum); } swap(a[c[tim].pos],c[tim].col); tim--; } ans[q[i].id]=sum; } for(i=1;i<=q_cnt;i++) { cout<<ans[i]<<endl; } } return 0; }
总结
- \(T1,T2\) 赛时没读懂什么意思，手摸样例也失败了，赛后发现题读假了。
- \(T3\) 貌似是自己第一次独立做稍微困难点的区间 \(DP\) ，感觉对区间 \(DP\) 的转移有了更深刻的认识；想出二分后感觉为一个 \(0.34\) 的常数去写二分加
bitset优化还照样过不去就没写，然后就不会去掉 \(\log\) 了；尝试想 \(Kruskal\) 重构树发现不会建图。
后记
- 组题人以后组题的时候能不能别整些题意不清晰的题啊。
- \(T2\) 没解释 放完整行或整列 是指栅栏必须一整行或整列得放，而不是必须全放栅栏。
- \(T3\) 没说单次输出的魔力值是固定的，在手摸最小化总魔力值、最小化最大魔力值、最大化最小魔力值后发现最小化最大魔力值是对的。
- \(T4\) 一开始没有 \(m\) 的数据范围。