P7862 [COCI2015-2016#2] DRŽAVA 题解

题意

给定一个 $n$ 个点的平面图，每个点有个权值，现在选出一个点集使得其某一个非空子集的权值之和是 $K$ 的倍数，最小化使点集联通所需的最长边。

$n\leq 5\times 10^4,K\leq 30$

题解

乱搞过的，但实际上复杂度可以做到保证。

首先有一个结论：一个大小为 $K$ 的整数集合，一定有一个子集之和使 $K$ 的倍数，证明：把这个集合任意排列，然后求出前缀和，前缀和一共有 $K+1$ 个数，根据抽屉原理，一定有两个数相同，所以可以找出来。

那么意味着，对于一个点找周围最近的 $K$ 个点就一定有解，那么对于每个点找出最近的 $K$ 个点，把这些边记录下来跑最小生成树即可。在最小生成树时记录下当前集合可以选出的数，合并的时候 $\mathcal{O}(K^2)$ 即可。

怎么找最近 $K$ 个点呢，对于这个题可以乱搞过，先对 $x$ 轴排序，然后对于每个点往后找，用一个堆维护当前前 $k$ 小，若当前点的 $x$ 轴距离已经大于前 $k$ 小中最大的距离就跳出即可。显然这是可卡的，卡的方式在我代码里面了，但是用 KDT 即可做更优。

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

struct NODE{
    int x,y,val;
}nods[50010];

struct EDGE{
    int x,y;
    double dis;
    bool operator < (const EDGE o) const{
        return dis<o.dis;
    }
};

std::vector<EDGE> edges;

int par[50010];
char f[50010][40],g[70];

int find(int x){return (x==par[x])?x:(par[x]=find(par[x]));}

double dis(int x,int y){
	return sqrt(1ll*(nods[x].x-nods[y].x)*(nods[x].x-nods[y].x)+1ll*(nods[x].y-nods[y].y)*(nods[x].y-nods[y].y));
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    register int i,j,l,r,pari,parj;
    int n=read();int k=read();

    for(i=1;i<=n;++i){
        //要卡就这样输入 能卡掉几篇题解
        // nods[i].x=1;
        // nods[i].y=1e8/n*i;
        // nods[i].val=0;
        
        nods[i].x=read();
        nods[i].y=read();
        nods[i].val=read()%k;
    }

    std::sort(nods+1,nods+1+n,[](auto a,auto b){return a.x==b.x?a.y<b.y:a.x<b.x;});

    for(i=1;i<=n;++i){
        std::priority_queue<std::pair<double,int>> h;
        for(j=i+1;j<=n;++j){
            if(h.size()<k) h.push({dis(i,j),j});
            else{
                if(nods[j].x-nods[i].x>h.top().first) break;
                else if(dis(i,j)<h.top().first){
                    h.pop();
                    h.push({dis(i,j),j});
                }
            }
        }
        while(!h.empty()) edges.push_back({i,h.top().second,h.top().first}),h.pop();
    }

    std::sort(edges.begin(),edges.end());

    for(i=1;i<=n;++i) par[i]=i,f[i][nods[i].val]=1;

    for(auto edge:edges){
        i=edge.x,j=edge.y;
        if((pari=find(i))==(parj=find(j))) continue;
        for(l=0;l<=k*2;++l) g[l]=0;
        for(l=0;l<=k;++l)if(f[pari][l])
            for(r=0;r<=k;++r)
                g[l+r]|=f[parj][r];
        for(l=0;l<=k*2;++l)
            f[pari][l%k]|=g[l]|f[parj][l%k];
        par[parj]=pari;
        if(f[pari][0]){
            printf("%.3lf",edge.dis);
            break;
        }
    }

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}