4 羚恩羊

尚未进行身份认证

我要认证

轮子搬运工

等级
TA的排名 12w+

题库随记:超快速排序

题库 18.超快速排序在这个问题中,您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理n个不同整数的序列,直到序列按升序排序。对于输入序列9 1 0 5 4,超快速排序生成输出0 1 4 5 9。您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。输入格式输入包括一些测试用例。每个测试用例的第一行输入整数n,代表该用例中输入序列的长度。接下来n行每行输入一个整数 ai ,代表用例中输入序列的具体数据,第i行的数据代表序列中第 i 个数。当输

2020-08-28 22:52:18

题库随记:动态中位数

题库 17.动态中位数依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。输入格式第一行输入一个整数 P ,代表后面数据集的个数,接下来若干行输入各个数据集。每个数据集的第一行首先输入一个代表数据集的编号的整数。然后输入一个整数 M ,代表数据集中包含数据的个数,M 一定为奇数,数据之间用空格隔开。数据集的剩余行由数据集的数据构成,每行包含10个数据,最后一行数据量可能少于10个,数据之间用空格隔开。输出格式对于每个数据集,第一行输出两个整数,分别代表数

2020-08-22 22:36:54

题库随记:货仓选址

题库 16.货仓选址在一条数轴上有 N 家商店,它们的坐标分别为 A1 ~ AN 。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。输入格式第一行输入整数 N 。第二行N个整数 A1 ~ AN 。输出格式输出一个整数,表示距离之和的最小值。数据范围1≤ N ≤100000输入样例46 2 9 1输出样例12题解核心思路即 排序+中位数中位数有非常优秀的性质,比如说在这道题目中,每一

2020-08-19 22:32:16

题库随记:最高的牛

题库 15.最高的牛题目描述有 N 头牛站成一行,被编队为1、2、3 … N ,每头牛的身高都为整数。当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。现在,我们只知道其中最高的牛是第 P 头,它的身高是 H,剩余牛的身高未知。但是,我们还知道这群牛之中存在着 M 对关系,每对关系都指明了某两头牛 A 和 B 可以相互看见。求每头牛的身高的最大可能值是多少。输入格式第一行输入整数N,P,H,M,数据用空格隔开。接下来M行,每行输出两个整数 A 和 B ,代表牛 A 和牛 B 可以相

2020-08-16 22:38:29

题库随记:奇怪的汉诺塔

题库 14.奇怪的汉诺塔汉诺塔问题,条件如下:1、这里有A、B、C和D四座塔。2、这里有n个圆盘,n的数量是恒定的。3、每个圆盘的尺寸都不相同。4、所有的圆盘在开始时都堆叠在塔A上,且圆盘尺寸从塔顶到塔底逐渐增大。5、我们需要将所有的圆盘都从塔A转移到塔D上。6、每次可以移动一个圆盘,当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时,可将圆盘移至这座塔上。请你求出将所有圆盘从塔A移动到塔D,所需的最小移动次数是多少。没有输入输出格式对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动

2020-08-11 22:47:09

题库随记:递归实现排列型枚举

题库 13.递归实现排列型枚举把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。输入格式一个整数n。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。数据范围1 ≤ n ≤ 9输入样例3输出样例1 2 31 3 22 1 32 3 13 1 23 2 1题解代码如下:#include <bits/stdc++.h>using n

2020-08-08 23:06:12

题库随记:递归实现组合型枚举

题库 12.递归实现组合型枚举从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。输入格式两个整数 n,m,在同一行用空格隔开。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的数升序排列,相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如1 3 5 7排在1 3 6 8前面)。数据范围n > 0,0 ≤ m ≤ n,n + (n − m) ≤ 25输入样例5 3输出样例1 2 31 2

2020-08-06 23:30:21

题库随记:递归实现指数型枚举

题库 11.递归实现指数型枚举从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。输入格式输入一个整数n。输出格式每行输出一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,输出空行。本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。数据范围1≤ n ≤15输入样例3输出样例322 311 31 21 2 3题解位运算+递归深度优先搜索代码如下:#include <bits/stdc++.h

2020-08-04 23:41:55

题库随记:最短Hamilton路径

题库 10.最短Hamilton路径给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。输入格式第一行输入整数n。接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i, j])。对于任意的x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。输出格式输出一个整数,

2020-08-01 22:13:05

题库随记:64位整数乘法

