LOJ6469 Magic（trie）

纪念我菜的真实的一场模拟赛

首先看到这个题目，一开始就很毒瘤。一定是没有办法直接做的。

我们考虑转化问题

假设，我们选择枚举\(x\)，其中\(x\)是\(10\)的若干次方，那么我们只需要求有多少对异或完比\(x\)大的数，那么就是\(x\)对于答案的贡献了。

那么应该怎么求比多少对呢？

！！！trie！！！

对于trie的每个节点，我们维护他的子树里面的数的个数，记为\(size[x]\)

我们考虑把每一个串放进trie里面去跑，如果当前这个数的这一位是1，而10的几次方对应的也是1的话，那么当前位只能选择0，即\(root=ch[root][0]\)，如果10的几次方对应的位是0的话,那么这一位选择0一定是全都满足条件的，是1的不一定，那么我们可以把0的那边记录进答案里面，然后走1的那边试一试，\(ans=ans+ch[root][0],root=ch[root][1]\)

另一种情况同理

不过需要注意的是，因为我们的贪心的放，所以必须从高位到低位来循环

int query(int now,int lim)

{

 int root=1;

 int ans=0;

 for (register int i=62;i>=0;--i)

 {

  if (!root) break;

  if (now&(1ll << i))

  {

   if (lim & (1ll << i))

     root=ch[root][0];

   else

     ans=ans+sum[ch[root][0]],root=ch[root][1];

  }

  else

  {

   if (lim&(1ll <<i))

     root=ch[root][1];

   else

     ans=ans+sum[ch[root][1]],root=ch[root][0];

  }

 }

 return ans;

}

对于每一个，我们都这么算，那么最后的\(ans/2\)，就是我们要的答案

因为每一对，我们会重复算两遍

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define ll long long

#define int long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 1e5+1e2;

int n;

int a[maxn];

int ch[7000000][3];

int tot=1;

int ans;

int sum[7000000];

void insert(int now)

{

 int root=1;

 for (register int i=62;i>=0;--i)

 {

    int x = (now & (1ll << i));

    if (x!=0) x=1;

    else x=0;

    if (!ch[root][x]) ch[root][x]=++tot;

    root=ch[root][x];

    sum[root]++;

 }

 //cout<<tot<<endl;

}

int query(int now,int lim)

{

 int root=1;

 int ans=0;

 for (register int i=62;i>=0;--i)

 {

  if (!root) break;

  if (now&(1ll << i))

  {

   if (lim & (1ll << i))

     root=ch[root][0];

   else

     ans=ans+sum[ch[root][0]],root=ch[root][1];

  }

  else

  {

   if (lim&(1ll <<i))

     root=ch[root][1];

   else

     ans=ans+sum[ch[root][1]],root=ch[root][0];

  }

 }

 return ans;

}

int qsm(int i,int j)

{

 //if (j==0) return 0;

 int ans=1;

 while (j)

 {

  if (j&1) ans=ans*i;

  i=i*i;

  j>>=1;

 }

 return ans;

}

signed main()

{

  n=read();

  for  (int i=1;i<=n;++i) a[i]=read();

  for (register int i=1;i<=n;++i) insert(a[i]);

  int pre=0;

  for (register int i=0;i<=18;++i)

  {

     int cnt=0;

     for (register int j=1;j<=n;++j)

     {

       cnt=cnt+query(a[j],qsm(10,i)-1);

       //cout<<i<<" "<<cnt<<endl;

   }

   ans=ans+cnt;

  }

  cout<<ans/2;

  return 0;

}

巴特西

LOJ6469 Magic（trie）

最新文章

热门文章