【模拟8.01】big（trie树）

一道trie树的好题

首先我们发现后手对x的操作就是将x左移一位，溢出位在末尾补全

那么我们也可以理解为现将初值进行该操作，再将前i个元素异或和进行操作，与上等同。

那么我们等于转化了问题：

我们求出m+1个数（前i个元素进行操作，再异或后面元素），并从1-2^n中找到一个数使最小值最大

（当然数已经进行溢出操作了）。

于是我们联想到trie树.........

1.建出m+1个数的trie树

2.对于从高位到低位的搜索，

若是当前只有1或0有节点，我们都有办法使结果当前位是1，那么或上这个位的1

若是都有，因为当前是高位，后手当然会把改为搞成0

若是无节点统计答案，返回

时间复杂度（nm），注意数组开为节点×50

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<string>

 4 #include<algorithm>

 5 #include<cmath>

 6 #include<vector>

 7 #include<map>

 8 #include<cstring>

 9 #define int long long

10 #define MAXN 101000

11 using namespace std;

12 int T[MAXN*50][3];int deep[MAXN*50];

13 int tot=1;

14 int summ,base;

15 int bin[MAXN];

16 int n,m,a[MAXN];int pre[MAXN];

17 int read()

18 {

19     int x=0;char c=getchar();

20     while(c<'0'||c>'9')c=getchar();

21     while(c>='0'&&c<='9')

22     {

23          x=(x<<1)+(x<<3)+(c^48);c=getchar();

24     }

25     return x;

26 }

27 void build(int x)

28 {

29      int p=1;

30      //printf("x=%lld ",x);

31      for(int i=n-1;i>=0;--i)

32      {

33           int th=((x>>i)&1);

34           //printf("i=%lld th=%lld\n",i,th);

35           if(T[p][th]==0)T[p][th]=++tot;

36           deep[T[p][th]]=bin[i];

37           p=T[p][th];

38      }

39

40 }

41 int maxn=0,ans=0;

42 void find(int p,int sum)

43 {

44     // printf("p=%lld sum=%lld\n",p,sum);

45      if((T[p][0]!=0&&T[p][1]==0))

46      {

47          sum|=deep[T[p][0]];

48          find(T[p][0],sum);

49      }

50      else if(T[p][0]==0&&T[p][1]!=0)

51      {

52          sum|=deep[T[p][1]];

53          find(T[p][1],sum);

54      }

55      else if(T[p][0]!=0&&T[p][1]!=0)

56      {

57          find(T[p][0],sum);

58          find(T[p][1],sum);

59      }

60      else

61      {

62          if(sum>maxn)

63          {

64                  maxn=sum;

65                  ans=1;

66          }

67          else if(sum==maxn)

68          {

69                  ans++;

70          }

71          return ;

72      }

73      return ;

74 }

75 signed main()

76 {

77     n=read();m=read();

78     base=(1<<n);

79     pre[0]=0;

80     bin[0]=1;for(int i=1;i<=n;++i)bin[i]=(bin[i-1]<<1);

81     for(int i=1;i<=m;++i)

82     {

83          a[i]=read();

84          summ^=a[i];

85          pre[i]=pre[i-1]^a[i];

86     }

87     for(int i=0;i<=m;++i)

88     {

89         int sur=summ^pre[i],s;

90         s=((2*pre[i]/base)+2*pre[i])%base;

91         s^=sur;

92         build(s);

93     }

94     find(1,0);

95     printf("%lld\n%lld\n",maxn,ans);

96 }

巴特西

【模拟8.01】big（trie树）

最新文章

热门文章