题解:

首先如果对于一条边的两个端点均满足$>k$,则显然可以缩到一起变成一个点.

然后对于剩下的边,我们需要添加若干条使得不出现环,因为如果出现了环肯定有$\leq{k}$的点在环上.

我们可以按任意顺序添加,因为最后图的形态是固定的.

所以直接并查集水过就可以.

代码(非常蠢):

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1000010
#define M 2000010
struct Edge{
    int a,b;
    Edge(){}
    Edge(int _a,int _b):a(_a),b(_b){
        if(a>b)
            swap(a,b);
    }
    bool operator<(const Edge&B)const{
        return a>B.a;
    }
}E[M];
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return*S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int r[N],siz[N];
inline int find(int x){
    int q=x,rq;
    for(;x!=r[x];x=r[x]);
    for(;q!=x;rq=r[q],r[q]=x,q=rq);
    return x;
}
inline void merge(int a,int b){
    if(siz[a]>siz[b])
        swap(a,b);
    siz[b]+=siz[a];
    r[a]=b;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m,k,i;
    n=getint();
    m=getint();
    k=getint();
    for(i=1;i<=m;++i)
        E[i]=Edge(getint(),getint());
    for(i=1;i<=n;++i)
        r[i]=i,siz[i]=1;
    int ra,rb,cnt=0;
    for(i=1;i<=m;++i){
        if(E[i].b<=k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            ++cnt;
            if(ra!=rb)
                merge(ra,rb);
        }
    }
    for(i=1;i<=m;++i){
        if(E[i].a<=k&&E[i].b>k){
            ra=find(E[i].a);
            rb=find(E[i].b);
            if(ra!=rb)
                ++cnt,merge(ra,rb);
        }
    }
    cout<<m-cnt<<endl;
    return 0;
}

思路:

我保证这是一种奇葩算法.

我们二分答案,那么问题就转化为若任意两个部落之间的距离\(\leq{l}\),是否能够划分为为\(k\)组.

我们能发现以下性质:若能够划分为\(k'\)组,且满足\(k'>k\),则必定能够划分为\(k\)组.原因是我们可以合并一些块,那么部落之间距离的最小值必然不会减少.

因此我们只需考虑对于一个给定的\(l\),最多能够划分为几组.

考虑两个点,若两点距离\(\leq{l}\),那么必定划分在一组中.那么现在有若干个连通块,不同连通块之间的所有点的距离均\(>l\),显然当前连通块数就是我们要求的最大连通块数.

于是二分+并查集水.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define N 1010
int n,k,x[N],y[N],r[N];
 
inline void init(){for(int i=1;i<=n;++i)r[i]=i;}
inline int find(int x){int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;}
inline void merge(int x,int y){r[find(x)]=find(y);}
typedef double f2;
 
f2 dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
 
 
int main(){
    scanf("%d%d",&n,&k);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
     
    f2 Maxdis=0;
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)Maxdis=max(Maxdis,dis(i,j));
     
    f2 L=0,R=Maxdis,mid;
    while(R-L>1e-4){
        mid=(L+R)*.5;
        init();
        for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(dis(i,j)<=mid)merge(i,j);
         
        int cnt=0;for(i=1;i<=n;++i)cnt+=(i==find(i));
         
        if(cnt>=k)L=mid;else R=mid;
    }
     
    printf("%.2lf",L);
     
    return 0;
}

思路:

我们建立原串的后缀树,那么发现出现次数为1的子串仅能出现在叶子节点上的父亲边上.(说起来很容易)

然后发现每一个更新可以分解为两端,每一段可以相当于一条斜率恒定的线段.

因此我们将两段分开,按照截距从小到大排序,并用并查集模拟覆盖即可.

(说起来很容易)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
struct Node{
    Node*tranc[26],*pa;int len,begin,siz,deg;
    Node(){}
    Node(int _len,int _begin):len(_len),begin(_begin){}
}Tnull,*null=&Tnull,mem[N<<1],*P=mem,*root,*last;
Node*Newnode(int _len,int _begin){
    P->len=_len,P->begin=_begin;for(int i=0;i<26;++i)P->tranc[i]=null;P->pa=null;return P++;
}
 
char s[N];
 
struct Interval{
    int l,r,k;
    Interval(){}
    Interval(int _l,int _r,int _k):l(_l),r(_r),k(_k){}
    bool operator<(const Interval&B)const{return k<B.k;}
}S[N],S2[N];
 
int r[N];
inline void reset(int n){
    for(register int i=1;i<=n+1;++i)r[i]=i;
}
inline int find(int x){
    int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;
}
 
int v[N],vv[N];
 
Node*q[N<<1];int fr,ta;
 
int main(){
    scanf("%s",s+1);int l=strlen(s+1);
    register int i,j;int y;Node*p,*np,*q,*nq;
    for(last=root=Newnode(0,0),i=l;i>=1;--i){
        np=Newnode(last->len+1,i);np->siz=1;
        for(p=last,y=s[i]-'a';p!=null&&p->tranc[y]==null;p=p->pa)p->tranc[y]=np;
        if(p==null)np->pa=root;
        else{
            q=p->tranc[y];
            if(q->len==p->len+1)np->pa=q;
            else{
                nq=Newnode(p->len+1,0);nq->pa=q->pa,q->pa=np->pa=nq;
                memcpy(nq->tranc,q->tranc,sizeof q->tranc);
                for(;p!=null&&p->tranc[y]==q;p=p->pa)p->tranc[y]=nq;
            }
        }last=np;
    }
     
    for(p=mem;p<P;++p)++p->pa->deg;
    for(p=mem;p<P;++p)if(p->deg==0)::q[ta++]=p;
    while(fr^ta){
        p=::q[fr++];
        if(p->pa!=null){
            p->pa->siz+=p->siz;
            if(!--p->pa->deg)
                ::q[ta++]=p->pa;
        }
    }
     
    int id=0,id2=0;
    for(p=mem;p<P;++p){
        if(p->siz==1){
            //printf("%d %d %d\n",p->begin,p->len,p->pa->len);
            S[++id]=Interval(l-(p->len-p->pa->len)+1,l,1-p->begin);
            S2[++id2]=Interval(p->begin,S[id].l-1,S[id].l-p->begin+1);
        }
    }sort(S+1,S+id+1),sort(S2+1,S2+id2+1);
     
    reset(l);
    memset(v,0x3f,sizeof v);
    for(i=1;i<=id;++i){
        for(j=find(S[i].l);j<=S[i].r;j=r[j]){
            if(v[j]==0x3f3f3f3f)v[j]=S[i].k;
            r[j]=find(j+1);
        }
    }
    reset(l);
    memset(vv,0x3f,sizeof vv);
    for(i=1;i<=id2;++i){
        for(j=find(S2[i].l);j<=S2[i].r;j=r[j]){
            if(vv[j]==0x3f3f3f3f)vv[j]=S2[i].k;
            r[j]=find(j+1);
        }
    }
     
    for(i=1;i<=l;++i)printf("%d\n",min(l,min(v[i]+i,vv[i])));
     
    return 0;
}