多校A层冲刺NOIP2024模拟赛06
\(T1\) A. 小 Z 的手套（gloves） \(100pts/100pts\)
-
容易发现将选出的左右手套各升序排序后，同一个位置上的两只手套的尺码差距一定在答案的候选集合里，画个数轴分讨一下就证完了。
-
部分分
- \(20 \%\) ：因为 \(n=m\) 所以不用管谁选谁不选的问题，故 \(\sum\limits_{i=1}^{n}|l_{i}-r_{i}|\) 。
- 另外 \(50 \%\)
- 以 \(n>m\) 为例。
- 设 \(f_{i,j}\) 表示前 \(i\) 只左手手套中选了 \(j\) 只左手手套的最小的最大值，状态转移方程为 \(f_{i,j}=\min(f_{i-1,j},\max(f_{i-1,j-1},|l_{i}-r_{j}|))\) ，边界为 \(f_{0,0}=0\) 。
- 最终有 \(f_{n,m}\) 即为所求。
点击查看代码
ll l[100010],r[100010],f[2][100010]; int main() { freopen("gloves.in","r",stdin); freopen("gloves.out","w",stdout); ll n,m,ans=0,i,j; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) { scanf("%lld",&l[i]); } for(i=1;i<=m;i++) { scanf("%lld",&r[i]); } sort(l+1,l+1+n); sort(r+1,r+1+m); memset(f,0x3f,sizeof(f)); f[0][0]=0; if(n>m) { for(i=1;i<=n;i++) { for(j=0;j<=min(i,m);j++) { f[i&1][j]=f[(i-1)&1][j]; if(j-1>=0) { f[i&1][j]=min(f[i&1][j],max(f[(i-1)&1][j-1],abs(l[i]-r[j]))); } } } printf("%lld\n",f[n&1][m]); } if(n==m) { for(i=1;i<=n;i++) { ans=max(ans,abs(l[i]-r[i])); } printf("%lld\n",ans); } if(n<m) { for(i=1;i<=m;i++) { for(j=0;j<=min(i,n);j++) { f[i&1][j]=f[(i-1)&1][j]; if(j-1>=0) { f[i&1][j]=min(f[i&1][j],max(f[(i-1)&1][j-1],abs(r[i]-l[j]))); } } } printf("%lld\n",f[m&1][n]); } fclose(stdin); fclose(stdout); return 0; } -
正解
- 仍以 \(n>m\) 为例。
- 观察到答案具有单调性，考虑二分答案。假设当前二分出的答案为 \(mid\) ，在第 \(i\) 只右手手套能够匹配的范围内选尽量小的，画数轴即可证明。
- 至于一只左手手套仅能匹配一只右手手套，使用双指针或
multiset维护即可，后者比前者多一个 \(\log\) 。
点击查看代码
int x[100010],y[100010]; multiset<int>a,b; multiset<int>::iterator it; vector<int>s; bool check(int mid,int n,int m) { bool flag=1; s.clear(); if(n>m) { for(int i=1;i<=m;i++) { it=a.lower_bound(y[i]-mid); if(it!=a.end()&&*it<=y[i]+mid) { s.push_back(*it); a.erase(it); } else { flag=false; break; } } for(int i=0;i<s.size();i++) { a.insert(s[i]); } return flag; } else { for(int i=1;i<=n;i++) { it=b.lower_bound(x[i]-mid); if(it!=b.end()&&*it<=x[i]+mid) { s.push_back(*it); b.erase(it); } else { flag=false; break; } } for(int i=0;i<s.size();i++) { b.insert(s[i]); } return flag; } } int main() { freopen("gloves.in","r",stdin); freopen("gloves.out","w",stdout); int n,m,ans=0,l=0,r=1e9,mid,i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&x[i]); a.insert(x[i]); } for(i=1;i<=m;i++) { scanf("%d",&y[i]); b.insert(y[i]); } sort(x+1,x+1+n); sort(y+1,y+1+m); while(l<=r) { mid=(l+r)/2; if(check(mid,n,m)==true) { r=mid-1; ans=mid; } else { l=mid+1; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. 小 Z 的字符串（string） \(30pts/30pts\)
-
部分分
- \(30 \%\) ：爆搜求出可以得到的所有优雅字符串，然后同 luogu P3531 [POI2012] LIT-Letters | String Reversal 一样求逆序对即可。
点击查看代码
int cnt[3],tmp[3],a[410],ans=0x7f7f7f7f; char s[410]; vector<int>id[3],e; void dfs(int pos,int n,int pre) { if(pos==n+1) { int sum=0; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { sum+=(a[j]<a[i]); } } ans=min(ans,sum); } else { for(int i=0;i<=2;i++) { if(i!=pre&&tmp[i]<=cnt[i]-1) { tmp[i]++; a[id[i][tmp[i]-1]]=pos; dfs(pos+1,n,i); a[id[i][tmp[i]-1]]=-1; tmp[i]--; } } } } int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); int n,flag=1,i; cin>>(s+1); n=strlen(s+1); for(i=1;i<=n;i++) { cnt[s[i]-'0']++; id[s[i]-'0'].push_back(i); flag&=(s[i]!=s[i-1]); } if(flag==1) { cout<<0<<endl; } else { if(cnt[0]>n/2+1||cnt[1]>n/2+1||cnt[2]>n/2+1) { cout<<-1<<endl; } else { dfs(1,n,3); cout<<ans<<endl; } } fclose(stdin); fclose(stdout); return 0; }
-
正解
- 设 \(f_{i,j,k,h,0/1/2}\) 表示最终前 \(i\) 个位置上有 \(j\) 个 \(0\) 和 \(k\) 个 \(1\) 和 \(h\) 个 \(2\) 且第 \(i\) 位为 \(0/1/2\) 的最少移动次数。
- 类似 luogu P3531 [POI2012] LIT-Letters ，我们发现相同的数字间交换一定不优，即相同数字之间的相对位置不变。
- 压缩 \(j+k+h=i\) 加滚动数组后时空复杂度为 \(O(n^{3})\) 。
- 最终有 \(\frac{1}{2}\min\limits_{i=0}^{2}\{ f_{n,cnt_{0},cnt_{1},cnt_{2},i} \}\) 即为所求。
-
带 \(\frac{1}{2}\) 的系数是因为交换两个相邻位置的过程这两个数中一个向前移动，一个向后移动，用移动次数 \(\times \frac{1}{2}\) 才能得到操作次数。
-
挂一下官方题解的理解方式。
-
点击查看代码
int cnt[3],f[2][210][210][3]; char s[410]; vector<int>pos[3]; int main() { freopen("string.in","r",stdin); freopen("string.out","w",stdout); int n,ans=0x7f7f7f7f,i,j,k; cin>>(s+1); n=strlen(s+1); for(i=1;i<=n;i++) { cnt[s[i]-'0']++; pos[s[i]-'0'].push_back(i); } if(cnt[0]>(n+1)/2||cnt[1]>(n+1)/2||cnt[2]>(n+1)/2) { cout<<-1<<endl; } else { memset(f,0x3f,sizeof(f)); for(i=0;i<=2;i++) { f[0][0][0][i]=0; } for(i=1;i<=n;i++) { for(j=0;j<=min(i,cnt[0]);j++) { for(k=0;k<=min(i,cnt[1]);k++) { if(j-1>=0) { f[i&1][j][k][0]=min(f[(i-1)&1][j-1][k][1],f[(i-1)&1][j-1][k][2])+abs(pos[0][j-1]-i); } if(k-1>=0) { f[i&1][j][k][1]=min(f[(i-1)&1][j][k-1][0],f[(i-1)&1][j][k-1][2])+abs(pos[1][k-1]-i); } if(i-j-k<=min(i,cnt[2])&&i-j-k-1>=0) { f[i&1][j][k][2]=min(f[(i-1)&1][j][k][0],f[(i-1)&1][j][k][1])+abs(pos[2][i-j-k-1]-i); } } } } for(i=0;i<=2;i++) { ans=min(ans,f[n&1][cnt[0]][cnt[1]][i]); } cout<<ans/2<<endl; } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 一个真实的故事（truth） \(50pts/50pts\)
-
原题： luogu P7230 [COCI2015-2016#3] NEKAMELEONI | SP25818 NEKAMELEONI - NEKAMELEONI
-
部分分
-
\(20 \%\) ：枚举左右端点 \(O(n^{2})\) 处理询问。
点击查看代码
```cpp int a[50010],cnt[50]; int main() { // freopen("in.in","r",stdin); // freopen("truth.out","w",stdout); int n,k,m,pd,ans,sum,i,j; scanf("%d%d%d",&n,&k,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(j=1;j<=m;j++) { scanf("%d",&pd); if(pd==1) { scanf("%d",&i); scanf("%d",&a[i]); } else { ans=0x7f7f7f7f; sum=0; for(int l=1;l<=n;l++) { memset(cnt,0,sizeof(cnt)); sum=0; for(int r=l;r<=n;r++) { cnt[a[r]]++; sum+=(cnt[a[r]]==1); if(sum==k) { ans=min(ans,r-l+1); break; } } } if(ans==0x7f7f7f7f) { ans=-1; } printf("%d\n",ans); } } fclose(stdin); fclose(stdout); return 0; } ``` -
\(50 \%\) ：双指针 \(O(n)\) 处理单组询问。
点击查看代码
int a[50010],cnt[50]; int main() { freopen("truth.in","r",stdin); freopen("truth.out","w",stdout); int n,k,m,pd,ans,sum,pos,l,r,i,j; scanf("%d%d%d",&n,&k,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=m;i++) { scanf("%d",&pd); if(pd==1) { scanf("%d",&pos); scanf("%d",&a[pos]); } else { sum=0; ans=0x7f7f7f7f; memset(cnt,0,sizeof(cnt)); for(l=r=1;r<=n;r++) { cnt[a[r]]++; sum+=(cnt[a[r]]==1); while(l<=r&&cnt[a[l]]>1) { cnt[a[l]]--; sum-=(cnt[a[l]]==0); l++; } if(sum==k) { ans=min(ans,r-l+1); } } if(ans==0x7f7f7f7f) { ans=-1; } printf("%d\n",ans); } } fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 观察到 \(c \le 50\) ，同 暑假集训CSP提高模拟22 T3 P266. 军队 ，考虑线段树维护前后缀元素最早/晚出现位置，然后
pushup合并两个区间的信息，求解答案时双指针维护即可。 - 时间复杂度为 \(O((n+m)k \log n \log k)\) ，写个常数小的写法。
点击查看代码
int a[100010],cnt[60]; pair<int,int>tmp[110]; struct node { struct SegmentTree { int ans,lpos[60],rpos[60]; }tree[400010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt,int k) { int sum=0,num=0; tree[rt].ans=0x3f3f3f3f; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=k;i++) { if(tree[lson(rt)].rpos[i]!=0x3f3f3f3f) { num++; tmp[num]=make_pair(tree[lson(rt)].rpos[i],i); } if(tree[rson(rt)].lpos[i]!=0x3f3f3f3f) { num++; tmp[num]=make_pair(tree[rson(rt)].lpos[i],i); } } sort(tmp+1,tmp+1+num); for(int l=1,r=1;r<=num;r++) { cnt[tmp[r].second]++; sum+=(cnt[tmp[r].second]==1); while(l<=r&&cnt[tmp[l].second]>1) { cnt[tmp[l].second]--; sum-=(cnt[tmp[l].second]==0); l++; } if(sum==k) { tree[rt].ans=min(tree[rt].ans,tmp[r].first-tmp[l].first+1); } } tree[rt].ans=min(tree[rt].ans,min(tree[lson(rt)].ans,tree[rson(rt)].ans)); for(int i=1;i<=k;i++) { tree[rt].lpos[i]=min(tree[lson(rt)].lpos[i],tree[rson(rt)].lpos[i]); if(tree[rson(rt)].rpos[i]==0x3f3f3f3f) { tree[rt].rpos[i]=tree[lson(rt)].rpos[i]; } else { tree[rt].rpos[i]=tree[rson(rt)].rpos[i]; } } } void build(int rt,int l,int r,int k) { if(l==r) { for(int i=1;i<=k;i++) { tree[rt].lpos[i]=tree[rt].rpos[i]=0x3f3f3f3f; } tree[rt].lpos[a[l]]=tree[rt].rpos[a[l]]=l; tree[rt].ans=(k==1)?1:0x3f3f3f3f; return; } int mid=(l+r)/2; build(lson(rt),l,mid,k); build(rson(rt),mid+1,r,k); pushup(rt,k); } void update(int rt,int l,int r,int pos,int val,int k) { if(l==r) { tree[rt].lpos[a[l]]=tree[rt].rpos[a[l]]=0x3f3f3f3f; a[l]=val; tree[rt].lpos[a[l]]=tree[rt].rpos[a[l]]=l; tree[rt].ans=(k==1)?1:0x3f3f3f3f; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos,val,k); } else { update(rson(rt),mid+1,r,pos,val,k); } pushup(rt,k); } }T; int main() { freopen("truth.in","r",stdin); freopen("truth.out","w",stdout); int n,k,m,pd,pos,val,i; scanf("%d%d%d",&n,&k,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } T.build(1,1,n,k); for(i=1;i<=m;i++) { scanf("%d",&pd); if(pd==1) { scanf("%d%d",&pos,&val); T.update(1,1,n,pos,val,k); } else { printf("%d\n",((T.tree[1].ans==0x3f3f3f3f)?-1:T.tree[1].ans)); } } fclose(stdin); fclose(stdout); return 0; } - 观察到 \(c \le 50\) ，同 暑假集训CSP提高模拟22 T3 P266. 军队 ，考虑线段树维护前后缀元素最早/晚出现位置，然后
\(T4\) D. 异或区间（xor） \(20pts/20pts\)
-
部分分
- \(20pts\) ：模拟。
点击查看代码
int a[100010]; int main() { freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); int n,sum,maxx,i,j; ll ans=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { sum=maxx=0; for(j=i;j<=n;j++) { sum^=a[j]; maxx=max(maxx,a[j]); ans+=(sum<=maxx); } } printf("%lld\n",ans); fclose(stdin); fclose(stdout); return 0; }
总结
- 下发题面后觉得 \(T3\) 线段树维护合并两个区间最可做，但碍于码量较大就先把其他题看了一遍。 \(T1\) 想了近 \(40 \min\) 才想出 \(70pts\) ，而且大部分时间都在想几个比较显然的结论； \(T4\) 误认为是 luogu P10853 【MX-X2-T2】「Cfz Round 4」Xor Counting ，一直在想怎么按位开桶做。中间写暴力部分分的暂且不讲，在最后 \(40 \min\) 才想出 \(T1\) 正解并在仅剩 \(20 \min\) 时成功口胡出 \(T4\) 使用主席树维护二维覆盖的做法，临近结束时码完了但没意识到会有重复统计的问题。