锐客网

  1. 首页 > 睿知 > it技术 > >

HDU5119 - Happy Matt Friends

IT知识happyfriendFriends

青春须早为，岂能长少年。这篇文章主要讲述HDU5119 - Happy Matt Friends相关的知识，希望能为你提供帮助。
HDU5119 - Happy Matt Friends【HDU5119 - Happy Matt Friends】做法：拆成两堆数，分别暴力出两组的所有异或值A,B，枚举A, 将B全部插入Trie树，通过枚举的数每一位的值,确定异或后构成的新树，然后在新树上统计比m大的值的个数即可。

#include < bits/stdc++.h> #define pb push_back typedef long long ll; const int N = 1e6 + 7; using namespace std; int n, m, a[42], b[42], numa, numb; ll ans = 0; vector< int> va; struct node{ int ch[2], num; void init() { ch[0] = ch[1] = -1; num = 0; } }T[N*20]; int cc, rt; void ins(int x) { int now = rt; for(int i = 22; i > = 0; --i) { int t = !!(x& (1< < i)); if(T[now].ch[t] == -1) { T[now].ch[t] = ++cc; T[cc].init(); } ++T[now].num; now = T[now].ch[t]; } ++T[now].num; } int cal(int x) { int now = rt, ff = 0, ans = 0; for(int i = 22; i > = 0; --i) { int t = !!(m& (1< < i)); int f = !!(x& (1< < i)); if(!t) { if(T[now].ch[1^f]!=-1) ans += T[T[now].ch[1^f]].num; now = T[now].ch[0^f]; } else { now = T[now].ch[1^f]; } if(now == -1) break; } if(now != -1) ans+=T[now].num; return ans; } int TT, CC = 0; int main() { memset(T,0,sizeof(T)); scanf("%d",& TT); while(TT--) { scanf("%d%d",& n,& m); for(int i = 0; i < n; ++i) scanf("%d",& a[i]); numa = n/2; numb = 0; for(int i = numa; i < n; ++i) b[numb++] = a[i]; ans = 0; va.clear(); for(int s = 0; s < (1< < numa); ++s) { int tmp = 0; for(int i = 0; i < numa; ++i) if(s& (1< < i)) tmp^=a[i]; va.pb(tmp); } rt = cc = 0; rt = ++cc; T[rt].init(); for(int s = 0; s < (1< < numb); ++s) { int tmp = 0; for(int i = 0; i < numb; ++i) if(s& (1< < i)) tmp^=b[i]; ins(tmp); }for(int i = 0; i < va.size(); ++i) ans += 1LL*cal(va[i]); printf("Case #%d: %lld ",++CC,ans); for(int i = 1; i < = cc; ++i) T[i].init(); } }


    推荐阅读


    上一篇：Android异步框架RxJava 1.x系列 - 事件及事件序列转换原理

    下一篇：头条Android 屏幕适配