【cf1012f】Xor MST【uoj176 Goodbye Yiwei C】新年的繁荣

Source

cf1012f
Goodbye Yiwei C 新年的繁荣
uoj176

Hint

请先思考后再展开

Boruvka算法

Solution

请先思考后再展开

A. 先说Xor MST

网上的做法好像都是trie上,考虑每个有分叉的节点,在上面启发式来找到最小点对
这里提供一个不同,不过也没有更快的做法,是我在看了看Boruvka后想的
就是给每个联通块维护trie,并查集的时候直接trie合并,复杂度和线段树合并是相同的
然后我还要开一个总的trie,用于询问这个点向联通块外的节点连边的最小代价,就类似主席树那样搞就行了
tire合并的总复杂度为nlogn,然后最小生成树求解过程是 $nlog^2n$

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(ll &x,const int y) {x=x<y?x:y;}
const int MAX_N=2e5+10;
const ll MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int bin[50];
struct Trie
{
struct Nod{int son[2],c,fm;}p[MAX_N*32*2];//n+1=all
int id;Trie(){memset(p,0,sizeof p);id=MAX_N;}
void insert(int x,int num,int fm)
{
for(int i=30;i>=0;i--)
{
int wt=(num&bin[i])>0;
if(!p[x].son[wt]) p[x].son[wt]=++id;
x=p[x].son[wt];p[x].c++;p[x].fm=fm;
}
}
int askmi(int x,int y,int num)//x-y
{
for(int i=30;i>=0;i--)
{
int wt=(num&bin[i])>0;
if(p[p[x].son[wt]].c-p[p[y].son[wt]].c==0) wt^=1;
num^=wt*bin[i];x=p[x].son[wt];y=p[y].son[wt];
}
return p[x].fm;
}
void merg(int x,int &y)
{
if(!x) return;
if(y==0) {y=x;return;}
p[y].c+=p[x].c;
merg(p[x].son[0],p[y].son[0]);
merg(p[x].son[1],p[y].son[1]);
}
}tr;
struct DSU
{
int fa[MAX_N],siz[MAX_N];DSU(){for(int i=0;i<MAX_N;i++) fa[i]=i,siz[i]=1;}
int findfa(int x) {return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void merg(int x,int y)
{
int fx=findfa(x),fy=findfa(y);if(fx==fy) return;
fa[fx]=fy;tr.merg(fx,fy);siz[fy]+=fx;
}
}dsu;
int a[MAX_N];
pr ner[MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<=40;i++) bin[i]=bin[i-1]<<1;
int n=qread();for(int i=1;i<=n;i++) a[i]=qread();
for(int i=1;i<=n;i++) tr.insert(i,a[i],i),tr.insert(n+1,a[i],i);
ll ans=0;
while(1)
{
for(int x=1;x<=n;x++) ner[x]=MP(INF,0);
for(int x=1;x<=n;x++)
{
int fx=dsu.findfa(x),y=tr.askmi(n+1,fx,a[x]),fy=dsu.findfa(y);
if(fx!=fy) ner[fx]=min(ner[fx],MP(a[x]^a[y],fy));
}
bool bk=0;
for(int x=1;x<=n;x++) if(x==dsu.findfa(x) and ner[x].SE)
{
int fy=dsu.findfa(ner[x].SE);if(x!=fy) ans+=ner[x].FR,dsu.merg(x,fy),bk=1;
}
if(!bk) break;
}
write(ans);
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

B. 新年的繁荣
这题其实就是解决and和or的极值生成树,那么和xor不同的在于在某些情况需要遍历两种二进制位
以本题为例,就是1->1,0->0/1
注意到m很小,那么一棵trie填满也只是 $2^m$ ,那么我们建好trie后,从下往上把1的合并到0那边
但在上一道题中,我是用了个保存权值的可合并trie,然后求联通块外是用总-当前的,然后我就不知道这种怎么保证复杂度了……只好看了看begay的代码

其实mst整体是log次,每次这个联通块只会被修改一次,询问联通块的时候,询问两端一定在不同联通块,
所以合并的时候不用立刻改tire(也没能力改),只要判断编号的异同就行了
所以可以每次给所有联通块分别建立trie(其实这样写上一道题会好写一点,我比较蠢就没想到)
那么现在每个数所在联通块是确定的,trie上维护子树编号的最大最小就能判断能否访问了

时间复杂度为 $O(m2^mlogn+nlog^2 n)$

然后对于本题,lzz有个$O(m2^m)$的优秀做法

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/fd96.html
转载请注明出处,谢谢!