DRŽAVA题解

Hide_In_The_Shadow · 2022-09-23 08:40:43 · 个人记录

大概题意：把集合连在一起，要求有子集的人口数能被 k 整除，而且最长边长度最小。

考场上以为这道题是最小生成树，但看一眼数据范围我人就傻了（ 5e4 无论是建边的时间还是空间都会爆炸）。

于是我只考虑拿部分分 （写了个暴力最小生成树） 竟然有 50pts! （机房某巨拿了70pts，貌似我是判断能否被整除的时候出错了?）

来个码吧（大雾）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1100000000
using namespace std;
int n,k,fa[51000],tot,sum[51000];
bool pd,ccf[51000][30];
struct node{
    double x,y;
}no[51000];
struct edg{
    int u,v;
    double w;
}e[1100000];
void add(int u,int v){
    e[++tot].u=u;
    e[tot].v=v;
    double x=no[u].x-no[v].x;
    double y=no[u].y-no[v].y;
    e[tot].w=sqrt(x*x+y*y);
}
bool cmp(edg a,edg b){
    return a.w<b.w;
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
int main(){
//  freopen("drzava.in","r",stdin);
//  freopen("drzava.out","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        int rk=0;
        scanf("%lf %lf %d",&no[i].x,&no[i].y,&rk);
        sum[i]=rk;
        if(rk%k==0)pd=1;
        else ccf[i][rk%k]=1;
        fa[i]=i;
    }
    if(pd==1){
        puts("0.000");
        return 0;
    }
    if(n<=1010){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j==i)continue;
                add(i,j);
            }
        }
        sort(e+1,e+tot+1,cmp);
        for(int i=1;i<=tot;i++){
            int u=e[i].u;
            int v=e[i].v;
            int x=findfa(u);
            int y=findfa(v);
            if(x!=y){
                fa[y]=x;
                //printf("%d %d\n",x,y);
                for(int j=1;j<k;j++){
                    if(ccf[x][j]&&ccf[y][k-j]){//这样子判断貌似是错的
                        printf("%.3lf",e[i].w);
                        return 0;
                    }
                    ccf[x][j]|=ccf[y][j];
                    //printf("%d ",ccf[x][j]);
                }
                //printf("\n");
                sum[x]+=sum[y];
                if(sum[x]%k==0){
                    printf("%.3lf",e[i].w);
                    return 0;
                }
            }
        }
    }
    return 0;
}

然而另一位机房某巨用一种很巧妙的方法直接 AC 了，根据（x^2+y^2）对点排序 ，这样点和序号相近的点的距离就会相对变小，（貌似会被（1e6,1）和（1,1e6）这样的点卡掉 ? 我就被卡了）。，而整除 k 的问题也很好解决，因为只需要至多 k 个点的集合就能凑出能 k 整除的数 （然而我证明不来），那么我们往前后50条边就好了。然而我用这种方法只能氵到 85pts （为什么大佬能建下前后100条边而我只能建前后35条，建多了就会炸，就因为我是小丑？）

后附代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1100000000
using namespace std;
int n,k,fa[51000],tot;
bool pd,mid[31];
struct node{
    double x,y;
    int rk;
    bool ccf[31];
}no[51000];
struct edg{
    int u,v;
    double w;
}e[1100000*5];
void add(int u,int v){
    e[++tot].u=u;
    e[tot].v=v;
    double x=no[u].x-no[v].x;
    double y=no[u].y-no[v].y;
    e[tot].w=sqrt(x*x+y*y);
}
bool cmp(edg a,edg b){
    return a.w<b.w;
}
bool cnmp(node a,node b){
    return (a.x*a.x+a.y*a.y)<(b.x*b.x+b.y*b.y);
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
int main(){
//  freopen("drzava.in","r",stdin);
//  freopen("drzava.out","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        int rk=0;
        scanf("%lf %lf %d",&no[i].x,&no[i].y,&no[i].rk);
        if(no[i].rk%k==0)pd=1;
        else no[i].ccf[no[i].rk%k]=1;
        fa[i]=i;
    }
    if(pd==1){
        puts("0.000");
        return 0;
    }
    sort(no+1,no+n+1,cnmp);
    for(int i=1;i<=n;i++){
        for(int j=max(1,i-35);j<=min(i+35,n);j++){//小丑双向边
            add(i,j);
        }
    }
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        int u=e[i].u;
        int v=e[i].v;
        int x=findfa(u);
        int y=findfa(v);
        if(x!=y){
            fa[y]=x;
            memset(mid,0,sizeof mid);
            for(int j=0;j<k;j++){
                if(!no[x].ccf[j])continue;
                for(int p=0;p<k;p++){//正确的判断方法
                    if(!no[y].ccf[p])continue;
                    mid[(p+j)%k]=1;
                }
            }
            for(int j=0;j<k;j++){
                no[x].ccf[j]|=mid[j],no[x].ccf[j]|no[y].ccf[j];
            }
            if(no[x].ccf[0]){
                printf("%.3lf",e[i].w);
                return 0;
            }
        }
    }
    return 0;
}

