当前位置: 首页 > news >正文

每日一题~abc356(对于一串连续数字 找规律,开数值桶算贡献)

添加链接描述
在这里插入图片描述
题意:对于给定的n,m 。计算0~n 每一个数和m & 之后,得到的数 的二进制中 1的个数的和。

一位一位的算。最多是60位。
在这里插入图片描述
我们只需要计算 在 1-n这些数上,有多少个数 第i位 为1.
因为是连续的自然数,每一位上1 的出现 必然存在某种规律。
我们从 第零位 开始计数。
第 i 位 的 1 的出现周期是 2^(i+1) ,其中前一半是0,后一半是1.(数量是 2^i个)
想明白这一点之后,
对于整除的那一部分,第i位的贡献是

int w=(long long )1<<i;
n/(w*2)*w 

那么整的部分算完了,接下来算 散 的那一部分

这里可以自己找个例子,算一下。不然很容易错。
max((long long )0,n%(2*w)-w+1)
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=998244353;
signed main()
{int n,m;cin>>n>>m;int ans=0;for (int i=0;i<60;i++){if (m>>i &1){int w=(long long )1<<i;ans+=n/(w*2)*w+max((long long )0,n%(2*w)-w+1);ans%=mod;}}cout<<ans<<endl;return 0;
}

