- 考试的时候乱搞了个做法.结果以每个大数据点 \(1900+\ ms\) 的优秀效率通过了此题...
乱搞
- 建一颗 \(Trie\) 树,显然可以每次用一个 \(log\) 查询与 \(a_i\) 异或的第 \(p\) 大值.每个数与其他数异或显然最多有前 \(k\) 大有用.如果对每个数把这 \(k\) 个值查询出来,时间复杂度为 \(O(n^2log a_i)\) .
- 考虑一个简单的剪枝,用一个堆维护当前所有查询出的值中前 \(k\) 大.若当前询问与 \(a_i\) 异或的第 \(p\) 大值得到的答案比堆中最小的元素还要小,那么 \(a_i\) 这个数就不用再询问了.
- 配合 \(random\_shffle,reverse\) 等函数乱搞有奇效.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=5e5+10;
const int N=32;
ll a[MAXN];
ll s[MAXN],t=0;
struct Trie
{
int idx;
int ch[MAXN*32][2];
int tot[MAXN*32][2];
Trie(){idx=0;}
void ins(ll x)
{
int u=0;
for(int i=N-1; i>=0; --i)
{
int k=(int)((x>>i)&1LL);
tot[u][k]++;
if(ch[u][k])
u=ch[u][k];
else
u=(ch[u][k]=++idx);
}
}
ll query(ll x,int p)
{
int u=0;
--p;
ll res=0;
for(ll i=N-1; i>=0; --i)
{
int k=(int)((x>>i)&1LL);
int v;
if(ch[u][k^1])
{
if(p>=tot[u][k^1] && ch[u][k])
{
v=k;
p-=tot[u][k^1];
}
else
{
v=k^1;
res+=(1LL<<i);
}
}
else
{
v=k;
}
u=ch[u][v];
}
return res;
}
} T;
priority_queue<ll> q;
int siz=0;
int n,k;
void solve()//One Must Have His Dream.
{
srand(19260817);
random_shuffle(a+1,a+1+n);
reverse(a+1,a+1+n);
for(int i=1; i<=n; ++i)
{
int f=1;
for(int p=1; p<=min(k,i-1) && f; ++p)
{
ll c=T.query(a[i],p);
if(siz<k)
q.push(-c),++siz;
else
{
if(c<=-q.top())
f=0;
else
{
q.pop();
q.push(-c);
}
}
}
T.ins(a[i]);
}
ll ans=0;
while(!q.empty())
{
ll x=q.top();
ans-=x;
q.pop();
}
cout<<ans<<endl;
}
int main()
{
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
n=read(),k=read();
for(int i=1; i<=n; ++i)
a[i]=a[i-1]^read();
a[++n]=0;
solve();
return 0;
}
正常向
- 考后得知为 \(bzoj\) 原题.
- 正常做法:先将每个数与其他数异或的最大值放入堆中.这样所有数两两异或的最大值也一定在其中.
- 每次取堆顶加入答案,弹出堆顶(假设为与 \(a_i\) 异或的第 \(p\) 大)后,用与 \(a_i\) 异或的第 \(p+1\) 大代替.这样每个数会入堆两次.取一半输出.
- 这样做的时间复杂度就是严格 \(O(nloga_i)\) 了.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=5e5+10;
const int N=32;
ll a[MAXN];
ll s[MAXN],t=0;
struct Trie
{
int idx;
int ch[MAXN*32][2];
int tot[MAXN*32][2];
Trie(){idx=0;}
void ins(ll x)
{
int u=0;
for(int i=N-1; i>=0; --i)
{
int k=(int)((x>>i)&1LL);
tot[u][k]++;
if(ch[u][k])
u=ch[u][k];
else
u=(ch[u][k]=++idx);
}
}
ll query(ll x,int p)
{
int u=0;
--p;
ll res=0;
for(ll i=N-1; i>=0; --i)
{
int k=(int)((x>>i)&1LL);
int v;
if(ch[u][k^1])
{
if(p>=tot[u][k^1] && ch[u][k])
{
v=k;
p-=tot[u][k^1];
}
else
{
v=k^1;
res+=(1LL<<i);
}
}
else
{
v=k;
}
u=ch[u][v];
}
return res;
}
} T;
struct node
{
ll x;
int id,p;
bool operator < (const node &rhs) const
{
return x<rhs.x;
}
node(ll x,int id,int p):x(x),id(id),p(p){}
};
priority_queue<node> q;
int siz=0;
int n,k;
void solve()
{
for(int i=1;i<=n;++i)
T.ins(a[i]);
for(int i=1;i<=n;++i)
q.push(node(T.query(a[i],1),i,1));
ll ans=0;
for(int t=1;t<=2*k;++t)
{
node u=q.top();
q.pop();
if(t&1)
ans+=u.x;
int i=u.id,p=u.p;
q.push(node(T.query(a[i],p+1),i,p+1));
}
cout<<ans<<endl;
}
int main()
{
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
n=read(),k=read();
for(int i=1; i<=n; ++i)
a[i]=a[i-1]^read();
a[++n]=0;
solve();
return 0;
}
- 清 明 十 二 响.
- 考试的时候做了链的部分分,就往合并的方向上想,但下午有点太昏了太菜了,没想出正解.
- 每个点开一个堆,合并子树时就像合并链那样,启发式合并就好了.
- 启发式合并有可能会 \(swap\) 两个节点的堆,所以要记录一下对应堆的编号.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=2e5+10;
int cnt=0,head[MAXN],to[MAXN],nx[MAXN];
int mem[MAXN];
inline void addedge(int u,int v)
{
++cnt;
to[cnt]=v;
nx[cnt]=head[u];
head[u]=cnt;
}
int n;
int dfn[MAXN],dfnidx=0;
int tmp[MAXN];
priority_queue<int> Heap[MAXN];
void dfs(int u)
{
dfn[u]=++dfnidx;
for(int k=head[u];k;k=nx[k])
{
int v=to[k];
dfs(v);
if(Heap[dfn[u]].size()<Heap[dfn[v]].size())
swap(dfn[u],dfn[v]);
int m=Heap[dfn[v]].size();
for(int i=1;i<=m;++i)
{
tmp[i]=max(Heap[dfn[u]].top(),Heap[dfn[v]].top());
Heap[dfn[v]].pop();
Heap[dfn[u]].pop();
}
for(int i=1;i<=m;++i)
Heap[dfn[u]].push(tmp[i]);
}
Heap[dfn[u]].push(mem[u]);
}
int main()
{
// freopen("spring.in","r",stdin);
// freopen("spring.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)
mem[i]=read();
for(int i=2;i<=n;++i)
{
int f=read();
addedge(f,i);
}
ll ans=0;
dfs(1);
while(!Heap[dfn[1]].empty())
{
ans+=Heap[dfn[1]].top();
Heap[dfn[1]].pop();
}
cout<<ans<<endl;
return 0;
}
