NOI2019 I君的探险

link

题解

考虑B部分的做法。

通过分治找到每个点的父亲。

对于一个区间,考虑父亲在这个区间内的点,如果在左半边则父亲一定在左半边,否则,先modify一下左半边的每个点,如果这个点改变了则它的父亲在左半边,否则在右半边。接着对左右半边分治下去。

发现当一个点前面有奇数个点的时候,这样的操作一定可以找到恰好一个父亲

于是每次shuffle一次,做一次上述操作,删掉孤立点。

不过最前面的暴力部分和B要另写。

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
#include "explore.h"
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005],ls[200005];
int t,fn;
vector<int> s[400005];
vector<int> to[200005];
void xreport(int x,int y){
x=a[x];y=a[y];
report(x,y);
++fn;
to[x].push_back(y);
to[y].push_back(x);
}
int xquery(int x){
x=a[x];
int w=query(x);
for(auto i:to[x])w^=b[i];
return w;
}
void solve(int l,int r,int rt){
if(l==r){
int n=s[rt].size();
for(int i=0;i<n;++i)if(s[rt][i]!=l)xreport(l,s[rt][i]);
}
else{
int mid=(l+r)>>1;
int x=t;
for(int i=l;i<=mid;++i){modify(a[i]);b[a[i]]=1;}
t+=2;
int n=s[rt].size();
for(int i=0;i<n;++i)if(s[rt][i]<=mid || xquery(s[rt][i])){ s[x+1].push_back(s[rt][i]);
}
else s[x+2].push_back(s[rt][i]);
for(int i=l;i<=mid;++i){modify(a[i]);b[a[i]]=0;}
solve(l,mid,x+1);
solve(mid+1,r,x+2);
}
s[rt].clear();
}

void solveB(int l,int r,int rt){
if(l==r){
int n=s[rt].size();
for(int i=0;i<n;++i)if(s[rt][i]!=l)report(l,s[rt][i]);
return;
}
else{
int mid=(l+r)>>1;
int x=t;
for(int i=l;i<=mid;++i)modify(i);
t+=2;
int n=s[rt].size();
for(int i=0;i<n;++i)if(s[rt][i]<=mid || query(s[rt][i])){
s[x+1].push_back(s[rt][i]);
}
else s[x+2].push_back(s[rt][i]);
for(int i=l;i<=mid;++i)modify(i);
solveB(l,mid,x+1);
solveB(mid+1,r,x+2);
}
}
void explore(int n, int m) {
if(n%10==7){
t=1;
for(int i=0;i<n;++i)s[t].push_back(i);
solveB(0,n-1,t);

return ;
}
else if(n<=500){
for(int i=0;i<n-1;++i){
modify(i);
for(int j=i+1;j<n;++j){
if(query(j)!=ls[j]){
ls[j]^=1;
report(i,j);
}
}
}
return;
}
for(int i=0;i<n;++i){
a[i]=i;
}
do{
random_shuffle(a,a+n);
t=1;
for(int i=0;i<n;++i)s[1].push_back(i);
solve(0,n-1,1);
if(fn<m){
for(int i=0;i<n;++i)if(check(a[i])){swap(a[i],a[--n]);--i;}
}
}while(fn<m);
t=1;
for(int i=0;i<n;++i)s[t].push_back(i);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×