A-Ancient Distance

由于答案单调不降,所以每次$k$增加的时候考虑是否答案一定要增加. $check()$ 时候每次找到一个未选择的深度最大的点,往上跳$ans$步,然后选择整颗子树,单次$check()$的复杂度为$O(n)$.

所以这个暴力做法的复杂度为$O(n^2)$.

我们如果能加速子树选择,那么就可以快速忽略已经选择的点. 我们可以用$dfs$序表示子树,那么我们用线段树维护$dfs$序中区间深度最大的未选择的点即可. 删除的时候打上标记直接走人… 最后我们要还原线段树,直接把本次修改的位置还原即可.

枚举$i$,求出$k_i$表示每次跳$i$步,至少需要多少个关键点.那么$[k_i,k_{i-1})$ 这个区间内的答案即为$i$. 每次跳跃至少覆盖$i+1$个点,所以单次次数约$\frac{n}{i+1}$. 所以总跳跃次数和是个调和级数,总复杂度为$O(n{\log }^{2}n)$.

int n,dfn[N],in[N],ou[N],id,fa[N][20],dep[N]; struct edge{int y,next; } a[N]; int len,last[N]; void ins(int x,int y) {a[++len]=(edge){y,last[x]}; last[x]=len;} void dfs(int x) { dfn[++id]=x; in[x]=id; for(int k=last[x],y;k;k=a[k].next) { y=a[k].y; for(int i=1;i<20;i++) fa[y][i]=fa[fa[y][i-1]][i-1]; dep[y]=dep[x]+1; dfs(y);v } ou[x]=id; } int jump(int x,int k) { for(int i=18;i>=0;i--) if(k>>i&1) x=fa[x][i]; return x; } int mx[N<<2],imx[N<<2],sta[N],top; void pushup(int x) {mx[x]=max(mx[lc],mx[rc]);} void bt(int x,int l,int r) { if(l==r) {mx[x]=imx[x]=dep[dfn[l]]; return ;} int mid=(l+r)/2; bt(lc,l,mid); bt(rc,mid+1,r); pushup(x); imx[x]=mx[x]; } void upd(int x,int l,int r,int L,int R,int z) { if(L<=l&&r<=R) {mx[x]=z*imx[x]; return ;} int mid=(l+r)/2; if(L<=mid) upd(lc,l,mid,L,R,z); if(mid< R) upd(rc,mid+1,r,L,R,z); pushup(x); } int query(int x,int l,int r) { if(l==r) return dfn[l]; int mid=(l+r)/2; if(mx[lc]==mx[x]) return query(lc,l,mid); return query(rc,mid+1,r); } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) last[i]=0; len=id=0; for(int i=0;i<=18;i++) fa[1][i]=1; for(int i=2;i<=n;i++) qr(fa[i][0]),ins(fa[i][0],i); dfs(1); bt(1,1,n); ll ans=0; for(int i=1,j=n,k;i<=n;i++) { top=k=0; while(1) { int x=jump(query(1,1,n),i); k++; if(x==1) break; upd(1,1,n,in[x],ou[x],0); sta[++top]=x; } ans+=(ll)(j-k)*i; j=k; while(top) upd(1,1,n,in[sta[top]],ou[sta[top]],1),top--; } pr2(ans); } }

B-Basic Gcd Problem

$\gcd (i,n)<n$,最优情况下质因子减小1. 那么容易看出我们要尽可能多的划分,则有 $ans=c^{\sigma (n)},\sigma (n)$表示$n$的质因子个数.

C-Count New String

结论1:我们要求$f(S,i,n)$的不同子串个数. 结论2:我们把$f(S,i,n)$翻转后塞入$Trie$树的话,总结点数至多为$10n$. 证明:第$i$个位置至多有10种方案,而这10种方案唯一对应了后面$(i,n+1)$的状态.

所以我们把所有串塞到广义后缀自动机即可. 总复杂度为$O(100n)$.

