0%

CF1305G 题解 - Kuroni and Antihype

题目链接翻译链接

1 操作相当于有一个年龄为 0 的人已经预先在传销组织里了。

顺序非常难搞。可以看成每个人第一次连边没有贡献。这启发我们把边权直接设为 $a_i+a_j$(也是 $a_i|a_j)$,最后算边权-点权。于是变为一个最大生成树问题。

显然可以 kruskal,枚举边权,枚举以它为权的所有边(边权的子集)。复杂度 $O(3^{\log_2 n}\alpha(n))$。你可能会很惊讶,$3^{18}$ 是怎么草过这题的呢,小编也很惊讶,但是事实就是这样。

考虑 Boruvka 算法。我们需要做 $O(\log n)$ 次以下操作:

  • 对每个连通块找出其最大出边。

  • 合并这些边。

考虑如何找点 $u$ 的最大出边。这里有一个很妙的操作:另一个端点一定是 $s/a_u$ 的子集,如果 $s/a_u$ 中权值最大的点和 $u$ 不在一个连通块,那么直接取它即可;否则再求一个 $s/a_u$ 和最大值不在一个联通块的最大点。子集DP即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxN=262144;
int N;
int A[maxN],fa[maxN];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
struct node{
int p,c;
node(int p0=-1,int c0=-1){p=p0;c=c0;}
bool operator <(const node b)const{
return p<b.p;
}
bool operator >(const node b)const{
return p>b.p;
}
operator bool(){return p!=-1;}
};
node F[maxN][2];
node maxE[maxN];
int ANS;

signed main(){
scanf("%d",&N);
for(int i=0;i<N;i++) scanf("%d",&A[i]),ANS-=A[i];A[N++]=0;
for(int i=0;i<N;i++) fa[i]=i;
int cnt=N;
while(cnt!=1){
for(int s=0;s<(1<<18);s++)
F[s][0]=F[s][1]=node();
for(int i=0;i<N;i++){
node tmp(A[i],find(i));
if(tmp>F[A[i]][0]){
if(F[A[i]][0].c!=tmp.c) F[A[i]][1]=F[A[i]][0];
F[A[i]][0]=tmp;
}
if(tmp>F[A[i]][1]&&tmp.c!=F[A[i]][0].c) F[A[i]][1]=tmp;
}
for(int i=0;i<18;i++)
for(int s=0;s<(1<<18);s++) if((s>>i)&1)
for(int d=0,t=s^(1<<i);d<2;d++){
node tmp=F[t][d];
if(tmp>F[s][0]){
if(F[s][0].c!=tmp.c) F[s][1]=F[s][0];
F[s][0]=tmp;
}
if(tmp>F[s][1]&&tmp.c!=F[s][0].c) F[s][1]=tmp;
}

for(int i=0;i<N;i++) maxE[i]=node();
for(int i=0;i<N;i++){
int s=((1<<18)-1)^A[i],c=find(i);
if(F[s][0])if(F[s][0].c!=c)
{if(node(A[i]+F[s][0].p,F[s][0].c)>maxE[c]) maxE[c]=node(A[i]+F[s][0].p,F[s][0].c);}
else if(F[s][1])
{if(node(A[i]+F[s][1].p,F[s][1].c)>maxE[c]) maxE[c]=node(A[i]+F[s][1].p,F[s][1].c);}
}
for(int u=0;u<N;u++) if(u==find(u)){
int v=maxE[u].c;
if(find(u)==find(v)) continue;
cnt--;fa[find(u)]=find(v);ANS+=maxE[u].p;
}
}
printf("%lld\n",ANS);
}

彩蛋