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;cinnk;string s;cins;s s;db l0,r1;autocheck[](db p)-bool{// cout p :;vectordbpre(n1);vi pos;intc0;rep(i,1,n){if(s[i]o){pos.push_back(i);c;}db curc-p*i;pre[i]min(cur,pre[i-1]);intszpos.size();if(szk){if(pre[pos[sz-k]-1]cur){// cout i pos[sz - k] - 1 cur pre[pos[sz - k] - 1] \n;return1;}}}return0;};while(r-leps){db m(lr)/2;if(check(m))lm;elserm;}coutfixedsetprecision(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 gcdggcdg计算最大生成树上有多少条边是这个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_igai​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;cinn;via(n1);intmx0;rep(i,1,n){cina[i];mxmax(mx,a[i]);}vif(mx1),c(mx1);rep(i,1,n){c[a[i]];f[a[i]]a[i];}autofind[](autofind,intx)-int{if(f[x]x)returnx;returnf[x]find(find,f[x]);};intans0;rep1(i,mx,1){unordered_setints;for(intji;jmx;ji){if(c[j]){s.insert(find(find,j));}}if(s.size()1){ansi*(s.size()-1);}if(c[i]1){ans(c[i]-1)*i;}if(s.size()){intrt*s.begin();for(intx:s){if(xrt)continue;intf1find(find,x);intf2find(find,rt);if(f1!f2){f[f1]f2;}}}}coutans\n;}