首页 > 其他分享 >E. Iva & Pav

E. Iva & Pav

时间:2023-09-28 11:12:46浏览次数:41  
标签:Iva Pav int mid cin l1

E. Iva & Pav

把每一项的数拆分成32位二进制,然后求前i项第j位二进制为1的前缀和,如果区间范围内的1等于区间范围,则是可行的,乘上对应位置的大小,每一位求和判断与k的大小
二分+前缀和

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int f[N][35],a[N];

void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 32; j++) {
			f[i][j] = f[i - 1][j];
			if ((a[i] >> j) & 1) f[i][j]++;
		}
	}
	int q,l,k;
	cin >> q;
	while (q--) {
		cin >> l >> k;
		auto check = [&](int r) {
			int x=0;
			for (int i = 0; i < 32; i++) {
				int p = f[r][i] - f[l - 1][i];
				if (p == r - l + 1) x += 1 << i;
			}
			return x >= k;
		};
		int l1 = l-1 ;int r=n+1;
		while (l1 +1 < r) {
			int mid = l1 + r >> 1;
			if (check(mid)) {
				l1 = mid;
			}
			else r = mid;
		}
		if (l1 == l - 1) cout << -1 << ' ';
		else cout << l1 << ' ';
	}
	cout << '\n';
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

标签:Iva,Pav,int,mid,cin,l1
From: https://www.cnblogs.com/bu-fan/p/17734269.html

相关文章

  • [题解]CF1878E Iva & Pav
    CF是没题考了吧,每场都出二进制拆位。思路首先我们可以二分\(r\),因为\(r\)越大,按位与一定只会小于等于\(r\)小的情况。那么,我们可以用\(num_{i,j}\)记录\(a_j\)第\(i\)位的二进制情况。如果我们对\(num_{i,j}\)做一个前缀和,如果\(num_{i,r}-num_{i,l-1}=r......
  • Adobe Captivate 9.0下载(adobe屏幕录制软件)下载 各个版本下载
    AdobeCaptivate是一款综合性创作工具,可为家庭用户、学生和专业人士提供简化的电子学习创建平台,用于创建交互式教育内容,例如软件演示、分支场景、随机谜题、软件模拟等。AdobeCaptivate在创建和发布电子学习内容方面拥有超过15年的经验,如今已发展成为一个强大的创作和项目导出工......
  • Adobe Captivate 2019下载 各个版本下载
    AdobeCaptivate2019是Adobe公司出品的一款专业的屏幕录制软件,它可以轻松创建诸如应用程序模拟模型、产品演示、拖放模块以及软技能和培训内容,实现Flash格式的内容交互。软件操作简单,任何不具有编程知识或多媒体技能的人都能够快速创建功能强大的软件演示和培训内容。软件地址:......
  • java中private是什么意思
    在java中,private的意思为“私有的”,是一种访问控制修饰符,用于修饰类、属性和方法。用private修饰的类成员,只能被该类自身的方法访问和修改,而不能被任何其他类(包括该类的子类)访问和引用;因此,private修饰符具有最高的保护级别。......
  • Signature|privileged permissions not in privapp-permissions whitelist异常处理
    1、问题背景及现象背景说明:软件系统:Android10需求处理:SystemUI添加截屏录屏功能问题现象:添加完修改后无法开机SystemUI/AndroidManifest.xml部分修改如下:<!--ScreenRecording--><uses-permissionandroid:name="android.permission.FOREGROUND_SERVICE"/><uses......
  • pycharm 无法加载文件activate.ps1的原因分析及解决方法
    这篇文章主要介绍了pycharm报错提示:无法加载文件\venv\Scripts\activate.ps1,因为在此系统上禁止运行脚本,解决方法终端输入get-executionpolicy,回车返回Restricted即可,需要的朋友可以参考下 pycharm报错提示:无法加载文件\venv\Scripts\activate.ps1,因为在此系统上禁止运行脚本......
  • VIVADO VCS VERDI联合仿真
    ./tb_test.shverdi-ffilelist.f-ssf*.fsdb&......
  • 02使用vivado和Modelsim进行仿真
    软件版本:vitis2021.1(vivado2021.1)操作系统:WIN1064bit硬件平台:适用AMD-XILINXA7/K7/Z7/ZU/KU系列FPGA登录"米联客"SOC|SOC社区-www.uisrc.com视频课程、答疑解惑!1概述仿真是每个初学者必须学会的一项技能,因为FPGA程序编译时间往往很长,所以对程序进行仿真就成为了校验程序......
  • 类与继承及修饰符public 、private 、protected 的使用方法
    1.什么是类类可以理解成为一个模板,通过这个模板可以实例化某一个具体对象比如说:我们定义一个动物类,通过这个动物模板可以实例化成为猫或者其他具体的动物2.类的基本使用我们需要创建一个动物类;这个动物有姓名、【默认值小可爱,字符串类型】年龄、【默认值20,数字类型】性......
  • 笔记5-vivado IP 时钟 -单端时钟输入
     这里选MMCM进行配置    用例化来调用IP,先找到生成IP后,接口例化的地方,软件已经自动例化好,只需将下面这段拷贝到工程文件中进行调用 拷贝到led_prj.v文件中1`timescale1ns/1ps2/////////////////////////////////////////////////////////////////......