Codeforces.959E.Mahmoud and Ehab and the xor-MST(思路)
2024-08-26 00:42:48
\(Description\)
有一张\(n\)个点的完全图,从\(0\)到\(n-1\)标号,每两点\(i,j\)间的边权为\(i\oplus j\)。求其最小生成树边权之和。
\(Solution\)
为方便,以下点从\(0\)到\(n\)编号。
每个点\(x\)应和\(x\oplus lowbit(x)\)相连,边权为\(lowbit(x)\)(\(lowbit(x)\)会和\(0\)相连,所以一定能构成树),所以答案为\(\sum_{i=1}^nlb(i)\)。
继续优化。注意到\(lb(i)\)一定是某个2次幂,所以令\(f(i)\)表示\(1\leq x\leq n\)且满足\(lb(x)=i\)的\(x\)的个数,则答案为\(\sum_{i=1}^nf(i)\times i\ (f(i)>0)=\sum_{i=0}^{\lfloor\log n\rfloor}f(2^i)\times 2^i\)
\(f(i)\)显然可以用数位DP算,但是太麻烦了。。
一些满足\(lb(i)=x\)的数,它们间隔至少是\(2x\)。比如\(x=(100)_2\),则\(i=100,1100,10100...\)(相差\(1000\))。所以\(f(x)=\lfloor\frac{n-x}{2x}\rfloor+1\ (1\leq x\leq n,x=2^y)\)。
还有DP求\(\sum_{i=1}^nlb(i)\)的做法,好长啊...先不看了。
#include <cstdio>
int main()
{
long long n,res=0;
scanf("%I64d",&n); --n;
for(long long x=1; x<=n; x<<=1)
res+=x*((n-x)/(x<<1)+1);
printf("%I64d\n",res);
return 0;
}
最新文章
- jQuery.extend 函数详解
- 【ASP.NET】利用Nuget打包package——命令行方式
- javaScript判断浏览器类型
- 循序渐进Python3(十)-- 0 -- RabbitMQ
- APP成功上线前的bug解决方案
- plsql登录找不到可连接数据库
- 思甜雅--关于qq的NABCD模型分析
- 数据类型的处理(提取自FMDB)
- Java Concurrency - Phaser, Controlling phase change in concurrent phased tasks
- mysql copy表或表数据常用的语句整理汇总
- Hash Killer I II
- mount的艺术
- 利用no_merge优化
- 最小费用最大流MCMF 最小增广
- Oracle EBS-SQL (MRP-7):检查MRP计划运行报错原因之超大数据查询2.sql
- Centos7中hadoop配置
- GraphQL基础篇
- 离线安装多版本node,使用nvm管理
- IDEA常用操作
- weblogic安装升级配置