首页 > 其他分享 >洛谷P10114题解

洛谷P10114题解

时间:2024-01-29 11:33:10浏览次数:29  
标签:代码 cnt 洛谷 limits 题解 ll P10114 sum

题意简述

给定一个长度为 \(n\) 的序列,求 \(\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}\)。

思维路径

观察数据范围可以发现 \(n\le 2\times 10^6\) 而 \(\sum\limits d_i\le5\times10^7\),这说明 \(d\) 数组中的重复值较多,直接枚举数值可以减少很多重复计算量。

对于重复值只要在计算时乘上对应的数量即可

AC 代码

代码中附了暴力的代码和正解的代码,注意分辨。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000009;
ll n,d[N],ans,f[N],vl[N],nV;

void input(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>d[i];	
}

ll cal(ll x){
	ll cnt=0;
	while(x){
		if(x&1) cnt++;
		x>>=1;
	}
	return cnt;
} 

void solveBF(){
	for(ll i=1;i<=n;i++){
		for(ll j=i;j<=n;j++){
			ll cnt=0;
//			cout<<cal(d[i])<<" "<<cal(d[j])<<" "<<cal(d[i]+d[j])<<" "<<cal(abs(d[i]-d[j]))<<"\n";
			cnt+=cal(d[i]+d[j]);
			cnt+=cal(abs(d[i]-d[j]));
			if(i==j) ans+=cnt;
			else ans+=cnt*2;
		}
	}
	cout<<ans;
}

void solve(){
	sort(d+1,d+n+1);
	if(d[n]==1){
		cout<<n*n;
		return;
	}
	for(ll i=1;i<=n;i++){
		if(d[i]!=d[i-1]) vl[++nV]=d[i];
		f[nV]++;
	}
	for(ll i=0;i<=nV;i++){
		ans+=f[i]*f[i]*cal(vl[i]);
		for(ll j=i+1;j<=nV;j++){
			ans+=f[i]*f[j]*(cal(vl[i]+vl[j])+cal(vl[j]-vl[i]))*2;
		}
	}
	cout<<ans;
}

int main(){
	input();
	if(n<=5000)
		solveBF();
	else
		solve();
	return 0;
}

标签:代码,cnt,洛谷,limits,题解,ll,P10114,sum
From: https://www.cnblogs.com/lemon-cyy/p/17994145

相关文章

  • 洛谷题解-[ABC325E] Our clients, please wait a moment
    https://www.luogu.com.cn/problem/AT_abc325_e题目描述ある国には都市がNNN個あります。あなたは、都市111にある営業所から000個以上の都市を経由して都市NNNにある訪問先へ移動しようとしています。移動手段は社用車と電車の222種類があります。都市......
  • 洛谷题单指南-排序-P1093 [NOIP2007 普及组] 奖学金
    原题链接:https://www.luogu.com.cn/problem/P1093题意解读:本题考察排序,根据题意,先按总分从大到小排,再按语文从大到小排,以上都相同则按学号从小到大排。100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=305;structstudent{intid;intyuw......
  • 洛谷题单指南-排序-P1059 [NOIP2006 普及组] 明明的随机数
    原题链接:https://www.luogu.com.cn/problem/P1059题意解读:此题主要做两件事:排序+去重,用计数排序即可解决,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=1005;inta[N];intn;intmain(){cin>>n;intx;intcnt......
  • 洛谷P10115题解
    题意简述给定一个括号序列,求整个序列的美丽值最大。思维路径见到序列和权值,很容易想到需要用DP。我们定义\(f[i][j]\)表示第\(1\)到\(i\)个括号产生的美丽值最大值,其中\(j=0\)表示第\(i\)个括号本身不参与美丽值贡献,\(j=1\)表示第\(i\)个括号本身参与美丽值贡献......
  • B3929 [GESP202312 五级] 小杨的幸运数 题解
    因为一些众所周知的原因,不放代码。分享一种考场思路:\(a\le10^7\),顺序查找肯定会废,所以可以用一种类似埃氏筛的方法将所有满足条件的数标记一下,并将其加入一个答案数组\(a\)当中。然后每次查询只需要用lower_bound函数二分查找一下,假如找到了第\(i\)个:\(a_i=x\),直接......
  • P7324 [WC2021] 表达式求值 题解
    题目链接点击打开链接题目解法不错的题首先建出表达式树说实话我一开始不知道怎么建,但看了代码之后就懂了这里简单说一下:假如要对区间\([l,r]\)建树,分\(E_r=)\)和\(E_r\neq)\)的情况\(E_r=)\),找到匹配的左括号,递归下去建树\(E_r\neq)\),\(r\)可以作为单独的一个......
  • 如何在洛谷看见别人的主页?
    最近洛谷又有点事情了,也不知怎么了。当你想要打开别人的主页时,总是会弹出“系统维护,该内容暂不可见”,这该怎么解决呢?别急,有插件可以帮助你。(以下默认使用edge)篡改猴首先我们需要安装篡改猴,link。LuoguUserContentBlockRemover接着,打开篡改猴,点击“添加新脚本…”,然后删......
  • ABC338D 题解
    赛时怎么连这题都不会。再不练练思维真的就连普及题都不会做了啊。Solution题目来源:ABC338D(inAtcoder|in洛谷)。不妨先考虑应该断掉哪条边。首先我们发现,仅断掉一条边并不会让两个结点不可达,只会让我们从一个结点绕更远的路到达目标结点。如果我们要从结点\(u\)前往结点......
  • CF1070H 题解
    思路我们第一眼看题就发现每个字符串的长度在只有\(8\)。我们需要判断的是某个字符串是不是前面字符串的子串,因为长度太小,所以可以把字符串的每一个子串放到map里,再用一个map判断一个子串是否在当前字符串出现过,出现过就不能重复记。最后在用一个map记录一下每个子串对应......
  • CF1472F 题解
    前言只要题目给了图,你就要画图。思路首先,我们要明确一点:一个矩形,如果里面不存在任何被覆盖的方格,那么这个矩形是绝对可以被覆盖的。如果现在有一个点被覆盖了。那么必定要有一个长方形从这个点下方往后。然后继续在上方接长方形继续往后。直到出现了一个新节点被覆盖。......