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

E. Iva Pav -前缀和 + 二分 +位运算

题面

分析:

赛时一直纠结于与运算前缀和不可逆,导致没有思路,但是发现行不通并没有及时思考别的解决办法导致一条路走到黑,阻碍了自己的思维,在今年的网络赛赛时也是一样,行不通的时候就没心思去重新想其他方法,这是大忌,以后要改,必须能够赛时不断发散自己思维,思考多种解决办法,还有就是赛时遇到一些自我感觉麻烦的做法就认为对的可能性不大,就不再去想,要大胆思考各种方法,多尝试。
虽然与运算不可逆,但是拆开他的每一位,从前向后记录他的每一位的1的个数,这样就可以进行前缀和计算了,根据后来的查询,只需要查询区间内的每一位的1的个数,只要区间内每一个数的二进制表示下第 i i i位都是1,那么区间的与运算之和的第 i i i位也就一定是1,这样就可以求出区间与运算的和,进而二分解决。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 2e5 + 10;int a[N][32];
int n;
int L;
int k;bool check(int mid) {int cnt = 0;for(int i = 0; i <= 31; i ++) {//cout << a[mid][i] << ' ';if(a[mid][i] - a[L - 1][i] == mid - L + 1) cnt |= (1 << i);}
//   cout << mid << ' ' << cnt << endl;return cnt >= k;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {cin >> n;for(int i = 1; i <= n; i ++) {int x;cin >> x;for(int j = 0; j <= 31; j ++) {a[i][j] = a[i - 1][j] + (x >> j & 1);}}int q;cin >> q;while(q --) {cin >> L >> k;int l = L - 1;int r = n;while(l < r) {int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}if(l < L || l > n) cout << "-1 ";else cout << l << " ";//cout << endl;}cout << "\n";}
}

相关文章:

E. Iva Pav -前缀和 + 二分 +位运算

题面 分析&#xff1a; 赛时一直纠结于与运算前缀和不可逆&#xff0c;导致没有思路&#xff0c;但是发现行不通并没有及时思考别的解决办法导致一条路走到黑&#xff0c;阻碍了自己的思维&#xff0c;在今年的网络赛赛时也是一样&#xff0c;行不通的时候就没心思去重新想其…...

新手学习:ArcGIS对shp文件裁剪

新手学习&#xff1a;ArcGIS对SHP文件裁剪 新手学习 记录每个步骤&#xff0c;因为有很多控件可能刚开始还不熟悉&#xff0c;根本不知道在哪里&#xff0c;所以写的比较详细。 1.添加要裁剪的shp文件 2.查看shp文件的地理坐标系 双击shp文件&#xff0c;就可以查看shp文件的…...

Java 设计模式——抽象工厂模式

目录 1.概念2.结构3.实现4.优缺点5.使用场景6.模式扩展7.JDK源码解析——Collection.iterator方法 1.概念 &#xff08;1&#xff09;Java 设计模式——工厂方法模式中考虑的是一类产品的生产&#xff0c;如畜牧场只养动物、电视机厂只生产电视机等。这些工厂只生产同种类产品…...

如何使用ChatGPT构建一个Web应用程序?

围绕ChatGPT的最大卖点之一是它可以成为一种有效的编程工具。其想法是这样的&#xff1a;你用自然语言描述需求&#xff0c;该聊天机器人生成满足该需求的代码。但是ChatGPT在这方面到底有多好呢&#xff1f; 还有什么比亲自测试一下更好的方法呢&#xff1f;我们让ChatGPT从头…...

关闭手机广告的步骤

关闭手机广告的步骤 小米 1.设置→小米账号→声明与条款→系统广告→系统工具广告→关闭 2.设置→应用设置→应用管理→右上角三个点→设置→关闭“应用升级提醒”&“资源推荐” 3.桌面左滑打开负一屏→划到底部→设置→服务管理→选择关闭项目 4.桌面→打开任意文件夹…...

【Verilog 教程】6.6Verilog 仿真激励

关键词&#xff1a;testbench&#xff0c;仿真&#xff0c;文件读写 Verilog 代码设计完成后&#xff0c;还需要进行重要的步骤&#xff0c;即逻辑功能仿真。仿真激励文件称之为 testbench&#xff0c;放在各设计模块的顶层&#xff0c;以便对模块进行系统性的例化调用进行仿真…...

Win/Mac版Scitools Understand教育版申请

这里写目录标题 前言教育版申请流程教育账号申请 前言 上篇文章为大家介绍了Scitools Understand软件&#xff0c;通过领取的反馈来看有很多朋友都想用这个软件&#xff0c;但是我的网盘里只存了windows的pojie版&#xff0c;没有mac版的&#xff0c;我没有去网上找相关的资源…...

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 试题 C: 班级活动

[蓝桥杯 2023 国 B] 班级活动 【问题描述】 小明的老师准备组织一次班级活动。班上一共有 n n n 名&#xff08; n n n 为偶数&#xff09;同学&#xff0c;老师想把所有的同学进行分组&#xff0c;每两名同学一组。为了公平&#xff0c;老师给每名同学随机分配了一个 n n …...

YOLOv8改进新颖的Gather-and-Distribute机制,低阶高阶新颖融合,增强了多尺度特征融合能力,实现了延迟和准确性的理想平衡

💡本篇内容:YOLOv8改进新颖的Gather-and-Distribute机制,低阶高阶新颖融合,增强了多尺度特征融合能力,实现了延迟和准确性的理想平衡 💡🚀🚀🚀本博客 改进源代码改进 适用于 YOLOv8 按步骤操作运行改进后的代码即可 💡本文提出改进 原创 方式:二次创新,YOL…...

面试算法13:二维子矩阵的数字之和

题目 输入一个二维矩阵&#xff0c;如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和&#xff1f;对于同一个二维矩阵&#xff0c;计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如&#xff0c;输入图2.1中的二维矩阵&#xff0c;以及左上角坐标…...

Vue安装插件时候中遇到冲突依赖解决方案

错误如下&#xff1a; npm ERR! code ERESOLVE npm ERR! ERESOLVE could not resolve npm ERR! npm ERR! While resolving: vue/eslint-config-standard6.1.0 npm ERR! Found: eslint-plugin-vue8.7.1 npm ERR! node_modules/eslint-plugin-vue npm ERR! dev eslint-pl…...

realloc函数应用IO泄露体验

本题主要介绍realloc函数&#xff0c;平时我们使用realloc最多便是在打malloc_hook–>onegadget的时候&#xff0c;使用realloc_hook调整onegadget的栈帧&#xff0c;从而getshell。 在realloc函数中&#xff0c;也能像malloc一样创建堆&#xff0c;并且比malloc麻烦一些&a…...

(c语言)野指针

#include<stdio.h> //野指针 int* test() { int a 10; return &a; } int main() { //野指针一&#xff1a; int* p; *p 10; //非法访问内存 //p没有初始化&#xff0c;就意味着没有明确的指向 //一个局部变量不初始化的话&#xff…...

【Git】轻松学会 Git(一):掌握 Git 的基本操作

文章目录 前言一、创建 Git 本地仓库1.1 什么是仓库1.2 创建本地仓库1.3 .git 目录结构 二、配置 Git三、认识 Git 的工作区、暂存区和版本库3.1 什么是 Git 的工作区、暂存区和版本库3.2 工作区、暂存区和版本库之间的关系 四、添加文件4.1 添加文件到暂存区和版本库中的命令4…...

rust trait对象

在拥有继承的语言中&#xff0c;可以定义一个名为shape的基类&#xff0c;该类上有一个draw方法。其他的类比如Button、SelectBox继承shape。它们各自覆盖draw方法。调用这些子类的draw方法时&#xff0c;就可以把它们统一当作shape来使用。不过Rust并没有继承&#xff0c;如果…...

Linux学习第21天:Linux内核定时器驱动开发: 流淌的时间长河

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 在人类的发展进化中&#xff0c;时间是一个非常重要神秘的物质量。任何事物都是在时间的长河中流淌发生、发展、变化。我们进行驱动开发中对时间的定义和使用也是…...

Centos服务在服务器重启后自启

以Dolphin为例 打开rc.local文件以编辑&#xff1a; sudo vi /etc/rc.d/rc.local在文件中添加您的启动命令。在您的情况下&#xff0c;要添加的命令如下&#xff1a; sh /opt/dolphinscheduler/zookeeper/bin/zkServer.sh start sh /opt/dolphinscheduler/dolphinscheduler/…...

慢性疼痛治疗服务公司Kindly MD申请700万美元纳斯达克IPO上市

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 猛兽财经获悉,慢性疼痛治疗服务公司Kindly MD近期已向美国证券交易委员会&#xff08;SEC&#xff09;提交招股书&#xff0c;申请在纳斯达克IPO上市&#xff0c;股票代码为&#xff08;KDLY&#xff09;,Kindly MD计划通过…...

代码随想录 Day6 哈希 LeetcodeT454 四数之和II T383赎金信 T15 三数之和 T18 四数之和

本文代码思路来源于: 代码随想录 前言 希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用api,比较方便理解. LeetCode T454 四数之和 题目链接:454. 四数相加 II - 力扣&#xff08;LeetCode&#xff09; 题目思路 暴力解法仍然是遍历四个数组解决此题, 哈希的思路有…...

干货速来|教你如何撰写毕业论文

撰写毕业论文对于正常大学毕业至关重要。毕业论文是对学生在大学期间所学知识的综合运用和深入研究的体现&#xff0c;也是对学术能力和独立思考能力的考验。 撰写毕业论文的过程需要学生投入大量的时间和精力&#xff0c;包括选题、文献综述、研究方法选择、数据收集和分析、…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...

STM32 低功耗设计全攻略:PWR 模块原理 + 睡眠 / 停止 / 待机模式实战(串口 + 红外 + RTC 应用全解析)

文章目录 PWRPWR&#xff08;电源控制模块&#xff09;核心功能 电源框图上电复位和掉电复位可编程电压监测器低功耗模式模式选择睡眠模式停止模式待机模式 修改主频一、准备工作二、修改主频的核心步骤&#xff1a;宏定义配置三、程序流程&#xff1a;时钟配置函数解析四、注意…...

c++算法学习3——深度优先搜索

一、深度优先搜索的核心概念 DFS算法是一种通过递归或栈实现的"一条路走到底"的搜索策略&#xff0c;其核心思想是&#xff1a; 深度优先&#xff1a;从起点出发&#xff0c;选择一个方向探索到底&#xff0c;直到无路可走 回溯机制&#xff1a;遇到死路时返回最近…...

Linux——TCP和UDP

一、TCP协议 1.特点 TCP提供的是面向连接、可靠的、字节流服务。 2.编程流程 &#xff08;1&#xff09;服务器端的编程流程 ①socket() 方法创建套接字 ②bind()方法指定套接字使用的IP地址和端口。 ③listen()方法用来创建监听队列。 ④accept()方法处理客户端的连接…...

C++信息学竞赛中常用函数的一般用法

在C 信息学竞赛中&#xff0c;有许多常用函数能大幅提升编程效率。下面为你介绍一些常见函数及其一般用法&#xff1a; 一、比较函数 1、max()//求出a&#xff0c;b的较大值 int a10,b5,c;cmax(a,b);//得出的结果就是c等于10. 2、min()//求出a&#xff0c;b的较小值 int a1…...