hdu 6059---Kanade's trio(字典树)
2018-06-17 22:06:09来源:未知 阅读 ()
题目链接
There are T test cases.
1≤T≤20
1≤∑n≤5∗105
0≤A[i]<230
For each test case , the first line consists of one integer n ,and the second line consists of n integers which means the array A[1..n]
题意:输入一个数列a[1]~a[n] ,求有多少个三元组(i,j,k) 满足1<=i<j<k<=n 且 a[i]异或a[j] < a[j]异或a[k]?
思路:对于a[i]与a[k],对于二进制从高位向低位进行判断,如果30位(A[i]<2^30)到25位相同,那么a[j]的这些位不管值是多少不影响异或后 a[i] 与 a[k] 的大小关系,现在第24位不同,那么a[j]的这一位必须和a[i]相同,这样a[k]异或a[j]的值一定大于a[i]异或a[j] ,第23位到第0位不管a[j]取何值不会影响大小关系了。 有上述可以得出我们只需要判断a[i]和a[k]的二进制最高不相同位就行,那么可以用一个二进制的字典树存储这n个数。
从a[i]~a[n]将a[k]插入字典树中,每次插入时需要记录 当前节点有多少数(num表示)、当前节点对应的a[j]有多少(count表示),用cn[32][2]记录第i位为0和1时的a[j]的个数,所以每次到一个节点时用count+=cn[i][1-t],表示当前的位(0或1),这样可以保证j<k,但是没有保证i<j ;
接下来将cn[][]清空,从a[1]~a[n]的进行删除,对于a[i]删除,可以保证i<k ,那么可以用count-num*cn[i][t] 保证i<j ;
代码如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int N=5e5+5; int a[N],p[35],cn[32][2]; struct node { node *son[2]; int count; int num; node() { count=0; num=0; son[0]=son[1]=NULL; } }; node *root; void add(int x,int v) { node * now=root; for(int i=30;i>=0;i--) { int t=(!!(p[i]&x)); if(now->son[t]==NULL) now->son[t]=new node(); now=now->son[t]; now->num+=v; cn[i][t]++; now->count+=v*cn[i][1-t];///当前点对应的j的个数; } } LL cal(int x) { node * now=root; LL sum=0; for(int i=30;i>=0;i--) { int t=(!!(p[i]&x)); node* bro=now->son[1-t]; if(bro) sum+=bro->count - ((LL)bro->num*(LL)cn[i][t]); now=now->son[t]; if(!now) break; } return sum; } int main() { ///cout << "Hello world!" << endl; int T; cin>>T; p[0]=1; for(int i=1;i<32;i++) p[i]=p[i-1]<<1; while(T--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); root=new node(); memset(cn,0,sizeof(cn)); for(int i=1;i<=n;i++) add(a[i],1); memset(cn,0,sizeof(cn)); LL ans=0; for(int i=1;i<n;i++){ add(a[i],-1); ans+=cal(a[i]); } printf("%lld\n",ans); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:离散化模板
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 洛谷P1164->小A点菜 2020-05-18
- 表达式·表达式树·表达式求值 2020-04-29
- STL之<string> 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash