蔚来杯2022牛客暑期多校训练营4 N-Particle Arts

news/2024/4/28 15:00:54/文章来源:https://www.cnblogs.com/rabbit1103/p/16608441.html

问题描述

In a confined NIO space, there are nnn NIO particles, the iii-th of which has aia_iai​ joule energy. The NIO particles are very special as they keep colliding with each other randomly. When one particle carrying energy aaa joule collides with another particle carrying energy bbb joule, they will be annihilated and produce two new particles carrying the energy of a AND b  and a OR b respectively. Here AND and OR mean bitwise AND and OR operation respectively.
The variance of the energy of these particles is obviously not decreasing, but unfortunately, the space here is too small for the author to write down his proof. After enough time the variance of the energy of these particles converges to a stable value. Can you find this value?
The variance of n numbers is defined as follows.

输入格式

The first line contains an integer n (2≤n≤105), indicating the number of particles.
The second line contains nnn integers a1,a2,…,an (0≤ai​<215), indicating the enegery of the particles.

输出格式

Output a irreducible fraction a/b (b>0) in the form of a/b that represents the answer. You should ensure that gcd⁡(a,b)=1 or when a=0, b should be 1.

样例输入

5
1 2 3 4 5

样例输出

54/5

提示

Warm tip: Please note the use of data types.

题解

模拟样例可知最后方差不变时,任意两个数进行计算都不会使序列发生改变

将样例所给数字全部转换成二进制,可以发现,最后所有数字不再改变时,所有的1都被尽可能移到一起

 

考虑统计二进制下1和0的个数,将1尽可能的移到一起,即可生成最后不再改变的序列,答案即为该序列的方差

 

 

 1 #include <cstdio>
 2 #define ll long long
 3 int n,a[100005],cnt[20];
 4 ll b[100005],sum,m,ans;
 5 ll gcd(ll x,ll y)
 6 {
 7     return y?gcd(y,x%y):x;
 8 }
 9 int main()
10 {
11     int i,j,k;
12     scanf("%d",&n);
13     for (i=1;i<=n;i++)
14     {
15         scanf("%d",&a[i]);
16         for (k=0;k<15;k++)
17         {
18             if ((1ll<<k)&a[i])
19               cnt[k]++;
20         }
21     }
22     ll x,s=0;
23     for (i=1;i<=n;i++)
24     {
25         for (j=0;j<=19;j++)
26         {
27             if (cnt[j])
28               b[i]+=(1ll<<j),
29               cnt[j]--;
30         }
31         sum+=b[i];
32         s+=b[i]*b[i];
33     }    
34     ans=s*n-sum*sum;
35     x=gcd(ans,1ll*n*n);
36     printf("%lld/%lld",ans/x,1ll*n*n/x);
37     return 0;
38 } 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_2370.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【SpringBoot】定时任务

SpringBoot实现定时任务 SpringBoot创建定时任务,目前主要有以下三种实现方式:基于注解(@Scheduled): 基于注解@Scheduled默认为单线程,开启多个任务时,任务的执行时机会受上一个任务执行时间的影响; 基于接口(SchedulingConfigurer): 用于实现从数据库获取指定时间来…

蔚来杯2022牛客暑期多校训练营2 G-Link with Monotonic Subsequence

