当前位置: 首页 > 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:…...

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

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

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...