C
三分
n个区间，要求至少有一个公共点，可以移动每个区间的端点，每个端点，每次移动距离x的代价x2x^2x2，问最小代价？
比较朴素的想法是，由于区间值域不大，考虑枚举这个公共点在哪。然后把所有区间拓展到恰好覆盖这个点，也就是左侧区间拓展右端点，右侧区间拓展左端点，初始包含这个点的区间不动。对于每个点暴力计算是O(n)O(n)O(n)的，再加上枚举，整体O(n2)O(n^2)O(n2)
注意到公共点位置，对于每个区间来说，代价都是一个下凸函数。而N个下凸函数叠加起来还是下凸函数（考虑从导数分析，下凸函数意味着导数单增，N个单增导数加起来，整体导数也是单增的，整体仍然是下凸函数），故可以考虑三分这个公共点，check时O(n)O(n)O(n)暴力计算n个区间的贡献，整体O(nlogn)O(n\log n)O(nlogn)
voidsolve(){intn;cin>>n;vil(n+1),r(n+1);intmx=0;rep(i,1,n){cin>>l[i]>>r[i];mx=max(mx,r[i]);}intlo=1,hi=mx;autocal=[&](intx)->int{intres=0;rep(i,1,n){if(r[i]<x){res+=(r[i]-x)*(r[i]-x);}elseif(x<l[i]){res+=(l[i]-x)*(l[i]-x);}}returnres;};while(lo<hi){intlmid=lo+(hi-lo)/3;intrmid=hi-(hi-lo)/3;if(cal(lmid)<cal(rmid)){hi=rmid-1;}else{lo=lmid+1;}}cout<<min(cal(lo),cal(hi))<<'\n';}G
贪心
每张牌有费用和伤害，如果当前牌费用是前一张牌+1，那么当前牌的伤害倍率+1，也就是如果有个费用单增的序列，造成的伤害倍率依次1x,2x,3x…问最优情况下，一副牌能造成的最高伤害？
能凑成费用单增，就要尽量凑。每轮根据费用从小到大遍历，找到所有的费用连续段，段内，每个费用可能有多张牌，让初始伤害更高的牌，使用更高的倍率是更优的。而越靠前的轮，可用牌更多，能凑出的单增序列更长，倍率更大，所以在靠前的轮，应该先用初始伤害更高的牌。考虑对于每个费用，把牌根据伤害排序，每次取伤害最高的。
贪心的实现过程中，由于费用很大，每个费用有多个牌，开个map<int,vector>记录每个费用的可用牌。每轮根据费用大小遍历map。如果一个费用的牌用光了，删除这个key。
这样虽然多轮遍历map，但是map的总操作数还是O(n)O(n)O(n)的，整体复杂度O(nlogn)O(n\log n)O(nlogn)
voidsolve(){intn;cin>>n;map<int,vi>mp;rep(i,1,n){inta,b;cin>>a>>b;mp[a].push_back(b);}for(auto&[k,v]:mp){ranges::sort(v);}intans=0,t=0,pre=-1;while(mp.size()){vi del;for(auto&[k,v]:mp){if(k!=pre+1){t=0;}++t;ans+=v.back()*t;v.pop_back();if(!v.size()){del.push_back(k);}pre=k;}for(intx:del){mp.erase(x);}}cout<<ans<<'\n';}K
MST 思维
一个无向连通图，给一些特殊节点，求使得这些点都是叶子的最小生成树
叶子的特点是，度为1。所以对于特殊点，有且必须有一条边，连接到非叶节点，想要边权最小，每个特殊节点选中的边都是他的边权最小的邻边。读入边时，维护每个特殊节点的最小邻边。注意两端都是特殊点的边不能选，直接忽略。
这样就给每个特殊点找到了一个邻边了。剩下的点没有度为1的限制了，直接跑生成树，注意需要把前面用到的边删掉。
intf[N];intfind(intx){if(f[x]==x)returnx;returnf[x]=find(f[x]);}voidmerge(intu,intv){u=find(u),v=find(v);f[u]=v;}voidsolve(){intn,m,k;cin>>n>>m>>k;via(n+1);rep(i,1,k){intx;cin>>x;a[x]=1;}if(n==2){intmn=inf;rep(i,1,m){intu,v,w;cin>>u>>v>>w;if(u!=v){mn=min(mn,w);}}cout<<mn<<'\n';return;}vvi e;vimn(n+1,inf);rep(i,1,m){intu,v,w;cin>>u>>v>>w;if(a[u]&&a[v])continue;if(a[u]){mn[u]=min(mn[u],w);}if(a[v]){mn[v]=min(mn[v],w);}if(!a[u]&&!a[v]){e.push_back({w,u,v});}}if(k==n){cout<<-1<<'\n';return;}sort(e.begin(),e.end());rep(i,1,n){f[i]=i;}intans=0,cnt=n-k;rep(i,1,n){if(a[i]){if(mn[i]==inf){cout<<-1<<'\n';return;}ans+=mn[i];}}for(auto&t:e){intw=t[0],u=t[1],v=t[2];if(find(u)!=find(v)){merge(u,v);cnt--;ans+=w;}}if(cnt!=1){cout<<-1<<'\n';}else{cout<<ans<<'\n';}}L
数论
初始给x,y<=1e12，每轮都+1，然后除以gcd(x,y)，问操作k=1e18轮后的x,y？多测
同步加一，然后看gcd，这是经典裴蜀定理，gcd(x,y)=gcd(x,y-x)，同步加一不改变y-x。又由于gcd=1的时候可以忽略，只需要考虑有几次gcd>1的时候。打表发现，gcd(x,y-x)，x,y自增这个问题，gcd>1的次数很少，接近于O(logV)O(\log V)O(logV)次。
于是考虑手动模拟这O(logV)O(\log V)O(logV)次。每一次，要做的就是快速找到x最小加几，gcd(x,y-x)>1，这可以枚举y-x的质因子，对于每个质因子，找到第一个不小于x的倍数z，那么x增加x-z次，就能gcd>1，对每个因子的增加次数取最小值，就能得到结果。
这需要我们得到y-x的质因数分解结果，肯定不能每轮都对y-x现场分解，太慢了，注意到O(y−x)=O(V),V=1e12O(y-x)=O(V),V=1e12O(y−x)=O(V),V=1e12。
注意到y-x的变化过程是每次除以一个gcd，质因子逐渐减少，所以只用在最开始分解一下y-x，后面每次更新时，删除失效的质因子。
由于是对于一个x,y有多组不同的k测试，分解放在最外面。分解x=1e12的数，可以pollard-rho，实现O(n1/4)O(n^{1/4})O(n1/4)，可以通过。也可以注意到质因子大小不超过1e6，可以先筛出来1e6以内的质数，然后逐个检查是不是y-x的因子，如果是则这个质数是y-x的一个质因子，这样的复杂度更低，只取决于筛法。
用pollard rho的话，复杂度O(V1/4+qlogK)O(V^{1/4}+q\log K)O(V1/4+qlogK)，如果考虑gcd计算的时间的话，则是O(V1/4+qlogKlogV)O(V^{1/4}+q\log K\log V)O(V1/4+qlogKlogV)
voidsolve(){intx,y,a,b,q,k;cin>>a>>b>>q;if(a==b){rep(i,1,q){cin>>k;cout<<1<<' '<<1<<'\n';}}else{factors.clear();get_factors(abs(a-b));vi F;for(auto[k,v]:factors){F.push_back(k);}rep(i,1,q){x=a,y=b;cin>>k;intd=abs(x-y);vi f=F;while(1){intmn=inf;for(intv:f){intnxt=(x+v-1)/v*v;mn=min(mn,nxt);}intdis=mn-x;if(k<dis||!f.size()){cout<<x+k<<' '<<y+k<<'\n';break;}else{k-=dis;x+=dis,y+=dis;intg=gcd(x,y);x/=g,y/=g;d=y-x;vi nf;for(intv:f){if(d%v==0){nf.push_back(v);}}swap(f,nf);}}}}}
