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

CF1692G 2^Sort 题解

CF1692G 2^Sort 题解

  • 题目
    • 链接
    • 字面描述
      • 题面翻译
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例 #1
        • 样例输入 #1
      • 样例输出 #1
    • 提示
  • 思路
  • 代码实现

题目

链接

https://www.luogu.com.cn/problem/CF1692G

字面描述

题面翻译

给你一个长度为 n(∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (n<2105) 的数组 aaa,问你在这个数组中,有多少个长度为 k+1(1≤k<n)k + 1 \ (1\le k < n)k+1 (1k<n) 的区间,符合以下的条件:

20⋅ai<21⋅ai+1<22⋅ai+2<⁣⋯<2k⋅ai+k注:i为这个区间开始的位置2^0 \cdot a_i < 2^1 \cdot a_{i + 1} < 2^2 \cdot a_{i + 2} < \dotsi < 2^k \cdot a_{i + k}\\ \footnotesize{注:i 为这个区间开始的位置} 20ai<21ai+1<22ai+2<<2kai+k注:i为这个区间开始的位置

由tzyt翻译

题目描述

Given an array $ a $ of length $ n $ and an integer $ k $ , find the number of indices $ 1 \leq i \leq n - k $ such that the subarray $ [a_i, \dots, a_{i+k}] $ with length $ k+1 $ (not with length $ k $ ) has the following property:

  • If you multiply the first element by $ 2^0 $ , the second element by $ 2^1 $ , …, and the ( $ k+1 $ )-st element by $ 2^k $ , then this subarray is sorted in strictly increasing order.

More formally, count the number of indices $ 1 \leq i \leq n - k $ such that $ $KaTeX parse error: Can't use function '$' in math mode at position 84: …\cdot a_{i+k}. $̲ $

输入格式

The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ , $ k $ ( $ 3 \leq n \leq 2 \cdot 10^5 $ , $ 1 \leq k < n $ ) — the length of the array and the number of inequalities.

The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the elements of the array.

The sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the number of indices satisfying the condition in the statement.

样例 #1

样例输入 #1

6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12

样例输出 #1

2
3
2
3
1
0

提示

In the first test case, both subarrays satisfy the condition:

  • $ i=1 $ : the subarray $ [a_1,a_2,a_3] = [20,22,19] $ , and $ 1 \cdot 20 < 2 \cdot 22 < 4 \cdot 19 $ .
  • $ i=2 $ : the subarray $ [a_2,a_3,a_4] = [22,19,84] $ , and $ 1 \cdot 22 < 2 \cdot 19 < 4 \cdot 84 $ .

In the second test case, three subarrays satisfy the condition: - $ i=1 $ : the subarray $ [a_1,a_2] = [9,5] $ , and $ 1 \cdot 9 < 2 \cdot 5 $ .

  • $ i=2 $ : the subarray $ [a_2,a_3] = [5,3] $ , and $ 1 \cdot 5 < 2 \cdot 3 $ .
  • $ i=3 $ : the subarray $ [a_3,a_4] = [3,2] $ , and $ 1 \cdot 3 < 2 \cdot 2 $ .
  • $ i=4 $ : the subarray $ [a_4,a_5] = [2,1] $ , but $ 1 \cdot 2 = 2 \cdot 1 $ , so this subarray doesn’t satisfy the condition.

思路

对原数组进行模拟下标x(2n)x(2~n)x(2 n)
根据题目
ax−1<2⋅axa_{x-1}<2\cdot a_xax1<2ax
∴fx=1\therefore f_x=1fx=1
否则,fx=0f_x=0fx=0

f数组f数组f数组进行前缀和预处理,就可以实现O(n)\Omicron(n)O(n)时间复杂度的统计了。

代码实现

#include<bits/stdc++.h>
using namespace std;const int maxn=2e5+10;
int t,n,k,ans;
int a[maxn],f[maxn];
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);int op=0;ans=0;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){int x;scanf("%d",&x);if(2*x>op)a[i]=1;op=x;}for(int i=1;i<=n;i++){f[i]=f[i-1]+a[i];if(i-k-1<0)continue;if(f[i]-f[i-k]==k)++ans;}printf("%d\n",ans);}return 0;
} 