int n; char s[N]; struct node{int fa,len,v[10];} tr[N]; int tot=1; int add(int last,int c) { int p=last,x=last=++tot; tr[x].len=tr[p].len+1; for( ;p&&!tr[p].v[c];p=tr[p].fa) tr[p].v[c]=x; if(!p) tr[x].fa=1; else { int q=tr[p].v[c],y; if(tr[p].len+1==tr[q].len) tr[x].fa=q; else { tr[y=++tot]=tr[q]; tr[y].len=tr[p].len+1; tr[q].fa=tr[x].fa=y; for( ;p&&tr[p].v[c]==q;p=tr[p].fa) tr[p].v[c]=y; } } return x; } int pos[N],R[N]; void calc() { ll ans=0; for(int i=2;i<=tot;i++) ans+=tr [i].len-tr[tr[i].fa].len; pr2(ans); } int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) s[i]-='a'; s[n+1]=55; pos[n+1]=1; for(int i=n;i;i--) { R[i]=i+1; while(s[i]>s[R[i]]) R[i]=R[R[i]]; pos[i]=pos[R[i]]; for(int j=R[i]-i; j;j--) pos[i]=add(pos[i],s[i]); } calc(); return 0; }

D-Dividing Strings

给定一个十进制字符串,让你把它划分成若干块无前导零的数,最小化 最大值和最小值 之差.

我们把数字一位一位分开,可以发现$ans\le 9$. 然后,划分要么分成若干块长度相等的部分. 要么长度差为1,且形为$1000..x$,$9999..x$.