后来才发现我是小丑，我最小生成树建了双向边。 其实数据很水，只需要往后面建，然后就 AC 了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1100000000
using namespace std;
int n,k,fa[51000],tot;
bool pd,mid[31];
struct node{
    double x,y;
    int rk;
    bool ccf[31];
}no[51000];
struct edg{
    int u,v;
    double w;
}e[1100000*5];
void add(int u,int v){
    e[++tot].u=u;
    e[tot].v=v;
    double x=no[u].x-no[v].x;
    double y=no[u].y-no[v].y;
    e[tot].w=sqrt(x*x+y*y);
}
bool cmp(edg a,edg b){
    return a.w<b.w;
}
bool cnmp(node a,node b){
    return (a.x*a.x+a.y*a.y)<(b.x*b.x+b.y*b.y);
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
int main(){
//  freopen("drzava.in","r",stdin);
//  freopen("drzava.out","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        int rk=0;
        scanf("%lf %lf %d",&no[i].x,&no[i].y,&no[i].rk);
        if(no[i].rk%k==0)pd=1;
        else no[i].ccf[no[i].rk%k]=1;
        fa[i]=i;
    }
    if(pd==1){
        puts("0.000");
        return 0;
    }
    sort(no+1,no+n+1,cnmp);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=min(i+50,n);j++){
            add(i,j);
        }
    }
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        int u=e[i].u;
        int v=e[i].v;
        int x=findfa(u);
        int y=findfa(v);
        if(x!=y){
            fa[y]=x;
            memset(mid,0,sizeof mid);
            for(int j=0;j<k;j++){
                if(!no[x].ccf[j])continue;
                for(int p=0;p<k;p++){
                    if(!no[y].ccf[p])continue;
                    mid[(p+j)%k]=1;
                }
            }
            for(int j=0;j<k;j++){
                no[x].ccf[j]|=mid[j],no[x].ccf[j]|no[y].ccf[j];
            }
            if(no[x].ccf[0]){
                printf("%.3lf",e[i].w);
                return 0;
            }
        }
    }
    return 0;
}

最后提一嘴正解，其实物理建边是不需要的，我们不妨换一种思路，将所有的点按 x 为第一关键字， y 为第二关键字排序，不断复原初始状态然后二分答案，如果 x 坐标差值大于 设定值 就不用再为这个点建边，又因为之前提到过的性质，所以每个点最多会建 k 条边，不用担心超时。

附上正解！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1100000000
using namespace std;
int n,k,fa[51000],tot;
bool pd,mid[31];
struct node{
    double x,y;
    int rk;
    bool ccf[31];
}no[51000];
double dist(int u,int v){
    double x=no[u].x-no[v].x;
    double y=no[u].y-no[v].y;
    return sqrt(x*x+y*y);
}
bool cnmp(node a,node b){
    return a.x==b.x?a.y<b.y:a.x<b.x;
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
bool slove(double a){
    for(int i=1;i<=n;i++){
        memset(no[i].ccf,0,sizeof no[i].ccf);
        no[i].ccf[no[i].rk]=1;
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(no[j].x-no[i].x>a)break;
            if(dist(i,j)>a)continue;
            int u=i;
            int v=j;
            int x=findfa(u);
            int y=findfa(v);
            if(x!=y){
                fa[y]=x;
                memset(mid,0,sizeof mid);
                for(int q=0;q<k;q++){
                    if(!no[x].ccf[q])continue;
                    for(int p=0;p<k;p++){
                        if(!no[y].ccf[p])continue;
                        mid[(p+q)%k]=1;
                    }
                }
                for(int q=0;q<k;q++){
                    no[x].ccf[q]|=mid[q],no[x].ccf[q]|=no[y].ccf[q];
                }
                if(no[x].ccf[0]){
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    freopen("drzava.in","r",stdin);
//  freopen("drzava.out","w",stdout);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        int rk=0;
        scanf("%lf %lf %d",&no[i].x,&no[i].y,&no[i].rk);
        if(no[i].rk%k==0)pd=1;
        no[i].rk%=k;
    }
    if(pd==1){
        puts("0.000");
        return 0;
    }
    sort(no+1,no+n+1,cnmp);
    double l=0,r=1e7*5,mid;
    while(l<=r-0.00005){
        mid=(l+r)/2;
        //printf("%lf\n",mid);
        if(slove(mid)){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    printf("%.3lf",l);
    return 0;
}