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

蓝桥杯练习系统(算法训练)ALGO-950 逆序数奇偶

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  老虎moreD是一个勤于思考的青年,线性代数行列式时,其定义中提到了逆序数这一概念。不过众所周知我们只需要知道逆序数的奇偶性就行了,为了防止计算上的失误,moreD准备编写一个小程序来判定。只要判断奇偶性就行了哦!
  另外作为一个技术宅,moreD对线性代数中最小下标为1非常不满,于是所有下标均从0开始。

输入格式

  一个测试点包含多组数据,你需要不断读入直到输入结束。
  每组数据第一行为一个n,接下来第二行输入n个数字,是一个0到n-1的排列。

输出格式

  输出若干行,每行表示对应组数据逆序数奇偶性,奇数输出odd,偶数输出even。

样例输入

5
0 1 2 3 4
5
4 3 1 2 0

样例输出

even
odd

数据规模和约定

  设每组测试点T个数据
  1<=T<=10
  1<=n<=100000

首先看暴力方法,超时(仅供理解题意):

4 3 1 2 0,求逆序数的方法:

  • 对于第1个数字4,前面没有比它大的数,逆序数为0
  • 对于3,前面有比它大的数字4,逆序数为1
  • 对于1,前面有4,3,都比它大,逆序数为2
  • 对于2 ,前面有4,3,1,两个比它大,逆序数为2
  • 对于0,前面有4,3,1,2,都比它大,逆序数为4

因此,该序列的逆序数=0+1+2+2+4=9,为odd

#include<iostream>
using namespace std;int main(){int n;while(cin>>n){int a[n];for(int i=0;i<n;i++){cin>>a[i];}long long int sum=0;for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(a[j]>a[i]) sum++;}}if(sum%2==0) cout<<"even"<<endl;else cout<<"odd"<<endl;}return 0;
}

归并算法

#include<iostream>
using namespace std;
const int N=100005;
int a[N];//待排序的数组
int tmp[N];
int res=0;void msort(int l,int r){if(l==r) return;//只有一个数 int mid=(l+r)>>1;msort(l,mid);msort(mid+1,r);//合并 int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]<=a[j]) tmp[k++]=a[i++];else{tmp[k++]=a[j++];res+=mid-i+1;}} while(i<=mid) tmp[k++]=a[i++];while(j<=r) tmp[k++]=a[j++];for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main(){int n;while(cin>>n){res=0;for(int i=0;i<n;i++){cin>>a[i]; }msort(0,n-1);if(res%2==0) cout<<"even"<<endl;else cout<<"odd"<<endl;}return 0;
} 

思路:归并算法。在右段取数时,计算逆序数,即取右段中的数时,该数的逆序数为左段中比它大的数。 

相关文章:

蓝桥杯练习系统(算法训练)ALGO-950 逆序数奇偶

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 老虎moreD是一个勤于思考的青年&#xff0c;线性代数行列式时&#xff0c;其定义中提到了逆序数这一概念。不过众所周知我们…...

uniapp踩坑 uni.showToast 和 uni.showLoading

uniapp踩坑 uni.showToast 和 uni.showLoading 一、问题描述 uni.showLoading 和 uni.showToast 混合使用时&#xff0c;showLoading和showToast会相互覆盖对方&#xff0c;调用hideLoading时也会将toast内容进行隐藏。 二、触发条件 1.uniapp中使用自己封装的axois&#x…...

BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION合集

&#xff08;BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION&#xff09;时&#xff0c;我们可以从它们的基本结构、工作原理、应用场景以及优缺点等方面进行详细介绍和分析。 BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU等&#xff08;matlab…...

通过 Java 操作 redis -- 基本通用命令

目录 使用 String 类型的 get 和 set 方法 使用通用命令 exists &#xff0c;del 使用通用命令 keys 使用通用命令 expire,ttl 使用通用命令 type 要想通过 Java 操作 redis&#xff0c;首先要连接上 redis 服务器&#xff0c;推荐看通过 Java 操作 redis -- 连接 redis 关…...

Jenkins集成Kubernetes 部署springboot项目

文章目录 准备部署的yml文件Harbor私服配置测试使用效果Jenkins远程调用参考文章 准备部署的yml文件 apiVersion: apps/v1 kind: Deployment metadata:namespace: testname: pipelinelabels:app: pipeline spec:replicas: 2selector:matchLabels:app: pipelinetemplate:metada…...

个股期权是什么期权?个股期权什么时候推出?

今天期权懂带你了解个股期权是什么期权&#xff1f;个股期权什么时候推出&#xff1f;期权也称选择权&#xff0c;是指期权的买方有权在约定的期限内&#xff0c;按照事先确定的价格&#xff0c;买入或卖出一定数量某种特定商品或金融指标的权利。 个股期权是什么期权&#xff…...

TCP UDP

传输层 端口号 tcp udp 网络层 IP地址 IP TCP&#xff0c;UDP 1&#xff0c;TCP是面向链接的协议&#xff0c;而UDP是无连接的协议; 2&#xff0c;TCP协议的传输是可靠的&#xff0c;而UDP协议的传输“尽力而为” 3&#xff0c;TCP可以实现流控&#xff0c;但UDP不行;…...

