蓝桥杯练习系统(算法训练)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;
} 

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/590353.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

力扣hot100:101. 对称二叉树(双指针以不同方式递归)

LeetCode&#xff1a;101. 对称二叉树 看了第一个样例&#xff0c;很容易直接层序遍历看每一层的前后是否相同。但接下来这个样例告诉你&#xff0c;不能这样做。 层序遍历 仔细思考会发现&#xff0c;层序遍历不能看本结点&#xff0c;但是可以看儿子结点是否对称&#xf…

RK3568平台(时间篇)看门狗

一.看门狗原理 在产品化的嵌入式系统中&#xff0c;为了使系统在异常情况下能自动复位&#xff0c;一般都需要引入看门狗。 看门狗其实就是一个可以在一定时间内被复位的计数器。当看门狗启动后&#xff0c;计数器开始自动计数&#xff0c;经过一定时间&#xff0c;如果没有被…

笔记-mathtype公式在PDF或打印出来显示不全

原文中的公式&#xff1a; 纸质版打印出来的公式有缺失 问题描述&#xff1a;mathtype公式编辑器所编辑的公式转成PDF或者打印出来有缺失 以下是解决方法的具体描述。 目录 一、准备工作二、操作步骤 一、准备工作 1、工具&#xff1a;mathtype、微软word 二、操作步骤 …

概念解析 | 互补学习系统

注1:本文系"概念解析"系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:互补学习系统(Complementary Learning Systems) 概念解析:互补学习系统 Paper Summary - “Complementary Learning Systems Theory Updated” | Rylan Schaeffer…

Linux下Palabos源码编译安装及使用

目录 软件介绍 基本依赖 其它可选依赖 一、源码下载 二、解压缩&#xff08;通过方式1下载源码.zip格式&#xff09; 三、编译安装 3.1 自带算例 ​编辑3.2 自行开发算例 四、简单使用 4.1 串行运行 4.2 并行运行 4.3 查看结果 软件介绍 Palabos是一款基于LBM&…

前端面试和一些建议

最近公司在招前端&#xff0c;我有跟着一起参与面试。我们主要负责面试的人&#xff0c;不会问那些什么闭包&#xff0c;原型链&#xff0c;他觉得那些东西在我们日常开发中用不到&#xff0c;问的基本都是一些工作中的问题。这些问题不是每次都问&#xff0c;但也就问这些了。…

[论文阅读] 测试时间自适应TTA

最初接触 CVPR2024 TEA: Test-time Energy Adaptation [B站]&#xff08;1:35:00-1:53:00&#xff09;https://www.bilibili.com/video/BV1wx4y1v7Jb/?spm_id_from333.788&vd_source145b0308ef7fee4449f12e1adb7b9de2 实现&#xff1a; 读取预训练好的模型参数设计需要更…

C语言写一个终端进度条

C语言写一个终端进度条 这个功能挺简单的&#xff0c;主要有以下两点&#xff1a; 如何获取终端宽度如何让字符在原地闪烁 如何获取终端宽度 这里用到了设备控制接口函数ioctl()&#xff0c;下面简单的介绍一下这个函数的用法&#xff1a; ioctl是一个在Unix和类Unix系统中…

怎样通过Java语言实现远程控制8路控制器/断路器

怎样通过Java语言实现远程控制8路控制器/断路器呢&#xff1f; 本文描述了使用Java语言调用HTTP接口&#xff0c;实现控制8路控制器/断路器&#xff0c;支持8路输出&#xff0c;均可独立控制&#xff0c;可接入各种电器。 可选用产品&#xff1a;可根据实际场景需求&#xff0…

【数据库主从架构】

【数据库主从架构】 1. 什么是数据库的主从架构1.1 主从复制1.1.1 MySQL的主从主从复制技术三级目录 1. 什么是数据库的主从架构 随着公司业务线的增多&#xff0c;各种数据都在迅速增加&#xff0c;并且数据的读取流量也大大增加&#xff0c;就面临着数据安全问题&#xff0c;…

手把手教你实现通讯录

整体构思 我们现在要实现一个通讯录 它应该有以下的功能 通讯录可以用来存储1000个人的信息&#xff0c;每个人的信息包括&#xff1a;姓名、性别、年龄、电话、住址 提供方法&#xff1a; 1.添加联系人信息 2.删除指定联系人信息 3.查找指定联系人信息 4.修改指定联系人信…

如何删除BigKey2

例2&#xff1a;假如有hash类型的key&#xff0c;其中有100万对field和value&#xff0c;field是自增id&#xff0c;这个key存在什么问题&#xff1f;如何优化&#xff1f; keyfieldvaluesomeKeyid:0value0..........id:999999value999999 存在的问题&#xff1a; hash的ent…

BJFUOJ-C++程序设计-实验2-类与对象

A 评分程序 答案&#xff1a; #include<iostream> #include<cstring>using namespace std;class Score{ private:string name;//记录学生姓名double s[4];//存储4次成绩&#xff0c;s[0]和s[1]存储2次随堂考试&#xff0c;s[2]存储期中考试&#xff0c;s[3]存储期…

机器学习:深入解析SVM的核心概念【二、对偶问题】

对偶问题 **问题一&#xff1a;什么叫做凸二次优化问题&#xff1f;而且为什么符合凸二次优化问题&#xff1f;**为什么约束条件也是凸的半空间&#xff08;Half-Space&#xff09;凸集&#xff08;Convex Set&#xff09;半空间是凸集的例子SVM 约束定义的半空间总结 **问题二…

使用Colab的高RAM模式

使用Colab的高RAM模式 colab需要升级为pro或者pro会员 1. 购买pro 图片来源&#xff1a;https://blog.csdn.net/javastart/article/details/138094086 2. 打开高RAM模式 要在Colab上使用高RAM模式来运行模型计算&#xff0c;您需要按照以下步骤操作&#xff1a; 打开您的…

Deep Learning Part Five RNNLM的学习和评价-24.4.30

准备好RNNLM所需要的层&#xff0c;我们现在来实现RNNLM&#xff0c;并对其进行训练&#xff0c;然后再评价一下它的结果的。 5.5.1 RNNLM的实现 这里我们将RNNLM使用的网络实现为SimpleRnnlm类&#xff0c;其层结构如下&#xff1a; 如图 5-30 所示&#xff0c;SimpleRnnlm …

调教AI给我写了一个KD树的算法

我不擅长C&#xff0c;但是目前需要用C写一个KD树的算法。首先我有一份点云数据&#xff0c;需要找给定坐标范围0.1mm内的所有点。 于是我开始问AI&#xff0c;他一开始给的答案&#xff0c;完全是错误的&#xff0c;但是我一步步给出反馈&#xff0c;告诉他的问题&#xff0c;…

基于Springboot的交流互动系统

基于SpringbootVue的交流互动系统的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringbootMybatis工具&#xff1a;IDEA、Maven、Navicat 系统展示 用户登录 首页 帖子信息 聚会信息 后台登录 后台管理首页 用户管理 帖子分类管理 帖子信息…

【模板】二维前缀和

原题链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 二维前缀和板题。 二维前缀和&#xff1a;pre[i][j]a[i][j]pre[i-1][j]pre[i][j-1]-pre[i-1][j-1]; 子矩阵 左上角为(x1,y1) 右下角(x2,y2…

自然语言处理基础

文章目录 一、基础与应用简单介绍基本任务重要应用 二、词表示与语言模型词表示方案一&#xff1a;用一组的相关词来表示当前词方案二&#xff1a;one-hot representation&#xff0c;将每一个词表示成一个独立的符号方案三&#xff1a;上下文表示法&#xff08;contextual rep…