[BZOJ3054] Rainbow的信号(考虑位运算 + DP?)

news/2024/4/20 11:13:28/

传送门

 

BZOJ没数据范围。。。

其实数据范围是这样的。。

前20%可以直接n^3暴力枚举每个区间

前40%可以考虑每一位,因为所有数每一位都是独立的,而和的期望=期望的和,那么可以枚举每一位,再枚举区间,最大 31*n*n

想到枚举每一位也就离正解不远了,可以dp,

对于xor有贡献的是区间xor值为1的区间,那么f[i]表示以i结尾的区间异或值为1的个数,那么xor就很好解决了

对于or,我们只需要找出所有的全为0的区间,拿总区间个数减去就好,

对于and,我们只需要找出所有全为1的区间即可

 

#include <cstdio>
#include <cstring>
#define N 100005
#define LL long long
#define max(x, y) ((x) > (y) ? (x) : (y))int p1, p0, mx;
int a[N], f[N];
LL n, num0, num1, cnt;
bool b[N];
double ans1, ans2, ans3;
//f[i]以i结尾的 xor值为1的数量int main()
{int i, j, k;scanf("%lld", &n);for(i = 1; i <= n; i++){scanf("%d", &a[i]);mx = max(mx, a[i]);}for(k = 0; mx; mx >>= 1, k++);for(i = 0; i < k; i++){p0 = p1 = -1;num0 = num1 = cnt = 0;for(j = 1; j <= n; j++){if(a[j] & (1 << i))f[j] = j - f[j - 1];elsef[j] = f[j - 1];cnt += f[j];b[j] = (a[j] & (1 << i));}for(j = 1; j <= n; j++){if(!b[j] && p0 == -1) p0 = j;if(b[j] && p0 ^ -1) num0 += (LL)(j - p0) * (j - p0), p0 = -1;if(b[j] && p1 == -1) p1 = j;if(!b[j] && p1 ^ -1) num1 += (LL)(j - p1) * (j - p1), p1 = -1;}if(p0 ^ -1) num0 += (LL)(j - p0) * (j - p0);if(p1 ^ -1) num1 += (LL)(j - p1) * (j - p1);cnt *= 2;for(j = 1; j <= n; j++)if(a[j] & (1 << i)) cnt--;ans1 += 1.0 * (1 << i) * cnt / n / n;ans2 += 1.0 * (1 << i) * num1 / n / n;ans3 += 1.0 * (1 << i) * (n * n - num0) / n / n;}printf("%.3lf %.3lf %.3lf\n", ans1, ans2, ans3);return 0;
}

  

转载于:https://www.cnblogs.com/zhenghaotian/p/7604817.html


http://www.ppmy.cn/news/341444.html

相关文章

[LOJ3054] 「HNOI2019」鱼

[LOJ3054] 「HNOI2019」鱼 链接 链接 题解 首先想 \(O(n^3)\) 的暴力&#xff0c;不难发现枚举 \(A\) 和 \(D\) 后&#xff0c; \((B,C)\) 和 \((E,F)\) 两组点互相之间没有影响&#xff0c;因此可以分开计算&#xff0c;对于任意一组点&#xff0c;枚举其中一个点&#xff0c;…

LOJ#3054. 「HNOI 2019」鱼

LOJ#3054. 「HNOI 2019」鱼 https://loj.ac/problem/3054 题意 平面上有n个点&#xff0c;问能组成几个六个点的鱼。(n<1000) 分析 鱼题&#xff0c;劲啊。 容易想到先枚举这个\(D\)&#xff0c;然后极角序排一下&#xff0c;我们枚举\(A\)&#xff0c;对\(B,E,F\)分别统计。…

逆序对——P3054 [USACO12OPEN]跑圈Running Laps

题目描述 农夫约翰让他的 n &#xff08;1 < n < 100,000&#xff09; 头牛在长度为 c 的跑道上进行跑 l 圈的比赛&#xff0c;所有牛从同一起点&#xff0c;以不同的速度开始跑。直到当跑得最快的那一头牛跑完 l 圈时&#xff0c;所有牛才同时停下。 约翰发现在跑圈过…

【JZOJ3054】祖孙询问【LCA】

题目大意&#xff1a; 题目链接&#xff1a;https://jzoj.net/senior/#main/show/3054 给出一棵有根树&#xff0c;询问 x x x和 y y y的祖孙关系。 思路: 水题。 直接求一遍 l c a lca lca&#xff0c;然后如果 l c a lca lca是 x x x或 y y y中的一个&#xff0c;那么 x x …

POJ 3054 High Spies 笔记

如图&#xff0c;集装箱运输&#xff0c;图中的叶节点表示国家&#xff0c;内部节点表示港口&#xff0c;集装箱只能发往其他国家。图共有n个节点&#xff0c;两个直接相邻的节点a、b&#xff0c;从 a 到 b 有 c1 个集装箱&#xff0c;从 b 到 a 有 c2 个集装箱。求从节点 fr 到…

数学- 找规律 HDU3054

HDU3054 http://acm.hdu.edu.cn/showproblem.php?pid3054 类似数据量很大 没思路的题目可以先打表找规律 先通过打表输出找到规律&#xff0c;然后根据规律解题 运行完打表代码之后会发现1,3,4,5,6,7&#xff0c;……都是到第9个数增量是有一个变化&#xff01;而2是到第4个…

基于微信小程序的失物招领系统设计与实现

博主介绍&#xff1a;✌擅长Java、微信小程序、Python、Android等&#xff0c;专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb; 不然下次找不到哟 Java项目精品实战案…

