前言
写晚了，忙着打 abc 和 scp 了。
scp T1送，T2T3T4 防 AK。
T1 小 Z 的手套
二分答案，双指针进行转移，若差值在 \(mid\) 范围内则转移，\(O(n\log(v))\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,ans,a[N],b[N];
bool check(int x)
{
for(int i=1,j=1;i<=n;i++,j++)
{
while(j<=m&&b[j]<a[i]-x) j++;
if(j>m||b[j]>a[i]+x) return 0;
}
return 1;
}
signed main()
{
freopen("gloves.in","r",stdin),freopen("gloves.out","w",stdout);
read(n,m);
for(int i=1;i<=n;i++) read(a[i]); sort(a+1,a+1+n);
for(int i=1;i<=m;i++) read(b[i]); sort(b+1,b+1+m);
if(n>m) swap(n,m),swap(a,b);
for(int l=0,r=(int)1e9,mid;l<=r;)
{
mid=l+r>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
write(ans);
}
T2 小 Z 的字符串
直接 DP，\(f_{i,j,k,h,s}\) 表示到了第 \(i\) 位，有 \(j\) 个 \(0\)，\(k\) 个 \(1\)，\(h\) 个 \(2\)，以 \(s\) 结尾的答案最小值，有转移：
\[\begin{cases} f_{i,j,k,h,0}=\min(f_{i-1,j-1,k,h,1},f_{i-1,j-1,k,h,2}+|pos_{0,j}-i|)\\ f_{i,j,k,h,1}=\min(f_{i-1,j,k-1,h,0},f_{i-1,j,k-1,h,1}+|pos_{1,k}-i|)\\ f_{i,j,k,h,2}=\min(f_{i-1,j,k,h-1,0},f_{i-1,j,k,h-1,1}+|pos_{2,h}-i|)\\ \end{cases}\]\(pos_{i,j}\) 表示第 \(j\) 个 \(i\) 字符在原串中出现的位置，注意一下边界即可，复杂度不对，发现 \(j+k+h=i\)，所以可以省去一维，可以滚动数组优化空间。
最后答案为 \(\dfrac{\min(f_{n,cnt_0,cnt_1,cnt_2,0},f_{n,cnt_0,cnt_1,cnt_2,1},f_{n,cnt_0,cnt_1,cnt_2,2})}{2}\)，因为挪过去和挪回来算了两次贡献。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=410;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
char s[N]; int n,cnt[3],f[2][N>>1][N>>1][3]; vector<int>pos[3];
signed main()
{
freopen("string.in","r",stdin),freopen("string.out","w",stdout);
scanf("%s",s+1); n=strlen(s+1);
for(int i=1;i<=n;i++) pos[s[i]-'0'].push_back(i),cnt[s[i]-'0']++;
if(cnt[0]>(n+1>>1)||cnt[1]>(n+1>>1)||cnt[2]>(n+1>>1)) return puts("-1"),0;
memset(f,0x3f,sizeof(f)),f[0][0][0][0]=f[0][0][0][1]=f[0][0][0][2]=0;
for(int i=1,x=1,y=0;i<=n;i++,x^=1,y^=1)
for(int j=0;j<=min(i,cnt[0]);j++)
for(int k=0,h;k<=min({i,i-j,cnt[1]});k++) if((h=i-j-k)<=cnt[2])
{
if(j) f[x][j][k][0]=min(f[y][j-1][k][1],f[y][j-1][k][2])+abs(i-pos[0][j-1]);
if(k) f[x][j][k][1]=min(f[y][j][k-1][0],f[y][j][k-1][2])+abs(i-pos[1][k-1]);
if(h) f[x][j][k][2]=min(f[y][j][k][0],f[y][j][k][1])+abs(i-pos[2][h-1]);
}
write(min({f[n&1][cnt[0]][cnt[1]][0],f[n&1][cnt[0]][cnt[1]][1],f[n&1][cnt[0]][cnt[1]][2]})>>1);
}
T3 一个真实的故事
-
部分分 \(50pts\)：\(O(n^2)\) 双指针跑。
-
部分分 \(95pts\)：\(O(nk\log(n))\) 修改，\(O(1)\) 查询，维护 \(pre,nxt\) 的暴力，\(95pts\) 因为加 hack 了。
-
正解：
考虑线段树，主要是怎么 pushup 的问题。
考虑用一个 long long 把都有哪些数二进制压起来，类似于区间子段和一样维护前缀与其端点，后缀与其端点，区间答案，答案考虑使用关于 \(k\) 的前缀和加双指针更新。
就是实现起来比较不好调，直接看代码吧。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define mid (l+r>>1) #define ls (mid<<1) #define rs (mid<<1|1) using namespace std; const int N=5e4+10,M=35,inf=0x3f3f3f3f; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar_unlocked(); for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0; for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);} template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');} template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);} template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);} int n,k,m,mx,a[N],val[N<<1],sum[N<<1],sp[N<<1][M],ss[N<<1][M]; ll pre[N<<1][M],suf[N<<1][M]; void pushup(int p,int l,int r) { val[p]=min(val[ls],val[rs]),sum[p]=sum[ls]; for(int i=1;i<=sum[ls];i++) pre[p][i]=pre[ls][i],sp[p][i]=sp[ls][i]; for(int i=1,j=sum[ls];i<=sum[rs];i++) if((pre[p][j]&pre[rs][i])!=pre[rs][i]) { pre[p][sum[p]=++j]=pre[p][j]|pre[rs][i]; sp[p][j]=sp[rs][i]; } for(int i=1;i<=sum[rs];i++) suf[p][i]=suf[rs][i],ss[p][i]=ss[rs][i]; for(int i=1,j=sum[rs];i<=sum[ls];i++) if((suf[p][j]&suf[ls][i])!=suf[ls][i]) { suf[p][++j]=suf[p][j]|suf[ls][i]; ss[p][j]=ss[ls][i]; } for(int i=sum[ls],j=1;i;i--) { for(;j<=sum[rs]&&(suf[ls][i]|pre[rs][j])!=mx;j++); if(j<=sum[rs]) val[p]=min(val[p],sp[rs][j]-ss[ls][i]+1); } } void build(int p,int l,int r) { if(l==r) { sp[p][1]=ss[p][1]=l,pre[p][1]=suf[p][1]=1ll<<(a[l]-1); return sum[p]=1,val[p]=inf,void(); } build(ls,l,mid),build(rs,mid+1,r),pushup(p,l,r); } void change(int p,int l,int r,int x,int d) { if(l==r) return pre[p][1]=suf[p][1]=1ll<<(d-1),void(); x<=mid?change(ls,l,mid,x,d):change(rs,mid+1,r,x,d),pushup(p,l,r); } signed main() { freopen("truth.in","r",stdin),freopen("truth.out","w",stdout); read(n,k,m),mx=(1<<k)-1; for(int i=1;i<=n;i++) read(a[i]); build(1,1,n); for(int op,x,y;m;m--) { read(op); if(op&1) read(x,y),change(1,1,n,x,y); else write(val[1]>n?-1:val[1]),puts(""); } }
T4 异或区间
本题可拆分成两个题，分别是 P4755 Beautiful Pair 和 CF665E Beautiful Subarrays。
P4755 Beautiful Pair
区间最值可以单调栈维护，那么对于每个 \(i\)，\([l_i,i]\) 中的左端点与 \([i,r_i]\) 中的右端点都以 \(a_i\) 为最大值。
那么考虑确定了一个端点，在另一个区间里找到满足的就可以了，发现复杂度不正确，考虑类似与启发式合并的选择较小的一遍枚举，这样每一个点被枚举到其上一个区间一定 \(\ge 2len\)，所以最多被枚举到 \(\log\) 次，可以套个主席树或扫描线加树状数组做，复杂度 \(O(n\log^2(n))\)。
类似的操作是笛卡尔树，但我不会那玩意，思路是一致的。
CF665E Beautiful Subarrays
建 01trie，求出异或前缀和，那么每次查询的时候，因为要 \(\ge k\)，所以若 \(k\) 当前位为 \(1\)，则必须向相反一边走，否则加上往相反一边走的贡献，继续往相同的一边走。
对于本题
就把上面两个合起来就可以了，第一道题的操作套个可持久化 01trie。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define son(p,c) t[p].son[c]
#define cnt(p) t[p].cnt
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,tot,a[N],vl[N],vr[N],rt[N],sum[N],sta[N]; ll ans;
struct aa {int son[2],cnt;}t[N<<5];
void insert(int &now,int last,int x)
{
now=++tot; int p=now,q=last;
for(int i=30,c;i>=0;i--)
{
son(p,0)=son(q,0),son(p,1)=son(q,1);
cnt(p=son(p,c)=++tot)=cnt(q=son(q,c=(x>>i)&1))+1;
}
}
int ask(int p,int q,int x,int y)
{
int res=0; for(int i=30,c;i>=0;i--)
{
if((y>>i)&1)
{
res+=cnt(son(p,c=(x>>i)&1))-cnt(son(q,c));
p=son(p,!c),q=son(q,!c);
}
else p=son(p,c=(x>>i)&1),q=son(q,c);
if(!p) break;
}
return res+cnt(p)-cnt(q);
}
signed main()
{
freopen("xor.in","r",stdin),freopen("xor.out","w",stdout);
read(n); insert(rt[1],rt[0],0);
for(int i=1,top=0;i<=n;i++)
{
for(read(a[i]);top&&a[sta[top]]<a[i];top--);
vl[i]=top?sta[top]+1:1,sta[++top]=i;
insert(rt[i+1],rt[i],sum[i]=sum[i-1]^a[i]);
}
for(int i=n,top=0;i;i--)
{
for(;top&&a[sta[top]]<=a[i];top--);
vr[i]=top?sta[top]-1:n,sta[++top]=i;
}
for(int i=1;i<=n;i++)
{
if(i-vl[i]<vr[i]-i) for(int j=vl[i];j<=i;j++)
ans+=ask(rt[vr[i]+1],rt[i],sum[j-1],a[i]);
else for(int j=i;j<=vr[i];j++)
ans+=ask(rt[i],rt[vl[i]-1],sum[j],a[i]);
}
write(ans);
}