问题描述 First, lets review some definitions. Feel free to skip this part if you are familiar with them. A sequence aaa is an increasing (decreasing) subsequence of a sequence bbb if aaa can be obtained from bbb by deletion of several (possibly, zero or al…

基于NFS实现pod数据持久化

一、nfs-server服务端:挂载一块新磁盘1.1、格式化并挂载parted /dev/vdb mklable xfs parted /dev/vdb primay 0% 100% mkfs.xfs /dev/vdb1 echo "/dev/vdb1 /nfs_share xfs defaults 0 0" >> /etc/fstab mount -a 1.2、安装nfs服务apt install nfs-kernel-s…

Mybatis的缓存

1. Mybatis的一级缓存 Mybatis的一级缓存是默认开启的,你只要搭建一个Mybatis框架,就可以直接使用一级缓存。 一级缓存是SqlSession级别的,通过SqlSession查询的数据会被缓存,下次使用同一个SqlSession查询相同的数据,就会从缓存中直接获取,不会从数据库重新访问,减轻数…

2022年多校冲刺NOIP联训测试13 51nod2023省选联训 第三场

A 隔离 二分答案,简单\(check\)一下即可code #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #include<vector> #include<set> #include<map> #include<iostream> #include<random>using na…

低风险稳健策略:BTC套利策略

更多精彩内容,欢迎关注公众号:数量技术宅,也可添加技术宅个人微信号:sljsz01,与我交流。 币安零手续费带来的机会 从7月8日的20点开始,币安推出了BTC现货交易零手续费的优惠活动,不论是Maker还是Taker都不收取手续费。此次活动包括了交易量最大的BTC/USDT和BTC/BUSD。BT…

适用于ps的Raw格式图像插件

Adobe Camera Raw14 中文版是适用于ps的Raw格式图像插件,安装上Camera Raw插件能在PS中打开编辑RAW格式文件,可以说是专业摄影师必备工具。目前Adobe Camera Raw中文版已经支持大部分主流相机,可以让用户在PS中处理各种形态的RAW文件。 软件下载地址 Camera Raw 软件是作为一…

AJAX概念和AJAX实现_原生JS方式

AJAX概念:概念:ASynchronous JavaScript And XML 异步的JavaScript和XML AJAX是一种在无需重新加载整个网页的情况下能够更新部分网页的技术。通过在后台于服务器进行少量数据叫唤,Ajax可以使网页实现异步更新,这意味着可以在不重新加载整个网页的情况下,对网页的某部分进…

RadioGroup+RadioButton进行美化,以替换之前的选择状态

效果图: 1、进行样式定义 radio_sel_state:<?xml version="1.0" encoding="utf-8"?> <selector xmlns:android="http://schemas.android.com/apk/res/android"><item android:state_checked="false"android:drawab…

Hadoop常见的文件格式及压缩算法

前言该文章中将会整理一些大数据中常见的文件格式及压缩算法的理论知识,作为后期实践的理论指导。理论+实践才会更方便用这些文件格式和压缩算法。 目前hadoop中常见的文件格式有textfile、sequencefile、avro、rcfile、orcfile、parquet等,上述六种文件格式又可以划分为行…

Vue3 + Socket.io + Knex + TypeScript 实现可以私聊的聊天室

前言 下文只在介绍实现的核心代码,没有涉及到具体的实现细节,如果感兴趣可以往下看,在文章最后贴上了仓库地址。项目采用前后端模式,前端使用 Vite + Vue3 + TS;后端使用 Knex + Express + TS。目前项目还没有完全实现,文章的目的是记录阶段性“胜利”和分享知识。 关于搭…

Docker入门-基础知识

Docker入门-基础知识 Cloud研习社 Cloud研习社 2022-06-17 07:26 发表于山东收录于合集#实战经验33个 #云计算34个 #计算机37个 #docker3个 #IT23个 Docker 是一个用于开发、发布和运行应用程序的开放平台。Docker 使您能够将应用程序与基础架构分离,以便您可以快速交付软件。…

AJAX概念和AJAX实现原生JS方式

AJAX概念 概念:ASynchronous JavaScript And XML 异步的JavaScript 和 XML1.异步和同步:客户端和服务器端相互通信的基础上同步:客户端必须等待服务器端的响应。在等待的期间客户端不能做其他操作。异步:客户端不需要等待服务器端的响应。在服务器处理请求的过程中,客户端…

mysql初识

mysql需要了解哪些知识 1.sql操作 2.索引 索引原理 索引优化 sql语句优化 3.事务 并发读异常的问题 并发死锁怎么解决 4. mysql与缓存 解决读性能问题 集群的内容OLTP: OLTP(online transaction processing)翻译为联机事务处理;主要对数据库增删改查; OLTP主要用来记录某类…

5个必知的高级SQL函数

5个必知的高级SQL函数SQL是关系数据库管理的标准语言,用于与数据库通信。它广泛用于存储、检索和操作数据库中存储的数据。SQL不区分大小写。用户可以访问存储在关系数据库管理系统中的数据。SQL允许描述数据。用户可以轻松创建和删除表和数据库。我们可以使用SQL库、模块和预…

Golang基础教程

以下使用goland的IDE演示,包含总计的golang基础功能共20个章节 一、go语言结构: 二、go基础语法:三、变量四、常量五、运算符 六、条件语句 七、循环 八、函数 九、变量作用域 十、数组 十一、指针 十二、结构体 十三、切片 十四、范围(Range) 十五、集合 十六、递归 十七、…

ceph 009 管理定义crushmap 故障域

管理和自定义crushmap 定义pg到osd的映射关系 通过crush算法使三副本映射到理想的主机或者机架 更改故障域提高可靠性 pg到osd映射由crush实现下载时需要将对象从osd搜索到,组成文件,那么对象多了就会效率变低,那么从pg组里面搜索。提高效率 对象放在pg要通过hash算法 95个…

网络编程-TCP通信程序(下)代码

TCP通信的客户端:向服务器发送连接请求,给服务端发送数据,读取服务端回写的数据 表示客户端的类:java.net.Socket:该类实现客户端套接字(也称为“套接字”)。 套接字是两台机器之间通讯的端点。套接字:包含了IP地址和端口号的网络单位 构造方法: Socket(String host, …

IfcDocumentInformation

IfcDocumentInformation实体定义 IfcDocumentInformation捕获外部文档的“元数据”。本规范未定义文件的实际内容;相反,它可以在Location属性之后找到。可以使用IfcDocumentReference从交换结构中全部或部分引用相同的IFCDocationInformation(例如,通过引用特定章节或段落)…

Volatile介绍

介绍 volatile 是 Java 虚拟机提供的轻量级的同步机制,它可以保证可见性(缓存一致性协议)和有序性(禁止指令重排序,也就是通过内存屏障来实现),但是不保证原子性。JMM 介绍 JMM 是一个抽象的概念,它描述的是一种规范。这些规范定义了程序中各种变量的访问规则。 JMM 定…