讨论一下即可.

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; void qr(int &x) {scanf("%d",&x);} int n,ans,mx,mn; char s[N]; void calc(int x) { static int a[N],b[N]; for(int i=0;i<x;i++) a[i]=-1,b[i]=10; for(int i=1;i<=n;i+=x) { if(!s[i]) return ; int big=0,sma=0; for(int j=0;j<x;j++) { if(!big&&s[i+j]!=a[j]) big=(s[i+j]>a[j])?1:-1; if(!sma&&s[i+j]!=b[j]) sma=(s[i+j]<b[j])?1:-1; } for(int j=0;j<x;j++) { if(big==1) a[j]=s[i+j]; if(sma==1) b[j]=s[i+j]; } } int num=0; for(int i=0;i<x;i++) { num=num*10+a[i]-b[i]; if(num>=ans) return ; } ans=num; } void solve(int x) {//x 表示 999..t 的位数 int mx=0,mn=1000,cnt=0; for(int i=1;i<=n;i++) if(s[i]==1) { if(i+x>n) return ; bool v=1; for(int j=1;j<x;j++) if(s[i+j]) {v=0; break;} if(!v) return ; mx=max(mx,10+s[i+x]); mn=min(mn,10+s[i+x]); i+=x; cnt++; } else { if(i+x-1>n) return; bool v=1; for(int j=0;j<x-1;j++) if(s[i+j]<9) {v=0; break;} if(!v) return; mx=max(mx,(int)s[i+x-1]); mn=min(mn,(int)s[i+x-1]); i+=x-1; cnt++; } if(cnt<2) return ; ans=min(ans,mx-mn); } int main() { freopen("a.in","r",stdin); int T; qr(T); while(T--) { qr(n); scanf("%s",s+1); mx=0; mn=10; for(int i=1;i<=n;i++) s[i]-='0',mx=max(mx,(int)s[i]),mn=min(mn,(int)s[i]); ans=mx-mn; for(int i=2;i*i<=n;i++) if(n%i==0) calc(i),calc(n/i); int k=0; for(int i=1;i<=n;i++) if(s[i]==1) { k=1; while(i+k<=n&&!s[i+k]) k++; break; } //长度不等的话,要么是1000...x,要么是99999...x. if(k)solve(k); if(k>1) solve(k-1); printf("%d\n",ans); } }

E-Eliminate++

$n(2|n-1)$个数,每次操作定义为保留连续3个数的中位数,其他删除,问每个数是否有可能留到最后.($n\le 1e6$)

假设最后剩余$a[i]$,那么我们可以把$<a[i]$的设为0, $>a[i]$的设为1. 然后3个相同可以删除2个,01可以带上一个数然后一起删除. 最后可以跨过$i$(跨过$i$表示$i$为三个数的第二个数), 消除01: 左0右1/左1右0.

性质1: 0和1数量相等一定有解. 我们把01消去,那么一边的0的数量等于一边的1的数量,那么显然再跨过$i$消去即可. 性质2: 假设一开始0,1数量不等,那么就需要删除00,11.所以有解一定可以先消两边,再消跨过$i$的情况.

设$mid=(n+1)/2$.那么$mid$一定有解(性质1). 对于$[1,mid-1]$,$c_0<c_1$(数量). 容易发现$c_0,c_1$的奇偶性相同(和为偶数). 那么我们贪心消除掉尽量多的1,设$one$为当前1的个数,$tot$表示至多能删除$11$ 删除多少次. 那么当出现0,就有$01$,$one--$. 当出现1,$one++$,若$one>=3$,$one-=2,tot++$.

我们只要知道$c_0\ge c_1^{\prime }$($c_1^{\prime }$表示$c_1-tot\times 2$)就有解.因为我们可以通过回撤删除实现$c_0=c_1^{\prime }$.

#include<bits/stdc++.h> #define fi first #define se second #define lc (x<<1) #define rc (x<<1|1) #define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++) #define mk make_pair #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define IT iterator #define vi vector<int> #define TP template<class o> #define SZ(a) ((int)a.size()) #define all(a) a.begin(),a.end() using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N=1e6+10,size=1<<20,mod=998244353,inf=2e9; //char buf[size],*p1=buf,*p2=buf; template<class o> void qr(o &x) { char c=gc; x=0; int f=1; while(!isdigit(c)){if(c=='-')f=-1; c=gc;} while(isdigit(c)) x=x*10+c-'0',c=gc; x*=f; } template<class o> void qw(o x) { if(x/10) qw(x/10); putchar(x%10+'0'); } template<class o> void pr1(o x) { if(x<0)x=-x,putchar('-'); qw(x); putchar(' '); } template<class o> void pr2(o x) { if(x<0)x=-x,putchar('-'); qw(x); putchar('\n'); } int T,n,a[N],p[N],mid; char ans[N]; struct node { int num[3],res[3];//num[i]表示有i个1,经过[l,r]后能匹配多少个0,res[i]表示经过后的剩余1的个数 node(int flag=0) { if(!flag) for(int i=0;i<3;i++) num[i]=i>=2,res[i]=i%2+1; else for(int i=0;i<3;i++) num[i]=0,res[i]=max(i-1,0); } node operator +(node b) const { node c; for(int i=0;i<3;i++) c.num[i]=num[i]+b.num[res[i]], c.res[i]=b.res[res[i]]; return c; } } tr[N<<2]; void bt(int x,int l,int r) { if(l==r) tr[x]=node(); else {int mid=(l+r)/2; bt(lc,l,mid); bt(rc,mid+1,r); tr[x]=tr[lc]+tr[rc]; } } void upd(int x,int l,int r,int pos) { if(l==r) {tr[x]=node(1); return ;} int mid=(l+r)/2; if(pos<=mid) upd(lc,l,mid,pos); else upd(rc,mid+1,r,pos); tr[x]=tr[lc]+tr[rc]; } void ask(int x,int l,int r,int L,int R,int &one,int &tot) { if(L<=l&&r<=R) {tot+=tr[x].num[one]; one=tr[x].res[one]; return ;} int mid=(l+r)/2; if(L<=mid) ask(lc,l,mid,L,R,one,tot); if(mid< R) ask(rc,mid+1,r,L,R,one,tot); } int main() { // freopen("a.in","r",stdin); qr(T); while(T--) { qr(n); ans[n+1]=0; for(int i=1;i<=n;i++) qr(a[i]),p[a[i]]=i; bt(1,1,n); int mid=(n+1)/2; for(int i=1;i<mid;i++) { upd(1,1,n,p[i]); int tot=0,one; if(p[i]>1) ask(1,1,n,1,p[i]-1,one=0,tot); if(p[i]<n) ask(1,1,n,p[i]+1,n,one=0,tot); ans[p[i]]=(i-1>=n-i-2*tot)+'0'; } bt(1,1,n); ans[p[mid]]='1'; for(int i=n;i>mid;i--) { upd(1,1,n,p[i]); int tot=0,one; if(p[i]>1) ask(1,1,n,1,p[i]-1,one=0,tot); if(p[i]<n) ask(1,1,n,p[i]+1,n,one=0,tot); ans[p[i]]=(n-i>=i-1-2*tot)+'0'; } puts(ans+1); } }

F-Finding the Order

我们设$A(0,0),B(0,t),C(u,y),D(v,y)(t>0)$. 用坐标表示$a^2,b^2,c^2,d^2$,然后作差来判断$u,v$的大小即可.

#include<bits/stdc++.h> using namespace std; int main() { int T,a,b,c,d; cin>>T; while(T--) { cin>>a>>b>>c>>d; if(a*a-c*c<=b*b-d*d) puts("AB//CD"); else puts("AB//DC"); } return 0; }

更直接的方法,如果$\max (AD,BC)>\max (AC,BD)$,则有$AB//CD$.

H-Harder Gcd Problem

显然1和满足$2p>n$的p是不能再配对中的. 我们倒序考虑每个$p$,把所有的未匹配的倍数找出,如果有偶数个就直接匹配.否则,留下一个2p. 这样下来,最后至多只会剩余一个数,所以匹配最大.

int T,n,ans,prime[N],tot,sta[N],top;bool v[N]; int main() { qr(T); while(T--) { qr(n); ans=n-1; for(int i=1;i<=n;i++) v[i]=0; for(int i=2;i<=n;i++) { if(!v[i]) {prime[++tot]=i; ans-=(i*2)>n;} for(int j=1,k;(k=i*prime[j])<=n;j++) { v[k]=1; if(i%prime[j]==0) break; } } pr2(ans/2); while(tot&&prime[tot]*2>n) tot--; for(int i=1;i<=n;i++) v[i]=0; while(tot) { top=0; int i=prime[tot--]; for(int j=i;j<=n;j+=i) if(!v[j]) sta[++top]=j,v[j]=1; swap(sta[1],sta[2]); while(top>1) pr1(sta[top--]),pr2(sta[top--]); v[sta[top]]=0; } } }

J-Jumping on the Graph

给定一张无向连通图,定义$D(i,j)$为两个点之间路径次大值的最小值.求${\sum }_{i=1}^n{\sum }_{j=i+1}^{n}D(i,j)$.$(n\le 1e5)$

我们从小到大依次考虑每条边 $(x,y,w)$ 的贡献. 一个重要的转化是,我们把其他边权$>w$的边的边权修改为1,$<w$的修改为0. 那么跑最短路,如果$D(i,j)\le 1$,那么$D(i,j)\le w$. 所以我们可以用当前的1对-上一次的1对($s$),那么$ans+=s\ast w$.

我们可以扫描所有1边,贡献为两边连通块大小的乘积(注意去重),复杂度为$O(m\log (m))$.(注意这是单次,所以总共$O(m^2\log m))$. 考虑优化: 首先,$x,y$是不同连通块才考虑,所有和当前连通块有关的路径都可以不选择$w$. 然后,$\Delta =s{z}_x\ast s{z}_{Y/X}+s{z}_y\ast s{z}_{X/Y},其中x,y为两个连通块,X,Y分别为两个连通块的邻接连通块集合,Y/X=\{a|a\in Y,a\notin X\}$ 对于合并问题,我们容易想到启发式合并. 我们要维护的信息有:邻接点 + 邻接点连通块的大小之和. $X$合并到$Y$,用启发式合并的话,我们只能遍历$X$不能遍历到$Y$,所以信息维护就有点困难.

为了能够遍历$Y$,我们考虑根号平衡. 因为一条边会出现两次,所以设一个阈值$T=\sqrt{2m}$,我们把邻接点数$< T $的点 的定义为小连通块,否则为大连通块. 类似的,定义小邻居(邻居是小联通块)和大邻居.

由于大邻居的数量只有至多$T$个,所以暴力扫描.$O(T)$. 而小邻居较多,我们考虑每次更新一个小连通块的时候, 如果更新后仍然是小连通块,那么把其所有的邻接点给更新.$O(T)$. 否则,扫描所有的出边,更新答案.至多更新$O(T)$次(每次$T$条边被删除),每次$O(n)$,总共$O(Tn)$. 更新大连通块的时候,我们只需更新邻接点即可.

总复杂度为:$O(Tn+m\log n)$.

#include<bits/stdc++.h> #define fi first #define se second #define lc (x<<1) #define rc (x<<1|1) #define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++) #define mk make_pair #define pi pair<int,bool> #define pll pair<ll,ll> #define pb push_back #define IT iterator #define vi vector<int> #define TP template<class o> #define SZ(a) ((int)a.size()) #define all(a) a.begin(),a.end() using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N=1e5+10,M=1.5e5+10,mod=998244353,inf=2e9; //char buf[size],*p1=buf,*p2=buf; template<class o> void qr(o &x) { char c=gc; x=0; int f=1; while(!isdigit(c)){if(c=='-')f=-1; c=gc;} while(isdigit(c)) x=x*10+c-'0',c=gc; x*=f; } template<class o> void qw(o x) { if(x/10) qw(x/10); putchar(x%10+'0'); } template<class o> void pr1(o x) { if(x<0)x=-x,putchar('-'); qw(x); putchar(' '); } template<class o> void pr2(o x) { if(x<0)x=-x,putchar('-'); qw(x); putchar('\n'); } int n,m,sz[N],fa[N],t,size[N]; bool small[N]; struct edge{ int x,y,z; bool operator <(edge b) const {return z<b.z;} } e[M]; unordered_map<int,bool > s[N],b[N],E[N];//small,big int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]); } int main() { qr(n); qr(m); t=sqrt(2*m); for(int i=1;i<=m;i++) { qr(e[i].x); qr(e[i].y); qr(e[i].z); if(e[i].x==e[i].y) continue; E[e[i].x][e[i].y]=E[e[i].y][e[i].x]=1; } for(int i=1;i<=n;i++) small[i]=(E[i].size()<=t); sort(e+1,e+m+1); for(int i=1,x,y;i<=m;i++) { x=e[i].x; y=e[i].y; if(x==y) continue; if(small[x]) s[y][x]=1; else b[y][x]=1; if(small[y]) s[x][y]=1; else b[x][y]=1; } for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,size[i]=s[i].size(); ll ans=0; // puts(""); for(int i=1,x,y;i<=m;i++) { x=get(e[i].x); y=get(e[i].y); ll z=e[i].z; if(x==y) continue; if(SZ(s[x])>SZ(s[y])) swap(x,y);//启发式合并 if(small[x]) s[y].erase(x),size[y]-=sz[x]; else b[y].erase(x); if(small[y]) s[x].erase(y),size[x]-=sz[y]; else b[x].erase(y); ll X=size[x],Y=size[y]; // pr1(X); pr2(Y); #define g p.fi for(pi p:s[x]) if(s[y].count(g)) X-=sz[g],Y-=sz[g];//去除公共部分 for(pi p:b[x]) if(!b[y].count(g)) X+=sz[g]; for(pi p:b[y]) if(!b[x].count(g)) Y+=sz[g]; ans += (sz[x]*Y+sz[y]*X)*z; // pr1(X); pr1(Y); pr2(ans); //消除x的影响 if(small[x]) { for(pi p:s[x]) size[g]-=sz[x],s[g].erase(x); for(pi p:b[x]) size[g]-=sz[x],s[g].erase(x); } else { for(pi p:s[x]) b[g].erase(x); for(pi p:b[x]) b[g].erase(x); } if(small[y]&&SZ(s[y])>t) {//变成大连通块 small[y]=0; for(pi p:s[y]) s[g].erase(y),size[g]-=sz[y],b[g][y]=1; for(pi p:b[y]) s[g].erase(y),size[g]-=sz[y],b[g][y]=1; for(pi p:s[x]) b[g][y]=1; for(pi p:b[x]) b[g][y]=1; } else if(small[y]) { for(pi p:s[y]) size[g]+=sz[x]; for(pi p:b[y]) size[g]+=sz[x]; for(pi p:s[x]) if(!s[g][y]) s[g][y]=1,size[g]+=sz[x]+sz[y]; for(pi p:b[x]) if(!s[g][y]) s[g][y]=1,size[g]+=sz[x]+sz[y]; } else { for(pi p:s[x]) b[g][y]=1; for(pi p:b[x]) b[g][y]=1; } //x对y的贡献 for(pi p:s[x]) if(!s[y].count(g)) size[y]+=sz[g],s[y][g]=1; for(pi p:b[x]) b[y][g]=1; sz[y]+=sz[x]; fa[x]=y; b[x].clear(); s[x].clear();//注意清空,否则是O(mlog(n))空间 } pr2(ans); return 0; }