[loj6736]最小连通块
定义$f(S)$表示点集$S$的最小连通块
做法1
通过对所有节点判定,可以在$n$次询问中求出具体的$f(S)$
对于$x\ne y$,显然$(x,y)\in E$当且仅当$f(\{x,y\})=\{x,y\}$,那么直接暴力判定即可
询问次数和时间复杂度均为$o(n^{3})$
做法2
为了方便,以下认为原树为有根树,且以1为根
对于$x\ne y$,显然$x$为$y$的祖先当且仅当$x\in f(\{1,y\})$,同样直接暴力判定即可
得到任意两点祖先后代关系后,再拓扑排序即可得到整棵树
询问次数和时间复杂度均为$o(n^{2})$
做法3
将上述结论拓展,即对于$x\not\in S$,$x\in f(\{1\}\cup S)$当且仅当$S$中存在$x$的后代
若满足此条件,则可以进行以下两种操作——
在$S$中二分,可以在$o(\log |S|)$次询问和$o(|S|)$的复杂度内找到某个$S$中$x$的后代
在$S$中搜索,即重复上述二分并在当前$S$中不存在$x$的后代时结束,可以在$o(m\log |S|)$次询问和$o(m|S|\})$的复杂度内找到$S$中所有$x$的后代(其中$m$为$S$中$x$的后代数)
下面,如果将原树看作有向树(方向为儿子到父亲),并得到了其任意一个拓扑序,那么即可利用上述做法得到整棵树,具体做法如下:
维护当前点集$S$(初始为$V$),并从前往后枚举拓扑序上的点$x$,并在$S$中找到$x$的儿子并删除,不难发现此时$S$中所有$x$的后代必然都是$x$的儿子,因此通过前面的搜索来实现
注意到每一个点恰被计入$m$一次,因此询问次数约为$o(n\log n)$,时间复杂度为$o(n^{2})$
显然这个复杂度是可以接受的,那么以下问题即变为如何求拓扑序
做法4
考虑拓扑序,实际上即不断找到原树的一个叶子,而$x$为叶子当且仅当$x\not\in f(V-\{x\})$
由此,可以在$n$次询问和$o(n^{2})$的复杂度内找到一个叶子,重复此操作即可(注意$V$要删除得到的叶子)
询问次数为$o(n^{2})$,时间复杂度为$o(n^{3})$
做法5
根据上述分析,实际上是需要优化找叶子的复杂度
考虑这样一个构造:从根节点开始,不断随机找到一个后代并变为该后代
记当前节点为$x$,选出$x$子树中所有子树大小$>\frac{sz_{x}}{2}$的点,假设有$s$个(不包括$x$),那么这些节点中最深的一个子树中至多有$sz_{x}-s$个点,也即得到$s<\frac{sz_{x}}{2}$,由于$s$为整数也可以看作$s\le \frac{sz_{x}-1}{2}$
换言之,每一次递归有$\frac{1}{2}$的概率子树大小除以2,那么期望两步使得子树大小除以2,因此子树大小从$n$变为1(叶子)的期望步数即$2\log n$(实际可能略少)
关于如何找到某个后代,(若$x$不为叶子)$V-\{x\}$中总存在$x$的后代,再使用之前的二分即可
询问次数为$o(n\log^{2}n)$,时间复杂度为$o(n^{2}\log n)$
做法6
换一个思路,去减少找叶子的轮数,即每一次取出所有叶子一起处理
但这样显然会被一条链卡掉,那么再对于每一个叶子向上找一条链,满足链上的点(目前)都仅有一个儿子(注意节点会被删除),将这条链上的点也删除
令$T(x)$为$x$被删除时的轮数(初始叶子有$T(x)=1$),根据上述过程,当$T(son)$中最大值不唯一时$T(x)$即为$T(son)$的最大值,否则$T(x)$为$T(son)$最大值+1
归纳证明$T(x)\ge n$的$x$满足$sz_{x}\ge 2^{n}-1$,根据转移显然成立,因此轮数即为$\log n$
下面,问题即如何找到这样的链:
首先,仍然按照做法4,找出所有叶子,假设其构成集合$L$
一个点在链上,当且仅当其恰有一个后代在$L$中,这可以先二分找到$L$中的某个后代,再判定剩下的部分中是否还存在后代,进而每一个后代对应的点即构成其向上的链
为了保证这些点的拓扑序,再将其sort一下即可
询问次数为$o(n\log^{2}n)$,时间复杂度为$o(n^{2}\log n)$
做法7
不再去找叶子,而是考虑分治——
构造函数$solve(S,x)$,保证$S$是$x$子树中若干个点(包含$x$),其需要求出$S$的一个拓扑序
若$S=\{x\}$显然拓扑序即仅含$x$,否则考虑分治:任取$S-\{x\}$中的一个元素$y$,并找出$S$中是$y$后代的元素,然后将该部分从$S$中取出分别求拓扑序
对$S-\{y\}$中的点染色,两点同色当且仅当删除$y$后两点在同一个连通块中,并称$x$的颜色为"白色",其余颜色为"彩色",显然判定$S'\subseteq S$中的点是否同色即等价于$y\not\in f(S')$
进一步的,将$S$中的点排在序列上,并利用上述操作不断找到下一个极长连续同色段,那么即有段数次二分
(注意只需要区分白色和彩色,而不需要区分具体的颜色)
假设颜色相同的点最多有$m$个,注意到剩下的点只有$|S|-m$个,因此不难发现至多只有$o(|S|-m)$段
换言之,可以看作每一次不属于这$m$个点的点都有一次二分的贡献
考虑每一个点的贡献,对该点颜色分类讨论:
1.为白色点,注意到该次分治$S$必然缩小一半,至多$\log n$次
2.为彩色点,再分类讨论:
(1)这$m$个点为白色,同样$S$必然缩小一半,至多$\log n$次
(2)这$m$个点为彩色(且不为该点的颜色),那么其必然是$y$的轻儿子,而每一个$y$只被以此法访问一次且每一个点到根路径上只有$\log n$条轻边,因此同样至多$\log n$次
综上,至多$o(n\log n)$次二分
询问次数为$o(n\log^{2}n)$,时间复杂度为$o(n^{2}\log n)$
做法8
实际上,并不需要真的划分出$y$的子树,不妨直接递归
具体的,重新构造函数$solve(S,x)$,其需要求出$S$与$x$子树交的一个拓扑序(保证$x\in S$)
若$S-\{x\}$中不存在$x$的后代,那么该拓扑序即仅包含$x$,直接返回即可
否则,二分找到$S-\{x\}$中$x$的一个后代$y$,然后执行$solve(S,y)$得到拓扑序,再将该拓扑序中的点(即$S$与$y$子树交的点)在$S$中删除,重复此过程即可
由此执行$solve(V,1)$即可,注意到每一个节点至多执行一次二分,因此共计即$n$次二分
询问次数为$o(n\log n)$,时间复杂度为$o(n^{2})$
1 #include<bits/stdc++.h>
2 #include"C.hpp"
3 using namespace std;
4 #define N 1005
5 #define pii pair<int,int>
6 #define vi vector<int>
7 int n;
8 vi V,S0,Pos;
9 vector<pii>E;
10 void del(vi &v,int x){
11 for(int i=0;i<v.size();i++)
12 if (v[i]==x){
13 v.erase(v.begin()+i);
14 break;
15 }
16 }
17 int get_one(vi S,int x){
18 del(S,1);
19 if (x==1){
20 if (S.size())return S[0];
21 return 0;
22 }
23 S0=S,S0.push_back(1);
24 if (!ask(S0,x))return 0;
25 int l=0,r=S.size()-1;
26 while (l<r){
27 int mid=(l+r>>1);
28 S0.clear(),S0.push_back(1);
29 for(int i=l;i<=mid;i++)S0.push_back(S[i]);
30 if (ask(S0,x))r=mid;
31 else l=mid+1;
32 }
33 return S[l];
34 }
35 vi get_all(vi S,int x){
36 Pos.clear();
37 while (1){
38 int pos=get_one(S,x);
39 if (!pos)break;
40 Pos.push_back(pos);
41 del(S,pos);
42 }
43 return Pos;
44 }
45 vi calc(vi S,int x){
46 vi ans(0);
47 while (1){
48 del(S,x);
49 int y=get_one(S,x);
50 if (!y){
51 ans.push_back(x);
52 break;
53 }
54 vi s=calc(S,y);
55 for(int i=0;i<s.size();i++){
56 ans.push_back(s[i]);
57 del(S,s[i]);
58 }
59 }
60 return ans;
61 }
62 vector<pii> get_E(vi order){
63 V.clear(),E.clear();
64 for(int i=1;i<=n;i++)V.push_back(i);
65 for(int i=0;i<n;i++){
66 del(V,order[i]);
67 vi son=get_all(V,order[i]);
68 V.push_back(order[i]);
69 for(int j=0;j<son.size();j++){
70 E.push_back(make_pair(order[i],son[j]));
71 del(V,son[j]);
72 }
73 }
74 return E;
75 }
76 vector<pii> work(int nn){
77 n=nn;
78 for(int i=1;i<=n;i++)V.push_back(i);
79 return get_E(calc(V,1));
80 }
做法9
再换一个思路,直接从拓扑序上考虑
具体的,拓扑序$\{a_{i}\}$的限制即不存在$1\le x<y\le n$,使得$a_{x}$是$a_{y}$的祖先
注意到这类似于逆序对,即联想到排序,那么初始令$a_{i}=i$,并执行插入排序
换言之,即需要对于已有的拓扑序$\{a_{1},a_{2},...,a_{k}\}$,加入一个新的$x$并保证拓扑序的性质
根据之前的性质,找到最长的后缀使得其中没有$x$的后代,注意到若$x$不为第一个元素,那么$x$的上一个元素必然恰好是$x$的后代,因此更之前的元素中不存在$x$的祖先(否则与其本来为拓扑序矛盾),因此所有与$x$相关的点对仍满足上述性质,即仍为拓扑序
显然该过程可以二分,同样也仅包含$n$次二分
询问次数为$o(n\log n)$,时间复杂度为$o(n^{2})$
1 #include<bits/stdc++.h>
2 #include"C.hpp"
3 using namespace std;
4 #define N 1005
5 #define pii pair<int,int>
6 #define vi vector<int>
7 int n;
8 vi V,S0,Pos,order;
9 vector<pii>E;
10 void del(vi &v,int x){
11 for(int i=0;i<v.size();i++)
12 if (v[i]==x){
13 v.erase(v.begin()+i);
14 break;
15 }
16 }
17 int get_one(vi S,int x){
18 S0=S,S0.push_back(1);
19 if (!ask(S0,x))return -1;
20 int l=0,r=S.size()-1;
21 while (l<r){
22 int mid=(l+r>>1);
23 S0.clear(),S0.push_back(1);
24 for(int i=mid+1;i<=r;i++)S0.push_back(S[i]);
25 if (ask(S0,x))l=mid+1;
26 else r=mid;
27 }
28 return l;
29 }
30 vi get_all(vi S,int x){
31 Pos.clear();
32 del(S,1);
33 if (x==1)return S;
34 while (1){
35 int pos=get_one(S,x);
36 if (pos<0)break;
37 Pos.push_back(S[pos]);
38 del(S,S[pos]);
39 }
40 return Pos;
41 }
42 vector<pii> get_E(vi order){
43 V.clear(),E.clear();
44 for(int i=1;i<=n;i++)V.push_back(i);
45 for(int i=0;i<n;i++){
46 del(V,order[i]);
47 vi son=get_all(V,order[i]);
48 V.push_back(order[i]);
49 for(int j=0;j<son.size();j++){
50 E.push_back(make_pair(order[i],son[j]));
51 del(V,son[j]);
52 }
53 }
54 return E;
55 }
56 vector<pii> work(int nn){
57 n=nn;
58 for(int i=2;i<=n;i++){
59 int pos=get_one(order,i)+1;
60 order.insert(order.begin()+pos,i);
61 }
62 order.push_back(1);
63 return get_E(order);
64 }
最新文章
- PopupWindowAction breaking MEF import?
- 《Inside UE4》-1-基础概念
- 使用ultraiso制作启动盘
- 解析Json需要设置Mime
- [电脑常见问题] win8 ie浏览器打不开
- gawk
- css样式书写的问题
- Uva 10652 Board Wrapping(计算几何之凸包+点旋转)
- C++写geohash
- Hibernate查询对象的方法浅析
- Java集合之Map
- python中的time模块和datetime模块
- hdu 1686 Oulipo (kmp)
- 集群部署时的分布式session如何实现
- rabbitmq安装及基本操作(含集群配置)
- normalized
- CRM 2013发邮件的插件报错Cannot open Sql Encryption Symmetric Key because Symmetric Key password does not exist in Config DB
- Linux下多路复用IO接口epoll/select/poll的区别
- 学习笔记之IKM C++ 11
- 模块(3)-使用__future__
热门文章
- windows下编译caffe出现错误 C4996: &#39;std::_Copy_impl&#39;: Function call with parameters that may be unsafe?
- Java基础之(三):IDEA的安装及破解
- Java(14)面向对象之封装
- float 与 double 类型区别
- Less-23 preg_replace1
- Unity——计时器功能实现
- Python语法1
- JDK里常见容器总结
- 【二食堂】Beta - Scrum Meeting 1
- spring session实现session统一管理(jdbc实现)