题库 9.64位整数乘法求 a 的 b 次方对 p 取模的值。输入格式第一行输入整数 a,第二行输入整数 b,第三行输入整数 p。输出格式输出一个整数,表示a*b mod p的值。数据范围0≤a,b,p≤108输入样例345输出样例2题解(二进制思想) O(logn)如果直接计算a乘b这会超过 long long 的最大范围,所以采用类似于快速幂的思想:把 b 写成二进制形式,然后如果某位上为 1 就加上它a * (2n) 次方(n与这位的位置有关)并且每次计算后取模就可以了

2020-07-31 22:58:48

题库随记:a^b

题库 8.a^b求 a 的 b 次方对 p 取模的值。输入格式三个整数 a,b,p, 在同一行用空格隔开。输出格式输出一个整数,表示a^b mod p的值。数据范围0≤a,b,p≤109数据保证 p ≠ 0输入样例3 2 7输出样例2题解表面AC实质是一道数论题数论题数论题(重要的事情说3遍QAQ )考虑到题目测试样例过于巨大(奇葩),因此暴力AC会TLE,需要快速幂的介入,因此,a^n 中的 n 用二进制数表示方法如下:f[c]=1;c++;f[c]=a%p;c++;fo

2020-07-29 22:27:03

标定算法记录:激光和Gnss融合的外参标定

记录目录1.lidar_align功能包1.1安装1.2输入里程记信息1.3外参估计程序(Estimation proceedure)1.4 可视化结果2.标定原理3.标定显示3.1外参显示3.2标定结果1.lidar_align功能包一种寻找三维激光雷达与六自由度姿态传感器外部标定的简单方法,开源链接点此。该工具来自瑞士苏黎世联邦理工大学的自动驾驶实验室。其实验室对imu与其他传感器融合传感定位建图的理论及项目研究处于世界领先水平,其代表作还包括摄像头与imu融合传感的OKVIS、ROVIO。此次l

2020-07-26 22:41:50

题库随记:找出数组中重复的数字

题库 7.找出数组中重复的数字给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。注意:如果某些数字不在 0∼n−1的范围内,或数组中不包含重复数字,则返回 -1;样例给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。题解(数组遍历) O(n)算法的主要思想是把每个数放到对应的位置上,即让nums[i] = i。

2020-07-25 22:32:58

题库随记:多重背包问题III

题库 5.多重背包问题III有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V ,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数,表示最大价值。数据范围0< N ≤ 10000< V ≤ 2

2020-07-23 22:50:29

题库随记:多重背包问题II

题库 4.多重背包问题II有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V ,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数,表示最大价值。数据范围0< N ≤10000< V ≤2000

2020-07-21 22:14:18

题库随记:多重背包问题 I

题库 4.多重背包问题I有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V ,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。输出格式输出一个整数,表示最大价值。数据范围0<N,V ≤1000<vi,wi, si

2020-07-20 22:56:07

题库随记:完全背包问题

题库 3.完全背包问题有 N 件物品和一个容量是 V 的背包。每件物品都有无限件可用。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 vi, wi,用空格隔开,分别表示第 i 件物品的体积和价值。输出格式输出一个整数,表示最大价值。数据范围0<N, V ≤10000<vi, wi ≤100

2020-07-18 22:48:26

题库随记:01背包问题

题库 2.背包问题有 N 件物品和一个容量是 ***V***的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 vi, wi,用空格隔开,分别表示第 i件物品的体积和价值。输出格式输出一个整数,表示最大价值。数据范围0<N, V ≤10000<vi, wi ≤10

2020-07-16 22:57:12

题库随记: A + B

题库 1. A + B输入两个整数,求这两个整数的和是多少。输入格式输入两个整数A,B,用空格隔开,0≤A,B≤108输出格式输出一个整数,表示这两个数的和样例输入:3 4样例输出:7算法(模拟) O(1)C++ 样例代码如下:#include <iostream>using namespace std;int main () { int a, b; cin >> a >> b; cout << a +

2020-07-14 22:23:12

TCP协议的三次握手和四次分手

通俗白话之TCP三握四挥通俗理解:引用的一些通俗易懂的例子,虽然不太正确,后面会指出,但是不妨碍我们理解,大体就是这么个理解法。第一次对话:老婆让甲出去打酱油,半路碰到一个朋友乙,甲问了一句:哥们你吃饭了么?结果乙带着耳机听歌呢,根本没听到,没反应。甲心里想:跟你说话也没个音,不跟你说了,沟通失败。说明乙接受不到甲传过来的信息的情况下沟通肯定是失败的。如果乙听到了甲说的话,那么第一次对话成功,接下来进行第二次对话。第二次对话:乙听到了甲说的话,但是他是老外,中文不好,不知道甲说的啥意

2020-07-13 22:32:23

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。