相关文章:

CF1692G 2^Sort 题解

CF1692G 2^Sort 题解题目链接字面描述题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码实现题目 链接 https://www.luogu.com.cn/problem/CF1692G 字面描述 题面翻译 给你一个长度为 n(∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (∑n<…...

关于物理像素,逻辑像素,像素比

关于物理像素、逻辑像素&#xff08;css像素&#xff09;、分辨率、像素比的超详细讲解 在日常生活中&#xff0c;有这样一个问题。同样的图片为什么在不同的设备上显示的大小是不一样的。&#x1f912;带着这个问题来说明一下。 一、物理像素 设备刚生产出来就已经固定了&a…...

JavaSE基础部分总结

JavaSe基础部分 文章目录JavaSe基础部分1.命名规范2.基本的数据类型3.方法3.1方法的基本格式3.2 方法的分类3.3 方法的注释4.数组4.1 数组的命名格式4.2 数组中存在的址交换的操作4.3数组Arrays常用的方法1. Arrays.asList(数组作为参数或者数据作为参数)&#xff1a;2.Arrays.…...

C++基础知识

目录类和对象C static_cast、dynamic_cast、const_cast和reinterpret_cast1、为什么要引入这四种类型转化&#xff1f;2、应用场景。C/C类型转换的本质struct和class的区别为什么会诞生面向对象的编程思想析构函数的执行时机初始化 const 成员变量C const对象&#xff08;常对象…...

2023/2/24 图数据库Neo4j的理解与应用

1 什么是图数据库&#xff08;graph database&#xff09; 十大应用案例&#xff1a;https://go.neo4j.com/rs/710-RRC-335/images/Neo4j-Top-Use-Cases-ZH.pdf “大数据”每年都在增长&#xff0c;但如今的企业领导者不仅需要管理更大规模的数据&#xff0c;还迫切需要从现有…...

适合视力障碍者的Linux

导读有哪些最适合视障用户的 Linux 发行版&#xff1f;让我们一起来看看。 如果有人视力障碍或失明&#xff0c;他们可能会依赖声音提示或其他交互方式&#xff08;如盲文&#xff09;来阅读和交流。 他们怎样才能使用 Linux 发行版&#xff1f; 嗯&#xff0c;一般来说&…...

Tina Linux 存储开发指南

Tina Linux 存储开发指南 1 概述 1.1 编写目的 介绍TinaLinux Flash&#xff0c;分区&#xff0c;文件系统等存储相关信息&#xff0c;指导方案的开发定制。 1.2 适用范围 Tina V3.0 及其后续版本。 1.3 相关人员 适用于TinaLinux 平台的客户及相关技术人员。 2 分区管…...

【洛谷 P2670】[NOIP2015 普及组] 扫雷游戏 题解(模拟)

[NOIP2015 普及组] 扫雷游戏 题目背景 NOIP2015 普及组 T2 题目描述 扫雷游戏是一款十分经典的单机小游戏。在 nnn 行 mmm 列的雷区中有一些格子含有地雷&#xff08;称之为地雷格&#xff09;&#xff0c;其他格子不含地雷&#xff08;称之为非地雷格&#xff09;。玩家翻…...

【nohup引发磁盘读写高】nohup命令导致服务器磁盘读写占满该如何修复?

【写在前面】自己在跑一个项目的时候&#xff0c;猛然发现服务器挂了&#xff0c;直接访问不了&#xff0c;呈现出一种卡死现象&#xff0c;我当时都懵了&#xff0c;难道阿里在后端升级&#xff0c;也不会选择在工作日的时间升级吧&#xff0c;于是乎就咨询了一下客服。才有下…...

MySQL(二)索引和SQL优化

MySQL进阶MySQL体系结构存储引擎存储引擎特点InnoDB逻辑存储结构MyISAMMemory存储引擎选择索引索引结构二叉树B-TreeBTreeHash索引分类索引语法SQL性能分析工具SQL执行频率慢查询日志profile详情explain索引使用联合索引索引失效情况SQL提示覆盖索引前缀索引单列索引与联合索引…...

