社区讨论

数据疑似有误

P10114 [LMXOI Round 1] Size参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lrxgju7v
此快照首次捕获于
2024/01/28 20:09
2 年前
此快照最后确认于
2024/01/28 21:45
2 年前
查看原帖
RT,测试代码:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,V=1e8+2;
int n,m,d[N],p[N],b[N];
int pop[V];
long long ans,sum;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<V;i++)
        pop[i]=pop[i>>1]+(i&1);
    for(int i=1; i<=n; ++i)
        cin>>d[i],b[i]=d[i],sum+=d[i];
    if(sum>=V/2)assert(0);//sum如果大于5e7就RE
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1; i<=n; ++i)
        d[i]=lower_bound(b+1,b+1+m,d[i])-b;
    for(int i=1; i<=n; ++i)++p[d[i]];
    for(int i=1; i<=m; ++i)
        for(int j=1; j<=m; ++j)
            ans+=1ll*p[i]*p[j]*(pop[b[i]+b[j]]+pop[abs(b[i]-b[j])]);
    cout<<ans;
    return 0;
}
https://www.luogu.com.cn/record/144873999
另外建议升绿,diS\sum d_i\leq S 使得 did_i 只有 S\sqrt S 种一点都不好想,反正我赛时是先 AC 才发现这个性质的。

回复

7 条回复,欢迎继续交流。

正在加载回复...