P10114 [LMXOI Round 1] Size
题目背景
在漆黑的夜晚，魔女带走了 LMX，HQZ 为了拯救 LMX。要完成魔女给出的任务。
题目描述
魔女给出一个长度为 nnn 的序列 ddd，魔女想要求得：
∑i=1n∑j=1n((di⊕dj)+(di⊗dj))\\sum\\limits_{i=1}^{ n}\\sum\\limits_{j=1}^{n}{((d_i\\oplus d_j)+(d_i \\otimes d_j))}i=1∑nj=1∑n((di⊕dj)+(di⊗dj))
其中定义 ⊕\\oplus⊕ 代表二进制下两数相加的和数位上 111 的个数， ⊗\\otimes⊗ 代表二进制下较大减较小的差数位上 111 的个数。
输入格式
一行一个整数 nnn 表示序列的长度。
第二行 nnn 个非负整数，表示序列 ddd。
输出格式
一行一个整数表示答案。
输入输出样例 #1
输入 #1
2
1 3
输出 #1
7
输入输出样例 #2
输入 #2
10
114514 19 19 810 1477 44151 15260 369 2010 222
输出 #2
1396
说明/提示
样例解释 #1
如下表所示，因此答案为 1+2+2+2=71 + 2 + 2 + 2 = 71+2+2+2=7。
| 111 | 111 | 111 |
| 111 | 222 | 222 |
| 222 | 111 | 222 |
| 222 | 222 | 222 |
对于 100%100 \\%100% 的数据，保证 1≤n≤2×106,∑di≤5×1071 \\le n\\le 2\\times 10^6,\\sum\\limits d_i\\le5\\times10^71≤n≤2×106,∑di≤5×107。
| Subtask #1 | $\\le 2\\times10^6 $ | di=1d_i =1di=1 | 101010 |
| Subtask #2 | ≤5000\\le 5000≤5000 | 无 | 202020 |
| Subtask #3 | ≤2×106\\le 2\\times 10^6≤2×106 | did_idi 是 222 的次幂 | 303030 |
| Subtask #4 | ≤2×106\\le 2\\times 10^6≤2×106 | 无 | 404040 |
C++实现
#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
template<typename T>inline void read(T &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')
f=–1;c=getchar();}
while(isdigit(c))
x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
int n,cnt[N],d,a[N],len;
long long ans;
inline int calc(int x){
int res=0;
while(x)
++res,x-=x&–x;
return res;
}
int main(){
read(n);
while(n—){
read(d);
if(cnt[d]++==0) a[++len]=d;
}
for(int i=1;i<=len;++i)
for(int j=1;j<=len;++j)
ans+=1ll*cnt[a[i]]*cnt[a[j]]*(calc(a[i]+a[j])+calc(abs(a[i]–a[j])));
printf("%lld",ans);
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
