51nod 1150 Logarithm
2024-08-26 01:27:05
题目来源: Ural 1318
给出n个互不相等的整数A[0] - A[n-1],选A[i]同A[j]进行异或运算(结果都 > 0无符号),对结果取lg(以10为底)并取整后记为L[i,j],求n个数之间两两运算得到的L[i,j]之和。
例如:1 10 30,1 xor 10 = 11,10 xor 30 = 20,1 xor 30 = 31。Sum = Lg(11) * 2 + Lg(20) * 2 + Lg(30) * 2 = (1 + 1 + 1) * 2 = 6(取整)。
由于i j同j i算作2个不同的,因此最终结果要 * 2。
Input
第1行:1个数N,表示整数的数量。(2 <= N <= 50000)
第2 - N + 1行:每行个1数A[i](1 <= A[i] <= 10^18)
Output
输出两两异或后取Lg(以10为底)并取整后的和。 首先建出二进制trie,然后由数据范围知log10(A[i] xor A[j])在0到19,可以枚举每个数和log10的每个取值在trie上查询出现次数
#include<cstdio>
typedef long long i64;
i64 _(){
i64 x=;
int c=getchar();
while(c<)c=getchar();
while(c>)x=x*+c-,c=getchar();
return x;
}
const int N=*;
int n;
i64 a[];
int ch[N][],sz[N],ptr=;
i64 ts[],p10[];
void ins(i64 x){
int w=;
for(int i=;~i;i--){
int d=x>>i&;
if(!ch[w][d])ch[w][d]=++ptr;
w=ch[w][d];
++sz[w];
}
}
int find(i64 x,i64 y){
int s=,w=;
for(int i=;~i;i--){
int d1=x>>i&,d2=y>>i&;
if(d2)s+=sz[ch[w][d1^d2^]];
w=ch[w][d1^d2];
}
return s;
}
int main(){
n=_();
for(int i=;i<n;i++){
a[i]=_();
ins(a[i]);
}
p10[]=;
for(int i=;i<=;i++)p10[i]=p10[i-]*;
for(int i=;i<n;i++){
for(int j=;j<=;j++)ts[j]+=find(a[i],p10[j]);
}
ts[]=1ll*n*n-ts[];
for(int i=;i>;i--)ts[i]-=ts[i-];
ts[]-=n;
i64 ans=;
for(int i=;i<=;i++)ans+=(i-)*ts[i];
printf("%lld",ans);
return ;
}
最新文章
- ASP.NET Core 中文文档 第二章 指南(4.1)ASP.NET Core MVC 与 Visual Studio 入门
- placeholder js简单实现
- VS中如何快捷地给自己的代码添加创建信息注释
- 十天精通CSS3学习笔记 part2
- 【Linux】将Oracle安装目录从根目录下迁移到逻辑卷
- linux中解决SSH连接慢问题 关键点GSSAPIAuthentication
- Day4_计算器
- SWIFT 闭包的简单使用二
- OpenMP的简单使用教程
- 如何在Windows系统中配置Mysql群集(Mysql Cluster)
- nslookup返回信息说明
- iOS开发——View的透明属性hidden、alpha、opaque
- 九度OJ 1434 今年暑假不AC
- Oracle 日期时间
- hdu_5826_physics(物理题)
- 使用(Drawable)资源——图片资源
- Web服务器磁盘满故障深入解析
- 最牛分布式消息系统:Kafka
- (转)Linux下查看文件和文件夹大小 删除日志
- Python学习笔记 set&;&;dict