Java常用日期类(包含三代)_Date类及Calendar类等

一.java.util.Date类概述从JDK 1.0出现。表示一个日期和时间&#xff0c;精确到毫秒&#xff0c;内部getTime()从1970年1月1号开始算。1. java.util.Date类构造部份构造已经过时&#xff0c;重点看以下两个构造。public Date()从运行程序的此时此刻到时间原点经历的毫秒值&…...

计算机网络你都懂了吗

文章目录一、计算机网络的定义简单定义通用定义二、计算机网络通信过程三、什么是网络协议&#xff08;Protocol&#xff09;四、网络协议组成及功能一、计算机网络的定义 简单定义 计算机网络是一些相互连接的、自治的计算机系统的集合。 通用定义 将处于不同位置并具有独…...

3.4 Spring Boot 日志配置

第3章 Spring Boot 的系统配置 3.1 Spring Boot 系统配置文件 3.2 Spring Boot 自定义配置项 3.3 Spring Boot 其他配置 3.4 Spring Boot 日志配置 3.5 实战&#xff1a;Spring Boot 实现系统多环境配置 3.4 Spring Boot 日志配置 日志对于系统监控、故障定位非常重要&#xf…...

3款百里挑一的国产软件,逆天好用,装了就舍不得卸载

推荐3款让你偷懒&#xff0c;让你上头的提效电脑软件&#xff0c;个个功能强大&#xff0c;让你远离加班&#xff01; 很多几个小时才能做好的事情&#xff0c;用上它们&#xff0c;只需要5分钟就行&#xff01;&#xff01; 1、JNPF快速开发平台 JNPF 是一款精巧耐用的软件…...

Java实现在线沟通功能

文章目录1、介绍 和 特点2、整合SpringBoot2.1、导入依赖2.2、websocket 配置类2.3、消息处理类2.4、启动服务2.5、前端代码&#xff1a;张三2.6、前端代码&#xff1a;李四3、效果4、小结1、介绍 和 特点 t-io是基于JVM的网络编程框架&#xff0c;和netty属同类&#xff0c;所…...

识别密文加密类型

离线密码破解&#xff1a;离线不会触发密码锁定机制不会产生大量登录失败日志引起管理员注意HASH识别工具&#xff08;识别哈希类型&#xff09;&#xff1a;hash-identifierHashid yara规则匹配文件得到特定加密算法一、hash-identifierKali Linux提供工具hash-identifier来识…...

node报错

记录bug:运行 npx -p storybook/cli sb init 时报错gyp info spawn C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Current\Bin\MSBuild.exegyp info spawn args [gyp info spawn args build/binding.sln,gyp info spawn args /nologo,gyp info spawn args…...

如何使用开源 BI 工具 DataEase 实现系列数据分析呢?

当我们使用可视化分析工具制作仪表板时&#xff0c;可能需要制作的仪表板不是单个单个的可视化大屏&#xff0c;而是一系列的仪表板&#xff0c;我们需要用它来产生一个连续性的故事&#xff0c;那么这个时候我们该怎么办呢&#xff1f;例如说总分形式&#xff0c;我们需要一个…...

金仓数据库安装

一、麒麟操作系统安装金仓数据库 操作系统 DISTRIB_IDKylin DISTRIB_RELEASEV10 DISTRIB_CODENAMEjuniper 按照安装文档的步骤安装&#xff0c;记得记住设置的数据库的用户名、密码 二、window安装连接数据库的工具软件 三、jdbc连接数据库 &#xff08;1&#xff09;连接工…...

深入浅出Webpack2-快速掌握webpack基本配置

深入浅出Webpack2-快速掌握webpack基本配置1.Entry1.1 context1.2 Entry类型2.Output2.1 filename2.2 path3.Module3.1配置Loader4.Resolve4.1 alias4.2 extensions4.3 modules5.Plugin6.DevServer7.其他配置项上一篇文章我们快速上手认识了一下webpack&#xff0c;今天这篇文章…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...