PCIE协议-1

1. PCIe结构拓扑 一个结构由点对点的链路组成&#xff0c;这些链路将一组组件互相连接 - 图1-2展示了一个结构拓扑示例。该图展示了一个称为层级结构的单一结构实例&#xff0c;由一个根复合体&#xff08;Root Complex, RC&#xff09;、多个端点&#xff08;I/O设备&#xf…...

[C++][PCL]pcl安装包预编译包国内源下载地址

版本名称下载地址PCL-1.14.1-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.14.0-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.13.1-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.13.0-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.12.1-AllInOne-msvc2019-win64含…...

海洋行业工业气体检测传感器的重要性

海洋行业是一个广阔而复杂的领域&#xff0c;涉及多个分支和应用&#xff0c;包括浮式生产、储存和卸载&#xff08;FPSO&#xff09;装置、渡轮和潜艇等。这些船舶和设施在执行任务时&#xff0c;都可能遇到各种潜在的气体危害。因此&#xff0c;对于海洋行业来说&#xff0c;…...

免费在线录屏、无需注册、免费可用、无限制

免费在线工具 https://orcc.online/ 在线录屏 https://orcc.online/recorder pdf在线免费转word文档 https://orcc.online/pdf 时间戳转换 https://orcc.online/timestamp Base64 编码解码 https://orcc.online/base64 URL 编码解码 https://orcc.online/url Hash(MD5/SHA…...

5V升9V2A升压恒压WT3231

5V升9V2A升压恒压WT3231 WT3231&#xff0c;一款性能卓越的DC-DC转换器&#xff0c;采用了集成10A、26mΩ功率的MOSFET电源开关转换器。它能够输出高达12V的电压&#xff0c;稳定可靠。这款产品以固定的600KHz运行&#xff0c;因此可以使用小型的外部感应器和电容器&#xff0…...

Java中枚举类的使用详解

Java中枚举类的使用详解 在Java编程中&#xff0c;枚举&#xff08;Enum&#xff09;是一种特殊的类&#xff0c;用于表示固定数量的常量。与常量相比&#xff0c;枚举类型具有类型安全、可读性强和易于管理的优点。下面我们将详细讲解Java中枚举类的使用&#xff0c;并通过示…...

C++11 设计模式6. 建造者模式,也叫做生成器模式

一 什么是建造者模式&#xff1f; // 小木公司对于SQL有配置&#xff0c;因此要输入sql url&#xff0c;然后输入 sql username&#xff0c;然后是 sql ps //因此小木就想到了使用 SystemConfig这个类来完成上述的三个初始化 //5.1号小木公司加入了redis的缓存机制&#xff0…...

GPS与精致农业 无人机应用 农业遥感 农业类

全球定位系统是美国国防部主要为满足军事部门对海上、陆地和空中设施进行高精度导航和定位的要求而建立的。GPS系统最基本的特点是以“多星、高轨、高频、测量-测距”为体制&#xff0c;以高精度的原子钟为核心。GPS作为新一代卫星导航与定位系统&#xff0c;不仅具有全球性、全…...

Kotlin注解简介

Kotlin注解 注解&#xff08;Annotations&#xff09;在 Kotlin 中和在 Java 中有类似的地位&#xff0c;它们都是元数据的形式&#xff0c;为代码提供了额外的信息。注解不会直接影响代码的操作&#xff0c;但可以被编译器或者运行时环境用来生成额外的代码、进行类型检查、处…...

代码随想录训练营

Day45代码随想录 322.零钱兑换 1.题目描述 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -…...

java中的变量、数据类型、人机交互

变量 变量要素 1、类型&#xff1b;每一个变量都需要定义类型&#xff08;强类型&#xff09;其它语言有弱类型&#xff08;js&#xff09; 2、变量名&#xff1b; 3、存储的值&#xff1b; 声明方式&#xff1a; 数据类型 变量名 变量值&#xff1b; public static vo…...

Python中的生成器是什么

生成器的工作原理 只要Python函数的主体中有yield关键字,该函数就是生成器函数。调用生成器函数,返回一个生成器对象。也就是说,生成器函数是生成器工厂。 下面以一个简单的函数说明生成器的行为: def gen123():yield 1yield 2yield 3print(gen123) # <function gen…...

【Camera2完整流程分析四】从log角度分析CameraService启动流程

下面直接带你通过log打印来一起读CameraService启动的过程。 1)Camera service对象构建,在启动的时候先创建CameraService 这里会打印: CameraService: CameraService started (pid=559)接着启动的时候会执行 –》onFirstRef() 进入这里面看,先输出打印: CameraService:…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

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

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

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Bean 作用域有哪些?如何答出技术深度?

导语&#xff1a; Spring 面试绕不开 Bean 的作用域问题&#xff0c;这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开&#xff0c;结合典型面试题及实战场景&#xff0c;帮你厘清重点&#xff0c;打破模板式回答&#xff0c…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...