企业官网建设流程全解析

E

二分 扫描线 划窗

一个01串，问至少包含k个1的所有子串中，1的个数/子串长度的最大值是多少？

注意到这个答案具有单调性，考虑二分答案p，于是有
( s 1 i − s 1 j ) / ( i − j ) ≥ p (s1_i-s1_j)/(i-j)\ge p(s1i​−s1j​)/(i−j)≥p

移项后等价于
s 1 i − p i ≥ s 1 j − p j s1_i-pi\ge s1_j-pjs1i​−pi≥s1j​−pj

这可以扫描线+数据结构维护，扫描线过程中枚举s 1 i − p i s1_i-pis1i​−pi，然后只要查前缀里是否有更小值，可以上log的数据结构，比如线段树，树状数组。但注意到这只需要维护一个前缀最小值，查询的前缀永远小于i ii，因此只要维护一个前缀min就行。

此外还有一个约束是至少包含k个1，因此对于i ii位置来说，设一共tot个1，可以查询的范围则为[ 0 , p o s t o t − k ) [0,pos_{tot-k})[0,postot−k​)，其中p o s i pos_iposi​表示第i ii个1的下标

voidsolve(){intn,k;cin>>n>>k;string s;cin>>s;s=' '+s;db l=0,r=1;autocheck=[&](db p)->bool{// cout << p << ":";vector<db>pre(n+1);vi pos;intc=0;rep(i,1,n){if(s[i]=='o'){pos.push_back(i);c++;}db cur=c-p*i;pre[i]=min(cur,pre[i-1]);intsz=pos.size();if(sz>=k){if(pre[pos[sz-k]-1]<=cur){// cout << i << ' ' << pos[sz - k] - 1 << ' ' << cur << ' ' << pre[pos[sz - k] - 1] << '\n';return1;}}}return0;};while(r-l>eps){db m=(l+r)/2;if(check(m))l=m;elser=m;}cout<<fixed<<setprecision(10)<<l<<'\n';}

F

调和级数 并查集 生成树

一个完全图，w ( i , j ) = g c d ( a i , a j ) w(i,j)=gcd(a_i,a_j)w(i,j)=gcd(ai​,aj​)，求最大生成树。

考虑贡献，也就是枚举g c d = g gcd=ggcd=g，计算最大生成树上有多少条边是这个g

为了最大化边权，考虑从大到小枚举g，对于一个g，边权可能为这个值的点对( i , j ) (i,j)(i,j)，必要条件为i , j i,ji,j都是g的倍数，于是考虑枚举g的倍数。

然后为了维护生成树，需要考虑连通性，全部点都连通了就不能再增加答案了，引入并查集，对于一个g来说，他所有的倍数的连边边权，只可能比g大，不可能比g再小了，因此g枚举结束后他所有的倍数，一定都在一个联通块内了，那么枚举到g时，g的倍数如果还有多个联通块，则把这些联通块一定都能连上，且连接边权都为g，有c n t cntcnt个联通块的话贡献就是( c n t − 1 ) g (cnt-1)g(cnt−1)g。

但是如何把这cnt个联通块都连上，确定边权都是g，不会是更大的？考虑如果有更大的边权，由于我们是从大到小枚举的，肯定在之前就已经连上了，也就是枚举到g时，剩下的这些边，边权一定只能是g了。

有几个实现细节

• 我们枚举的是边权g，不一定有a i = g a_i=gai​=g的点，因此不能直接把g的倍数的联通块都和g连接，考虑把这些联通块里随机选一个当根，其他的联通块都连接到根下面
• a i a_iai​可能重复，也就是一个a i a_iai​有多个，前面我们的分析是枚举值域的，不是枚举元素，那么我们把原始数组映射到cnt数组，也就是一个值i，能产生贡献的前提是c n t i > 0 cnt_i\gt 0cnti​>0，枚举倍数时，只用考虑cnt非负的倍数位置。
• 此外，对于一个g，他的倍数的联通块，每个联通块只需要一条边就能联通；但g本身也要连接到这个联通块，如果c g > 1 c_g\gt 1cg​>1，则需要c g − 1 c_g-1cg​−1条边

voidsolve(){intn;cin>>n;via(n+1);intmx=0;rep(i,1,n){cin>>a[i];mx=max(mx,a[i]);}vif(mx+1),c(mx+1);rep(i,1,n){c[a[i]]++;f[a[i]]=a[i];}auto&&find=[&](auto&&find,intx)->int{if(f[x]==x)returnx;returnf[x]=find(find,f[x]);};intans=0;rep1(i,mx,1){unordered_set<int>s;for(intj=i;j<=mx;j+=i){if(c[j]){s.insert(find(find,j));}}if(s.size()>1){ans+=i*(s.size()-1);}if(c[i]>1){ans+=(c[i]-1)*i;}if(s.size()){intrt=*s.begin();for(intx:s){if(x==rt)continue;intf1=find(find,x);intf2=find(find,rt);if(f1!=f2){f[f1]=f2;}}}}cout<<ans<<'\n';}