Fork me on GitHub

Uoj#349.【WC2018】即时战略

Uoj#349.【WC2018】即时战略 题解

题意:

  • 有一棵$n$个点的树,你需要进行若干次$explore(x,y)$的操作,满足$x$节点是已知的,它会返回$z$节点表示$x$到$y$路径上的第二个节点并标为已知的。
  • 开始只有$1$节点已知,现要求你在一定步数之内使得所有点变为已知。
  • $1\le n\le 300000$。

题解:

  • 考场上似乎就拿了自认为能拿的$65$分。
  • 但是最后半个小时突然想出$\rm lct$做法,然而却没有时间实现了。
  • 现在想想,这道题两个做法感觉都蛮容易想到的。
  • 根据给出的数据范围我们发现除了链以外,其他点的最严格限制在$n\log n$左右。
  • 然而因为链跟其他情况做法完全不同所以分开来讲。

链部分:

  • 我们选任意一个节点$x$,将其$explore(1,x)$的节点的方向作为默认方向。
  • 我们记录$1$节点向左向右所能到达的最远点$Max_1,Max_2$。
  • 按照随机的序列加入点。
  • 如果一个点$x$被访问过了,显然跳过。
  • 否则$explore(Max_1,x)$,如果得到的点被访问过那么就说明$x$在$Max_2$的方向。
  • 所以我们一直$explore(Max_2,x)$直到其被访问。
  • 如果未被访问,就直一直$explore(Max_1,x)$直到其被访问。
  • (当然如果每次随机向左向右肯定更强)
  • 显然除了每个点必定被访问的一次操作以外,多余操作就是猜错方向的操作次数。
  • 所以期望操作次数是$n+O(\log n)$。

动态点分治:

  • 因为其他部分的操作次数大概限制在$n\log n$左右,这看起来跟重心的性质很有关系。
  • 所以我们使用类似普通点分的思想。
  • 大致思想跟紫荆花之恋差不多。
  • 我们仿照替罪羊树设置一个阈值,表示当一棵树的现在重心的不平衡程度的上限。
  • 具体就是用$\frac{Max[G]}{size[G]}$来表示。
  • 每次加入一个点,也就是加入一条链,每次加入结束后,我们对于最高的不平衡过度的重心,我们进行整棵重建。
  • 根据替罪羊树的分析,这部分复杂度不会超过$O(n\log n)$。
  • 插入时,就相当于在重心树上走边,因为重心的性质,每次最多进行$O(\log n)$次$explore$操作。
  • 所以操作次数跟时间复杂度都是$O(n\log n)$。
  • 然而由于常数太差,我被$\rm Uoj$上的$\rm extra\ test\ 3$卡成了$\rm TLE$。

lct:

  • 每次加入一个点(链)时,如果可以在原来的链上二分,快速地跳链,就可以十分方便的加入。
  • 这跟$\rm lct$维护重链十分相似。
  • 我们可以每次在每条重链的$\rm splay$上二分到转折点,并将切入点(进入新的链的点)$\rm splay$到根,直到跳到未访问的点。
  • 然后我们将这次加入的点$\rm access$一下保证复杂度。
  • 这样操作次数跟时间复杂度也都是$O(n\log n)$。
  • 然而据说会被卡操作常数。

代码:

动态点分治:

  • 死活跑不过去($\rm TLE$)系列。
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include "rts.h"