T3054 高精度练习-文件操作 codevs

http://codevs.cn/problem/3054/ 题目描述 Description 输入一组数据&#xff0c;将每个数据加1后输出 输入描述 Input Description 输入数据&#xff1a;两行&#xff0c;第一行为一个数n&#xff0c;第二行为n个数据 输出描述 Output Description 输出数据&#xff1a;一行…

【loj3054】【hnoi2019】鱼

题目 描述 ​ 难以描述。。。。。。。慢慢看。。&#xff1a; ​ https://loj.ac/problem/3054 范围 ​ $6 \le n \le 1000 , 1 \le |x| , |y| \le 10^9 $ &#xff0c; 保证 \(n\) 个点互不相同&#xff1b; 题解 枚举 \(D\) 点&#xff0c;逆时针扫描 \(AD\) &#xff0c;在…

lopa分析_AQ/T 3054-2015保护层分析(LOPA)方法应用导则

保护层分析(LOPA)方法应用导则 1 范围 本标准规定了化工企业采用LOPA方法的技术要求,包括LOPA基本程序、场景识别与筛选、初始事件确认、独立保护层评估、场景频率技术、风险评估与决策、LOPA报告和LOPA后续跟踪及审查。 本标准适用于化工企业新建、改建、扩建和在役装置(设施…

hdu 3054 Fibonacci 找规律

传送门 题意&#xff1a;第m个满足末尾连续k个0的数是斐波那契的第几项。 思路&#xff1a;先通过打表输出找到规律&#xff0c;然后根据规律解题。运行完打表代码之后会发现1,3,4,5,6,7&#xff0c;……都是到第9个数增量是有一个变化&#xff0c;而2是到第4个数增量有了变化…

打印机故障处理【以MP 3054sp 打印机为例】

打印机故障处理【以MP 3054sp 打印机为例】 1、打印机故障原因检测 声明&#xff1a; 本文适用于打印机软件设置&#xff0c;打印机硬件问题不做判断处理。 1.1 电源故障检测 拔插打印机电源&#xff0c;检查打印机是否通电。无效的话临时借用办公室其他打印机接线做测试【…

Tektronix泰克MDO3054示波器

MDO3054混合信号示波器   简单介绍   混合域示波器拥有六种仪器&#xff0c;包括频谱分析仪、函数发生器、协议分析仪&#xff0c;电压表&#xff0c;计数器&#xff0c;数字示波器等&#xff0c;让您通过一台示波器就能捕获模拟信号、数字信号和 RF 信号。随着设计挑战不断…

bzoj3054 Rainbow的信号(位运算+瞎搞)

考虑单独统计每一位对答案的贡献。 考虑枚举区间右端点i&#xff0c;那么&操作就是往左找第一个0的位置 |操作就是往左找第一个1的位置 ^操作就是记一下到i-1的异或和为0/1的个数&#xff0c;转移一下就好了 复杂度 O(logwn) O ( l o g w n ) #include <bits/stdc.h…

pyecharts案例四——动态GDP柱状图绘制

思路 for循环每一年的数据&#xff0c;基于每一年的数据&#xff0c;创建每一年的Bar对象&#xff0c;并且将该对象添加到时间线timeline中&#xff0c;最后设置自动播放并绘图 实现代码 from pyecharts.charts import Bar, Timeline from pyecharts.options import * from …

算法模板(6):贪心

区间问题 1.区间选点 给定N个闭区间&#xff0c;请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。输出选择的点的最小数量 将每个区间按照右端点从小到大排序。从前往后依次枚举每个区间。如果当前区间中已经包含点&#xff0c;则直接pass。否则…

中兴机架服务器5300g3,产品技术-H3C UniServer R5300 G3服务器-新华三集团-H3C

前所未有的性能 H3C UniServer R5300 G3支持8块双宽GPU或20块单宽GPU&#xff0c;提供更强的计算能力。 H3C UniServer R5300 G3针对CPU/GPU异构计算特点&#xff0c;采用PCIe4.0通信链路设计&#xff0c;可以实现GPU之间高速低延迟的数据通信&#xff0c;为用户带来卓越性能体…

众辰变频器nz200t参数_【变频器 上海众辰变频器NZ100-1R5G-2】价格_厂家_图片 -Hc360慧聪网...

众辰变频器(汇菱变频器)主要技术参数&#xff1a;1、额定电压、频率&#xff1a;三相380V 50/60HZ&#xff1b;单相220V 50/60HZ 2、输入电压允许范围&#xff1a;380V&#xff1a;330-440&#xff1b;单相220V&#xff1a;170-240 3、输出电压&#xff1a;0-380V&#xff1b;0…

Hi3798M V200 SDK文档介绍

目录 下载SDK并解压解压后主要的文件夹 下载SDK并解压 步骤1&#xff1a;下载Hi3798M V200 SDK。 大家如果有下载路径可以直接下载&#xff0c;如果没有的话可以使用我这个路径。 链接&#xff1a;https://pan.baidu.com/s/1buqwwZ7yBPNmi6JA2KG1eQ 提取码&#xff1a;dv6f ps…

h3c服务器r4900清空配置信息,H3C R4900 G3服务器HDM初始化配置

H3C R4900 G3出厂设置HDM专用口默认IP:192.168.1.2,默认用户名:admin,默认密码:Password@_ 服务器安装以后需要根据实际情况修改HDM IP。 如果一台一台的修改会比较繁琐,现场交付时大多使用Windows笔记本电脑,使用批处理制作了快速配置脚本。将笔记本电脑的网口和HDM 专…