在这里插入图片描述
可以注意到
ai的数值非常小,不到1e6,这个时候 就有很大可能 开数值桶。
在这里插入图片描述

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int wc=1e6+5;
int a[wc],s[wc];signed main()
{int n;cin>>n;int t=0;for (int i=0;i<n;i++){cin>>t;a[t]++;}for (int i=1;i<=wc;i++){s[i]=s[i-1]+a[i];}int ans=0;for (int i=1;i<=wc;i++){ans+=a[i]*(a[i]-1)/2;//选择两个相同的数的贡献//枚举左端点 ,比枚举右端点好,因为右端点不一定正好到wc,//后面可能还有一些比a[i]大的数 for (int j=i;j<=wc;j+=i){ans+=a[i]*(j/i)*(s[min(wc,j+i-1)]-s[j==i?i:j-1]);非常优美的代码^_^} }cout<<ans<<"\n";return 0;
}

时间复杂度: 第二层for里面,因为每次都是 i 的倍数,并且有一个上界 wc,所以是调和级数的复杂度,
复杂度为 log wc。
总的复杂度为 wc* log wc

相关文章:

每日一题~abc356(对于一串连续数字 找规律,开数值桶算贡献)

添加链接描述 题意&#xff1a;对于给定的n,m 。计算0~n 每一个数和m & 之后&#xff0c;得到的数 的二进制中 1的个数的和。 一位一位的算。最多是60位。 我们只需要计算 在 1-n这些数上&#xff0c;有多少个数 第i位 为1. 因为是连续的自然数&#xff0c;每一位上1 的…...

商业合作方案撰写指南:让你的提案脱颖而出的秘诀

作为一名策划人&#xff0c;撰写一份商业合作方案需要细致的规划和清晰的表达。 它是一个综合性的过程&#xff0c;需要策划人具备市场洞察力、分析能力和创意思维。 以下是能够帮助你撰写一份有效的商业合作方案的关键步骤和要点&#xff1a; 明确合作目标&#xff1a;设定…...

【MySQL】锁(黑马课程)

【MySQL】锁 0. 锁的考察点1. 概述1. 锁的分类1.1 属性分类1.2 粒度分类 2. 全局锁2.1 全局锁操作2.2.1 备份问题 3. 表级锁3.1 表锁3.2 语法3.3 表共享读锁&#xff08;读锁&#xff09;3.4 表独占写锁&#xff08;写锁&#xff09;3.5 元数据锁(meta data lock, MDL)3.6 意向…...

1.10编程基础之简单排序--02:奇数单增序列

OpenJudge - 02:奇数单增序列http://noi.openjudge.cn/ch0110/02/ 描述 给定一个长度为N(不大于500)的正整数序列,请将其中的所有奇数取出,并按升序输出。 输入 共2行: 第1行为 N; 第2行为 N 个正整数,其间用空格间隔。 输出 增序输出的奇数序列,数据之间以逗号间隔。数…...

【leetcode78-81贪心算法、技巧96-100】

贪心算法【78-81】 121.买卖股票的最佳时机 class Solution:def maxProfit(self, prices: List[int]) -> int:dp[[0,0] for _ in range(len(prices))] #dp[i][0]第i天持有股票&#xff0c;dp[i][1]第i天不持有股票dp[0][0] -prices[0]for i in range(1, len(prices)):dp[…...

IEC62056标准体系简介-4.IEC62056-53 COSEM应用层

为在通信介质中传输COSEM对象模型&#xff0c;IEC62056参照OSI参考模型&#xff0c;制定了简化的三层通信模型&#xff0c;包括应用层、数据链路层&#xff08;或中间协议层&#xff09;和物理层&#xff0c;如图6所示。COSEM应用层完成对COSEM对象的属性和方法的访问&#xff…...

嵌入式应用开发之代码整洁之道

前言&#xff1a;本系列教程旨在如何将自己的代码写的整洁&#xff0c;同时也希望小伙伴们懂如何把代码写脏&#xff0c;以备不时之需&#xff0c;同时本系列参考 正点原子 &#xff0c; C代码整洁之道&#xff0c;编写可读的代码艺术。 #好的代码的特点 好的代码应该都有着几…...

iwconfig iwpriv学习之路

iwconfig和iwpriv是两个常用的wifi调试工具&#xff0c;最近需要使用这两个工具完成某款wifi芯片的定频测试&#xff0c;俗话说好记性不如烂笔头&#xff0c;于是再此记录下iwconfig和iwpriv的使用方式。 -----再牛逼的梦想&#xff0c;也抵不住傻逼般的坚持&#xff01; ----2…...

【Docker-compose】搭建php 环境

文章目录 Docker-compose容器编排1. 是什么2. 能干嘛3. 去哪下4. Compose 核心概念5. 实战 &#xff1a;linux 配置dns 服务器&#xff0c;搭建lemp环境&#xff08;Nginx MySQL (MariaDB) PHP &#xff09;要求6. 配置dns解析配置 lemp Docker-compose容器编排 1. 是什么 …...

【记录】LaTex|LaTex 代码片段 Listings 添加带圆圈数字标号的箭头(又名 LaTex Tikz 库画箭头的简要介绍)

文章目录 前言注意事项1 Tikz 的调用方法&#xff1a;newcommand2 标号圆圈数字的添加方式&#xff1a;\large{\textcircled{\small{1}}}\normalsize3 快速掌握 Tikz 箭头写法&#xff1a;插入点相对位移标号node3.1 第一张图&#xff1a;插入点相对位移3.2 第二张图&#xff1…...

《框架封装 · Redis 事件监听》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

小白学webgl合集-Three.js加载器

THREE.TextureLoader: 用途: 加载单个图像文件并将其作为纹理应用到材质上。示例: const loader new THREE.DataTextureLoader(); loader.load(path/to/data.bin, function (texture) {const material new THREE.MeshBasicMaterial({ map: texture });const geometry new TH…...

【算法】字符串的排列

难度&#xff1a;中等 给你两个字符串 s1 和 s2 &#xff0c;写一个函数来判断 s2 是否包含 s1 的排列。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 换句话说&#xff0c;s1 的排列之一是 s2 的 子串 。 示例 1&#xff1a; 输入&#xff1a;…...

5-3.损失函数

文章最前&#xff1a; 我是Octopus&#xff0c;这个名字来源于我的中文名–章鱼&#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github &#xff1b;这博客是记录我学习的点点滴滴&#xff0c;如果您对 Python、Java、AI、算法有兴趣&#xff0c;可以关注我的…...

SCSA第四天

ASPF FTP --- 文件传输协议 Tftp --- 简单文件传输协议 FTP协议相较于Tftp协议 ---- 1&#xff0c;需要进行认证 2&#xff0c;拥有一套完整的命令集 用户认证 防火墙管理员认证 ---- 校验登录者身份合法性 用户认证 --- 上网行为管理中的一环 上网用户认证 --- 三层认证…...

品牌策划必读:9本改变游戏规则的营销经典

作为深耕品牌十余年的策划人&#xff0c;这些年自学啃下的书不计其数。 这里特意挑选了几本知名度不高但是却非常有用的“遗珠”优质品牌策划书籍分享出来。 如果你是一位初步了解品牌的人&#xff0c;这些书籍既包含了品牌理论基础&#xff0c;也有实用的实践指导。 这些书…...

泛型

背景 优点 类型绝对安全避免强制类型转换 泛型类 定义 使用 举例 泛型类 // 泛型类 T就是类型参数 public class Generic<T>{// key这个成员变量的类型为T,T的类型由外部指定private T t;public void set(T t){this.t t;}public T get(){return t;} }使用 // 创建一个泛…...

react动态渲染列表与函数式组件

1.如何使用jsx语法动态渲染列表呢&#xff0c;下边我用一个例子来切实总结一下 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scal…...

小程序内容管理系统设计

设计一个小程序内容管理系统&#xff08;CMS&#xff09;时&#xff0c;需要考虑以下几个关键方面来确保其功能完善、用户友好且高效&#xff1a; 1. 需求分析 目标用户&#xff1a;明确你的目标用户群体&#xff0c;比如企业、媒体、个人博主等&#xff0c;这将决定系统的功…...

HDFS 块重构和RedundancyMonitor详解

文章目录 1. 前言2 故障块的重构(Reconstruct)2.1 故障块的状态定义和各个状态的统计信息2.2 故障文件块的查找收集2.5.2.1 misReplica的检测2.5.2.2 延迟队列(postponedMisreplicatedBlocks)的构造和实现postponedMisreplicatedBlocks中Block的添加postponedMisreplicatedBloc…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...