#include <bits/stdc++.h>
#define ll long long
#define N 300009
#define MAX 0.81
using namespace std;
typedef pair<int,int> pii;
int id[N],first[N],number,vis[N],size[N],deep[N],sz[N],Max[N],root;
struct hsh
{
#define P 30222223
#define M 30222223
pii val[M];
int first[P],next[M],cnt,key[M];
int &operator [](const pii &A)
{
int _x=((ll)A.first*23333%P+A.second)%P;
for (int i=first[_x];i;i=next[i])
if (val[i]==A) return key[i];
next[++cnt]=first[_x];
first[_x]=cnt;
val[cnt]=A;
return key[cnt];
}
}mp;
struct edge
{
int to,next,vis;
void add(int x,int y)
{
to=y,next=first[x],first[x]=number,vis=0;
}
}e[N<<1];
vector<pii> q;
void get_G(int x,int last,int y,int lim,int &G)
{
Max[x]=0,sz[x]=1;
for (int i=first[x];i;i=e[i].next)
if (e[i].to!=last&&(e[i].vis>=lim||!e[i].vis))
{
get_G(e[i].to,x,y,lim,G);
Max[x]=max(Max[x],sz[e[i].to]);
sz[x]+=sz[e[i].to];
}
Max[x]=max(Max[x],y-sz[x]);
if (Max[x]<Max[G]) G=x;
}
void clear(int x,int last,int lim)
{
for (int i=first[x];i;i=e[i].next)
if (e[i].to!=last&&(e[i].vis>=lim||!e[i].vis))
{
e[i].vis=e[i^1].vis=0;
clear(e[i].to,x,lim);
}
}
int solve(int x,int y,int lim)
{
int G=0;
get_G(x,0,y,lim,G);
deep[G]=lim;
for (int i=first[G];i;i=e[i].next)
if (!e[i].vis||e[i].vis>=lim)
{
e[i].vis=e[i^1].vis=lim;
int ret=0;
if (sz[e[i].to]<sz[G]) ret=solve(e[i].to,sz[e[i].to],lim+1);
else ret=solve(e[i].to,y-sz[G],lim+1);
mp[make_pair(G,e[i].to)]=ret;
}
size[G]=y;
return G;
}
void ins(int x)
{
int now=root,nxt=explore(now,x),tmp=0;
q.clear();
q.push_back(make_pair(now,nxt));
while (vis[nxt])
{
now=mp[make_pair(now,nxt)];
nxt=explore(now,x);
q.push_back(make_pair(now,nxt));
}
while (nxt!=x)
{
e[++number].add(now,nxt);
e[++number].add(nxt,now);
vis[nxt]=1;
now=nxt;
nxt=explore(now,x);
tmp++;
}
e[++number].add(now,nxt);
e[++number].add(nxt,now);
vis[nxt]=1;
tmp++;
for (int i=0;i<(int)q.size();i++)
size[q[i].first]+=tmp;
int k=-1;
for (int i=0;i<(int)q.size()-1;i++)
if ((double)size[q[i+1].first]/size[q[i].first]>MAX)
{
k=i;
break;
}
if (k==-1) k=(int)q.size()-1;
clear(q[k].first,0,k+1);
int ret=solve(q[k].first,size[q[k].first],k+1);
if (k==0) root=ret;
else mp[make_pair(q[k-1].first,q[k-1].second)]=ret;
}
void play(int n,int T,int dataType)
{
srand((int)time(0)+(unsigned long long)new char);
for (int i=2;i<=n;i++) id[i]=i;
random_shuffle(id+2,id+n+1);
if (dataType==3)
{
vis[1]=1;
int fir=explore(1,id[2]);
vis[fir]=1;
int Max1=fir,Max2=1;
for (int i=2;i<=n;i++)
{
int now=id[i];
if (vis[now]) continue;
int ret=explore(Max1,now);
if (vis[ret])
while (Max2!=now) vis[Max2=explore(Max2,now)]=1;
else
{
vis[Max1=ret]=1;
while (Max1!=now) vis[Max1=explore(Max1,now)]=1;
}
}
return;
}
//srand(1);
size[1]=number=root=deep[1]=vis[1]=1;
Max[0]=n+1;
for (int i=2;i<=n;i++)
{
if (vis[id[i]]) continue;
ins(id[i]);
}
}

lct:

  • 到死终于骗过去系列。(趁着还没人$\rm hack$)
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
#include "rts.h"
#include <bits/stdc++.h>
#define ll long long
#define N 300009
#define MAX 0.82
using namespace std;
int id[N],vis[N];
struct LCT
{
int fa[N],ch[N][2],L[N],R[N];
bool is_root(int x)
{
return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
void up(int x)
{
L[x]=R[x]=x;
if (ch[x][0]) L[x]=L[ch[x][0]];
if (ch[x][1]) R[x]=R[ch[x][1]];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],l=ch[y][1]==x;
if (!is_root(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z,fa[y]=x,fa[ch[x][!l]]=y;
ch[y][l]=ch[x][!l],ch[x][!l]=y;
up(y),up(x);
}
void splay(int x,int y=0)
{
for (;!is_root(x);rotate(x))
if (!is_root(y=fa[x])) rotate(ch[fa[y]][1]==y^ch[y][1]==x?x:y);
}
void access(int x)
{
for (int t=0;x;t=x,x=fa[x])
splay(x),ch[x][1]=t,up(x);
}
int find_root(int x)
{
for (;!is_root(x);x=fa[x]);
return x;
}
void ins(int x)
{
int now=find_root(1);
while (!vis[x])
{
int nxt=explore(now,x);
if (nxt==R[ch[now][0]]) now=ch[now][0];
else if (nxt==L[ch[now][1]]) now=ch[now][1];
else
if (vis[nxt]) now=find_root(nxt);
else vis[nxt]=1,fa[nxt]=now,now=nxt;
}
access(x);
}
}lct;
void play(int n,int T,int dataType)
{
srand((int)time(0)+(unsigned long long)new char);
for (int i=2;i<=n;i++) id[i]=i;
random_shuffle(id+2,id+n+1);
if (dataType==3)
{
vis[1]=1;
int fir=explore(1,id[2]);
vis[fir]=1;
int Max1=fir,Max2=1;
for (int i=2;i<=n;i++)
{
int now=id[i];
if (vis[now]) continue;
int ret=explore(Max1,now);
if (vis[ret])
while (Max2!=now) vis[Max2=explore(Max2,now)]=1;
else
{
vis[Max1=ret]=1;
while (Max1!=now) vis[Max1=explore(Max1,now)]=1;
}
}
return;
}
for (int i=1;i<=n;i++) lct.L[i]=lct.R[i]=i;
for (int i=2;i<=n;i++)
{
if (vis[id[i]]) continue;
lct.ins(id[i]);
}
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#349.【WC2018】即时战略

文章作者:wzf2000

发布时间:2018年03月16日 - 08:03

最后更新:2018年03月16日 - 14:03

原始链接:https://wzf2000.github.io/2018/03/16/Uoj349/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。