- 博客(246)
- 收藏
- 关注
RSS订阅
原创 北航2021年复试机试第二题
2. 机场登机口调整模拟【问题描述】假设某机场所有登机口（Gate）呈树形排列（树的度为3），安检处为树的根，如下图所示。图中的分叉结点（编号大于等于100）表示分叉路口，登机口用小于100的编号表示（其一定是一个叶结点）。通过对机场所有出发航班的日志分析，得知每个登机口每天的平均发送旅客流量。作为提升机场服务水平的一个措施，在不改变所有航班相对关系的情况下（即：出发时间不变，原在同一登机口的航班不变），仅改变登机口（例如：将3号登机口改到5号登机口的位置），使得整体旅客到登机口的时间有所减少（即：从安
2021-03-31 14:23:24
2167
2
原创 北航2021年复试机试第一题
【问题描述】在操作系统中，空闲存储空间通常以空闲块链表方式组织，每个块包含块起始位置、块长度及一个指向下一块的指针。空闲块按照存储位置升序组织，最后一块指向第一块（构成循环链表）。当有空间申请请求时，按照如下原则在空闲块循环链表中寻找并分配空闲块：1）从当前位置开始遍历空闲块链表（初始是从地址最小的第一个空闲块开始），寻找满足条件的最小块（即：大于等于请求空间的最小空闲块，如果有多个大小相同的最小空闲块，则选择遍历遇到的第一个空闲块）（最佳适应原则）；2）如果选择的空闲块恰好与请求的大小相符合，则将它
2021-03-31 08:51:01
2840
4
原创 Codeup100000584问题 C: To Fill or Not to Fill
Codeup100000584问题 C: To Fill or Not to Fill题目描述：With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas stat
2020-06-14 10:44:34
112
原创 大数据排序（10亿量级以上）C语言实现
大数据排序（10亿量级以上）C语言实现我们平常对数据进行排序一般用内部方法，即八大排序方法：直接插入排序冒泡排序希尔排序堆排序归并排序堆排序快速排序基数排序这些排序方法默认你们已经掌握了，如果不了解可以在网上搜一下首先给出设计的大纲，一共分三步：先生成10亿随机数数据将10亿数据分成n个小文件并进行排序最后将n个小文件进行归并这里可能大家就会有疑问了，为什么要...
2019-11-23 17:22:37
3518
原创 Codeup100000636问题 D: 数列-训练套题T10T3
题目描述：一个简单的数列问题：给定一个长度为n的数列，求这样的三个元素ai,aj,aka_i, a_j, a_kai,aj,ak的个数，满足ai<aj>aka_i < a_j > a_kai<aj>ak，且i<j<ki < j < ki<j<k。输入：第一行是一个整数n(n≤50000)n(n \le 50000)n(n≤50000)。第二行n个整数ai(0≤ai≤32767)a_i(0 \le a_i \le 32
2021-08-04 19:52:19
327
原创 Codeup100000636问题 C: Count Inversions
题目描述：给一个数组，算inverted pair的数目输入：有多组测试样例。每组输入数据占一行，每一行是一个数组，数组之间的元素用空格分开输出：每组输出结果占一行。对应于每组输入数据的inversions样例输入：1 2 32 1 33 2 1样例输出：013实现代码：#include<cstdio>#include<cstring>#include<string>#include<iostream>#include
2021-08-04 19:48:17
190
原创 Codeup100000636问题 B: 区间查询
题目描述：食堂有N个打饭窗口，现在正到了午饭时间，每个窗口都排了很多的学生，而且每个窗口排队的人数在不断的变化。现在问你第i个窗口到第j个窗口一共有多少人在排队？输入：输入的第一行是一个整数T，表示有T组测试数据。每组输入的第一行是一个正整数N（N≤30000N\le30000N≤30000），表示食堂有N个窗口。接下来一行输入N个正整数，第i个正整数ai表示第i个窗口最开始有ai个人排队。（1≤ai≤501 \le a_i \le 501≤ai≤50）接下来每行有一条命令，命令有四种形式：
2021-08-04 19:45:57
185
原创 Codeup100000636问题 A: 最少的交换
题目描述：现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？输入：输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000n<500000n<500000），表示序列的长度，当n=0时。接下来的n行，每行一个整数a[i]（0≤a[i]≤9999999990 \le a[i] \le 9999999990≤a[i]≤999999999），表示序列中第i个元素。输出：对于每组输入，输出使得所给序列
2021-08-04 19:42:46
167
原创 Codeup100000635问题 A: 区间查询
题目描述：食堂有N个打饭窗口，现在正到了午饭时间，每个窗口都排了很多的学生，而且每个窗口排队的人数在不断的变化。现在问你第i个窗口到第j个窗口一共有多少人在排队？输入：输入的第一行是一个整数T，表示有T组测试数据。每组输入的第一行是一个正整数N（N≤30000N\le30000N≤30000），表示食堂有N个窗口。接下来一行输入N个正整数，第i个正整数ai表示第i个窗口最开始有ai个人排队。（1≤ai≤501 \le a_i \le 501≤ai≤50）接下来每行有一条命令，命令有四种形式：
2021-08-04 19:39:56
178
原创 Codeup100000634问题 C: 剪花布条
题目描述：一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？输入：输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。输出：输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。样例输入：abcde
2021-08-04 19:36:53
102
原创 Codeup100000634问题 B: P2 统计单词数
题目描述：统计单词数 (stat.cpp/c/pas)一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即单词必须与文章中某一独立残次在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。输入：输入文件共2行。第1行为一个
2021-08-04 11:40:53
164
原创 Codeup100000634问题 A: 动物简介(animal)
题目描述：到了动物园，琦琦开心得跳起来。哗，这里好多动物呀，有老虎，有狮子……，在开心之余，琦琦也不忘妈妈的教导：观察动物时要认真仔细，还要看动物园附上的动物简介呀。动物的简介原来还有英文版的呢！为了卖弄自己的英文水平，琦琦就告诉妈妈每张动物简介里出现了多少次该动物的名称。注意：琦琦只认识小写字母，而且她只认得动物的单词，因此她认为monkeys或者smonkey或者smonkeys都是出现了monkey这个词。你能编程完成琦琦的任务吗？输入：输入文件共n+2行：第1行为数字n（n<=30
2021-08-04 11:35:16
442
原创 Codeup100000633问题 A: 求最长公共子串（串）
题目描述：求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。输入：输入两个字符串输出：输出公共子串样例输入：abcdefadbcef样例输出：bc实现代码1：#include <cstdio>#include <algorithm>#include <cstring>#include <vector>#include <iostream>#inclu
2021-08-04 11:30:38
144
原创 Codeup100000632问题 I: 毕业bg
题目描述：每年毕业的季节都会有大量毕业生发起狂欢，好朋友们相约吃散伙饭，网络上称为“bg”。参加不同团体的bg会有不同的感觉，我们可以用一个非负整数为每个 bg定义一个“快乐度”。现给定一个bg列表，上面列出每个bg的快乐度、持续长度、bg发起人的离校时间，请你安排一系列bg的时间使得自己可以获得最 大的快乐度。例如有4场bg：第1场快乐度为5，持续1小时，发起人必须在1小时后离开；第2场快乐度为10，持续2小时，发起人必须在3小时后离开；第3场快乐度为6，持续1小时，发起人必须在2小时后离开；
2021-08-01 14:31:10
114
原创 Codeup100000632问题 H: 最大报销额
题目描述：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。输入：测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q(Q≤2000Q\le2000Q≤2000) 是给定的报销额度，N（N≤30N\le30N≤30）是发票张数。随后是 N 行输入，每行的格式为：m
2021-08-01 14:27:42
229
原创 Codeup100000632问题 G: 点菜问题
题目描述：北大网络实验室经常有活动需要叫外买，但是每次叫外买的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为ViV_iVi，每种菜的价格为PiP_iPi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。注意：由于需要营养多样化，每种菜只能点一次。输入：输入的第一行有两个整数C（1≤C≤10001 \le C \le 10001≤C≤1000）和N（1≤N≤1001 \le N \le 100
2021-08-01 14:24:37
78
原创 Codeup100000632问题 F: 放苹果
题目描述：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。输入：第一行是测试数据的数目t（0≤t≤200 \le t \le 200≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤101\le M，N\le101≤M，N≤10。输出：对输入的每组数据M和N，用一行输出相应的K。样例输入：26 37 2样例输出：74提示：解题分析：设f(m,n)f(m,n)f(m,n)
2021-08-01 14:21:07
72
原创 Codeup100000632问题 E: 最大子矩阵
题目描述：已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×11 \times 11×1)子矩阵。比如，如下4×44 \times 44×4的矩阵0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2的最大子矩阵是9 2-4 1-1 8这个子矩阵的大小是15。输入：输入是一个N×NN \times NN×N的矩阵。输入的第一行给出N (0<N≤1000 < N \le 1000<N≤100)。再后面
2021-08-01 14:12:36
109
原创 Codeup100000632问题 D: Coincidence
题目描述：Find a longest common subsequence of two strings.输入：First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.输出：For each
2021-08-01 14:08:16
87
原创 Codeup100000632问题 C: 合唱队形
题目描述：N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K1, 2, …, K1,2,…,K，他们的身高分别为T1,T2,…,TKT_1, T_2, …, T_KT1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)T_1 < T_2 < … < T_i , T_i >
2021-07-31 14:29:21
143
原创 Codeup100000632问题 B: 拦截导弹
题目描述：某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。输入：每组输入有两行，第一行，输入雷达捕捉到的敌国导弹的数量k（k≤25k\le25k≤25），第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹
2021-07-31 14:25:35
189
原创 Codeup100000632问题 A: 第二题
题目描述：一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组各元素之和a,b的差最小，对于非法输入应该输出ERROR。输入：数组中的元素输出：降序输出两个子数组的元素和样例输入：10 20 30 10 1010 20 abc 10 10样例输出：40 40ERROR实现代码：#include<cstdio>#include<string>#include<iostream>#include<cstring>u
2021-07-31 14:23:31
114
原创 Codeup100000631问题 C: 货币系统
题目描述：母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。[In their own rebellious way],，他们对货币的数值感到好奇。传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。举例来说, 使用一个货币系统 {1,2,5,10,…}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。写一个程序来计算有多少
2021-07-31 14:11:53
160
原创 Codeup100000631问题 B: 采药
题目描述：辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间， 在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？输入：第 一行有两个整数T（1≤T≤10001 \le T \le 10001
2021-07-31 14:11:21
64
原创 Codeup100000631问题 A: 装箱问题
题目描述：有一个箱子的容量为V（V为正整数，且满足0≤V≤200000 \le V \le 200000≤V≤20000），同时有n件物品（体积值为正整数)。要求从n件物品中，选取若干装入箱内，使箱子的剩余空间最小。输入：1行整数，第1个数表示箱子的容量，第2个数表示有n件物品，后面n个数分别表示这n件物品各自的体积。输出：1个整数，表示箱子剩余空间。样例输入：24 6 8 3 12 7 9 7样例输出：0实现代码：#include<cstdio>#include&
2021-07-31 14:10:49
147
原创 Codeup100000630问题 A: 矩形嵌套
题目描述：有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<da<c,b<da<c,b<d或者b<c,a<db<c,a<db<c,a<d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。输入：第一行是一个正正数N(0<N<10
2021-07-31 14:10:17
72
原创 Codeup100000629问题 A: 【字符串】最长回文子串
题目描述：输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同。如abba和yyxyy。在判断回文时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。输入：一行字符串，字符串长度不超过5000。输出：字符串中的最长回文子串。样例输入：Confuciuss say:Madam,I
2021-07-31 14:09:49
97
原创 Codeup100000628问题 A: 最长公共子序列
题目描述：给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。例如：Z=<a,b,f,c>Z=<a,b,f,c>Z=<a,b,f,c>是序列X=<a,b,c,f,b,c>X=<a,b,c,f,b,c>X=<a,b,c,f,b,c>的一个子序列，Z中的元素在X中的下标序列为<1,2,4,6><1,2,4,6><1,2,4,6>。现
2021-07-31 14:09:18
78
原创 Codeup100000627问题 A: 最长上升子序列
题目描述：一个数列ai如果满足条件a1<a2<...<aNa_1 < a_2 < ... < a_Na1<a2<...<aN，那么它是一个有序的上升数列。我们取数列(a1,a2,...,aN)(a_1, a_2, ..., a_N)(a1,a2,...,aN)的任一子序列(ai1,ai2,...,aiK(a_{i1}, a_{i2}, ..., a_{iK}(ai1,ai2,...,aiK)使得1≤i1<i2<...<
2021-07-29 13:53:30
110
原创 Codeup100000626问题 A: 最大连续子序列
题目描述：给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为Ni,Ni+1,...,Nj{ N_i, N_{i+1}, ..., N_{j} }Ni,Ni+1,...,Nj，其中 1≤i≤j≤K1 \le i \le j \le K1≤i≤j≤K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最
2021-07-29 13:53:06
78
原创 Codeup100000625问题 A: Fibonacci
题目描述：The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55…} are defined by the recurrence:F0=0；F1=1；Fn=Fn−1+Fn−2,n≥2F_{0}=0 ；F_{1}=1；F_{n}=F_{n-1}+F_{n-2},n \ge 2F0=0；F1=1；Fn=Fn−1+Fn−2,n≥2Write a program to calculate the Fibonacci Numbers.输入：Each case
2021-07-29 13:52:47
73
原创 Codeup100000624问题 A: 关键路径
题目描述：描述：图的连接边上的数据表示其权值，带权值的图称作网。上图可描述为顶点集为（a,b,c,d,e)边集及其权值为(始点，终点 权值）：a b 3a c 2 b d 5c d 7c e 4d e 6 网的源点是入度为0的顶点，汇点是出度为0的顶点。网的关键路径是指从源点到汇点的所有路径中，具有最大路径长度的路径。上图中的关键路径为a→c→d→ea \to c \to d \to ea→c→d→e，其权值之和为关键路径的长度为15。本题的要求是根据给出的网的
2021-07-29 13:52:27
151
原创 Codeup100000622问题 C: 畅通工程
题目描述：省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。输入：测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N,M≤100N, M \le100N,M≤100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数
2021-07-29 13:52:04
129
原创 Codeup100000623问题 C: Legal or Not
题目描述：ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has ques
2021-07-29 13:51:50
83
原创 Codeup100000623问题 B: 确定比赛名次
题目描述：有N个比赛队（1≤N≤5001 \le N \le 5001≤N≤500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。输入：输入有若干组，每组中的第一行为二个数N（1≤N≤5001 \le N \le 5001≤N≤500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行
2021-07-29 13:51:15
82
原创 Codeup100000623问题 A: 算法7-12：有向无环图的拓扑排序
题目描述：由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。由偏序定义得到拓扑有序的操作便是拓扑排序。拓扑排序的流程如下：在有向图中选一个没有前驱的顶点并且输出之；从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况
2021-07-29 13:50:41
151
原创 Codeup100000622问题 E: Jungle Roads
题目描述：The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maint
2021-07-29 13:50:10
98
原创 Codeup100000622问题 D: 继续畅通工程
题目描述：省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。输入：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1<N<1001< N < 1001<N<100)；随后的 N(N−1)2\frac{N(N-1)}{2}2N(N−1) 行对应
2021-07-29 13:49:27
133
原创 Codeup100000622问题 B: Freckles
题目描述：In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad’s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley’s engagement falls through.Consider Dick’s back to
2021-07-25 15:41:51
102
原创 Codeup100000622问题 A: 还是畅通工程
题目描述：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。输入：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N−1)2\frac{N(N-1)}{2}2N(N−1)行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，
2021-07-25 15:41:24
72
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人