u012963208-CSDN博客

原创北邮OJ-273. Python List-14计院上机（第二套）D

又用到之前编的NameForm技巧了。这题不难就是很杂，字符串与下标映射表的管理，线性表的管理，字符串处理，简单排序。题目#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define MAXSIZE 50using namespace std;char operation[30];vecto

2017-03-23 01:00:11 820

原创北邮OJ-272. 网络的核-14计院上机（第二套）C

Floyd模板题。题目//输入顶点从1始，内部运行顶点从1始 //其实顶点从0编号也可以，改一改就好了 #include <iostream>#include <vector>#define MAXSIZE 100 #define INF 0x7fffffffusing namespace std;int main(){ int t,n,m;//vexes' num,edge's

2017-03-23 00:55:20 699

原创北邮OJ-271. 旋转图像-14计院上机（第二套）B

是时候查一查旋转变换的变换矩阵了= =两次了都是现场推的。题目#include <cstdio>#define MAXSIZE 100using namespace std;int t,n,m;int buf[MAXSIZE][MAXSIZE];int matr[MAXSIZE][MAXSIZE];void clockWise(){ //rotate for (int

2017-03-23 00:53:02 716

原创北邮OJ-270. 众数-14计院上机（第二套）A

认真写处理边界还挺麻烦。直接Hash了。题目#include <cstdio>#define MAXSIZE 100010using namespace std;int hash[MAXSIZE];int main(){ int t,n; int mostNum; int buf[110]; scanf("%d",&t); while (t--){

2017-03-23 00:50:51 598

原创北邮OJ-269. 网络传输-14网研上机D

题目描述网络的高效互联与智能传输是提升海量用户服务请求映射效率的重要措施。在这个任务中，你要用最少的传输时间，将特定的数据源发送到指定的网络节点中。我么给定的网络一共包含N个节点（从1到N编号），其中节点1为数据源。网络中有M条无向边（u,v,w），表示一条传输线连接节点u和节点v，且数据通过这条传输线的平均时间为w。由于传送机制的限制，当一个节点接收到数据之后，它只能选择与它互连的一个节点

2017-03-21 17:58:17 1389 1

原创北邮OJ-105. 寻找宝藏-11计院上机C

典型的树DFS模型题目：时间限制 1000 ms 内存限制 65536 KB Special Judge 题目描述有一棵多叉树T，你在树根处，宝藏在某一叶子节点L。现在你沿着树枝向叶子方向走去，从不回头，如果遇到树叉节点，你等概率地挑选一个分支继续走。请问，在给定T，L的情况下，你有多大概率拿到宝藏？输入格式第一行，整数N，M，L(1< N< 1000，0< M< 1000，0< L<

2017-03-21 16:10:13 699

原创北邮OJ-104. 912星球的研究生-11计院上机B

Debug记录：本题由于使用了hash，故MAXSIZE应该使用编号的上限，而非研究生输入记录条数的上限。题目:时间限制 1000 ms 内存限制 65536 KB 题目描述最近912星球的研究生入学了，912星球的教务处因此忙的焦头烂额，要求yzr做一个信息管理系统登陆查询研究生的考试成绩。但是yzr太弱了，你能帮帮忙么？ 912星球的每一位研究生都有一个名字id和一份星球考研成绩，可喜的

2017-03-21 16:08:12 608

原创北邮OJ-103. 反转单词-11计院上机A

时间限制 1000 ms 内存限制 65536 KB 题目描述给出一句英文句子(只由大小写字母和空格组成，不含标点符号，也不会出现连续的空格),请将其中的所有单词顺序翻转输入格式多组数据，以EOF结束。每行一句英文句子(确保只由大小写字母和空格组成，不含标点符号，也不会出现连续的空格，字符串总长度1000以内)输出格式每组数据输出一行，为反转后的字符串输入样例 It is a a

2017-03-21 16:05:18 839

原创九度OJ-题目1172：哈夫曼树-10计院上机D

题目描述：哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。输入：输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。输出：输出权值。样例输入： 5 1 2 2 5 9 样例输出： 37#

2017-03-21 13:22:18 676

原创九度OJ-题目1171：C翻转-10计院上机C

题目描述：首先输入一个5 * 5的数组，然后输入一行，这一行有四个数，前两个代表操作类型，后两个数x y代表需操作数据为以x y为左上角的那几个数据。操作类型有四种： 1 2 表示：90度，顺时针，翻转4个数 1 3 表示：90度，顺时针，翻转9个数 2 2 表示：90度，逆时针，翻转4个数 2 3 表示：90度，逆时针，翻转9个数输入：输入有多组数据。每组输入一个5

2017-03-21 13:21:14 413

原创九度OJ-题目1170：找最小数-10计院上机B

题目描述：第一行输入一个数n，1 <= n <= 1000，下面输入n行数据，每一行有两个数，分别是x y。输出一组x y，该组数据是所有数据中x最小，且在x相等的情况下y最小的。输入：输入有多组数据。每组输入n，然后输入n个整数对。输出：输出最小的整数对。样例输入： 5 3 3 2 2 5 5 2 1 3 6 样例输出： 2 1#include <io

2017-03-21 13:19:03 425

原创九度OJ-题目1169：比较奇偶数个数-10计院上机A

题目描述：第一行输入一个数，为n，第二行输入n个数，这n个数中，如果偶数比奇数多，输出NO，否则输出YES。输入：输入有多组数据。每组输入n，然后输入n个整数（1<=n<=1000）。输出：如果偶数比奇数多，输出NO，否则输出YES。样例输入： 5 1 5 2 4 3 样例输出： YES#include <iostream>#include <cstdio>#

2017-03-21 13:17:29 535

原创九度OJ-题目1176：树查找-10网研上机D

题目描述：有一棵树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。该树是完全二叉树。输入：输入有多组数据。每组输入一个n(1<=n<=1000)，然后将树中的这n个节点依次输入，再输入一个d代表深度。输出：输出该树中第d层得所有节点，节点间用空格隔开，最后一个节点后没有空格。样例输入： 4 1 2 3 4 2 样例输出： 2 3#include

2017-03-21 00:46:46 494

原创九度OJ-题目1175：打牌-10网研上机C

Debug记录：见代码注释。题目描述：牌只有1到9，手里拿着已经排好序的牌a，对方出牌b，用程序判断手中牌是否能够压过对方出牌。规则：出牌牌型有5种 [1]一张如4 则5…9可压过 [2]两张如44 则55，66，77，…，99可压过 [3]三张如444 规则如[2] [4]四张如4444 规则如[2] [5]五张牌型只有12345 23456 34567 45

2017-03-21 00:45:24 584

原创九度OJ-题目1174：查找第K小数-10网研上机B

题目描述：查找一个数组的第K小的数，注意同样大小算一样大。如 2 1 3 4 5 2 第三小数为3。输入：输入有多组数据。每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。输出：输出第k小的整数。样例输入： 6 2 1 3 5 2 2 3 样例输出： 3#include <iostream>#include <cstdio> #incl

2017-03-21 00:42:12 613

原创九度OJ-题目1173：查找-10网研上机A

题目描述：输入数组长度 n 输入数组 a[1…n] 输入查找个数m 输入查找数字b[1…m] 输出 YES or NO 查找有则YES 否则NO 。输入：输入有多组数据。每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m<=n<=100）。输出：如果在n个数组中输出YES否则输出NO。样例输入： 5 1 5 2 4 3 3

2017-03-21 00:40:14 344

原创北邮OJ-109. 中序遍历树-11网研上机C

算法分析：本题说是树，其实仔细分析完应当使用无向图进行建模，然后对该图进行限制性的深度优先遍历。Debug记录：（见代码注释）没有使用visited标记，出现了两个结点互相访问，死循环遍历边表的时候应当使用循环尽力搜，知道找到第一个没有visited的结点才是真正的首个子节点，否则是父节点每调用一次inOrder之前都得重置visited用引用传参来返回子函数结果很不好！在循环中反复调用的话

2017-03-20 22:02:02 829

原创北邮OJ-108. 虚数-11网研上机B

关于优先队列priority_queue，无论是小根堆还是大根堆，其排序时候调用的运算符都是<，故对结构体重载<即可对stack、queue等，top()方法返回的是一个常引用噢！（由栈、队列的性质所决定）。所以要调用这个常引用的方法就得把方法写成常成函数！题目描述给你一个复数集合{Aj+i*Bj},保证Aj和Bj都是整数，初始为空集。每次会给你如下两种操作中的一种： 1."Insert

2017-03-20 21:47:32 454

原创北邮OJ-107. 字符串操作-11网研上机A

Debug 记录： 1. 字符串并没有说不包含空格！所以得用gets 2. 由于用了gets，所以得考虑每个样例在用gets之前都得吸收掉前面的回车！！！！！！！这里出bug调了很久！！ 3. 题目说的是替代掉“子串”，也即新串的长度不会覆盖掉原串的’\0’字符！所以不能把新串的’\0’写到子串里进去！题目描述大家平时都会用到字符串，现在有几种字符串操作，需要你用这几种操作处理下字符

2017-03-20 21:31:54 633

原创北邮OJ-101. IP地址-12网研上机C

分析这题着实是坑爹了。所以总结题目的意思是：各种非法输入都可能发生，所有情况都得考虑到。故最佳方法就是用scanf("%d.%d.%d.%d%c",&x[0],&x[1],&x[2],&x[3],&c);来进行判断是否输入合法。然而倘若如此，若最后一个%d处没有输入元素，则程序会一直等待输入流输入一个数字，导致无法进行下去。而且使用此法的话当后续串没有被读入时，还得追加一个字符串读入函数进行后处

2017-03-20 17:18:28 3096 2

原创北邮OJ-100. 二叉树的层数-12网研上机B

老师有一个问题想考考mabo，但是mabo不会，所以想请你来帮帮忙。问题如下：给一个二叉树请把这个棵二叉树按层来打印。如果为相同层，需要从左到右打印。一个节点是先添加左节点后添加右节点，即添加顺序与输入顺序一致。输入格式首先输入一个整数T，表示一共有T组数据 0< T < =10再输入两个整数N,M(0<=N,M<=100)表示下面有N行，这个树有M个节点(

2017-03-20 17:06:12 1072

原创北邮OJ-99. 打印字符串-12网研上机A

题目描述老师有一个问题想考考mabo，但是mabo不会，所以想请你来帮帮忙。问题如下：给一串字符串，统计其中某个字符的个数。输入格式首先输入一个整数T，表示一共有T组数据 0#include <iostream>#include <cstdio>#include <cstring>#define MAXSIZE 1010using namespace std;int main(){

2017-03-20 17:02:10 702

原创北邮OJ-94. 最小距离查询-13计院上机D

算法分析：算法一：每次查询直接调用query，并且左右都分别遍历到尽头。超时算法二：优化了“左右分别遍历到尽头”的算法，采取了从index开始向两侧同时遍历，第一次找到相同值就返回。依然超时算法三：在各种优化了输入输出依然超时后，终于意识到问题的本质——m具有可怕的最大值，也就是说将要面对的是海量的查询次数。每次查询都要重新调用query的话会造成时间的严重浪费。于是想到使用空间换时

2017-03-20 10:08:18 879

原创北邮OJ-93. 中序遍历序列-13计院上机C

即判断此序列是否是一个非递减序列题目描述给出一个序列，判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出”Yes”，否则输出”No”。一颗带权二叉树是一颗二叉搜索树（二叉排序树），当且仅当对于任意一个节点，他的左子树中的所有权值小于当前节点的权值，且它的右子树中的所有权值均大于当前节点的权值。输入格式第一行T(T≤10)代表数据组数。每组数据包括两行：第一行为一个整数N(1

2017-03-20 10:04:44 718

原创北邮OJ-92. 统计节点个数-13计院上机B

最终算法：使用树模型，建立完整的包含父节点与子节点的树结构，这是为了后面在遍历比较与父与子的时候能够找到父找到子。然后关于degree的计算，在输入父子关系的时候可以直接把父与子的degree分别+1（因为求的是总度，可以看成无向图的顶点的度来处理）。错误建模： 1.使用了并查集模型：错误在于只能记录父节点而不能记录子节点 2.使用了图模型：错误在于把树转化为图之后，要把简单的父

2017-03-20 10:01:10 553

原创北邮OJ-87. 日期-13计院上机A

题目描述请你计算出第X年Y月Z日是第X年的第几天。其中，1月1日是第一天，1月2日是第二天，以此类推。计算时请注意闰年的影响。对于非整百年，年数能整除4是闰年，否则不是闰年；对于整百年，年数能整除400是闰年，否则不是闰年。如1900年和1901年不是闰年，而2000年和2004年是闰年。输入格式第一行有一个整数T (T≤100)，表示一共有T组数据需要你处理。接下来一共有T行，

2017-03-20 09:56:41 611 1

原创北邮OJ-91. 文件系统-13网研上机D

题目描述现在很多操作系统的文件系统都是基于树形结构设计的。即一个目录下可以有若干个目录和文件，而每个目录和文件都可以通过一条从根目录出发的唯一路径来唯一确定。我们希望你实现对这样的一个文件系统的简单管理。为了简化问题，我们做出如下假设：假设文件系统初始时只有一个根目录root。假设所有出现的文件和目录的名字都是唯一的。即，不会有两个相同名字的文件出现，不会有两个相同名字的目录出现，也

2017-03-16 22:15:12 643

原创北邮OJ-90. 字符串转换-13网研上机Ｃ

本就想暴力膜试一下，没想到竟然ＡＣ了。。。原来是道枚举搜索的题。不过也对，复杂度就在百万级别，没道理超时。题目描述我们将仅由若干个同一小写字母构成的字符串称之为简单串，例如”aaaa”是一个简单串，而”abcd”则不是简单串。现在给你一个仅由小写字母组成的字符串，你需要用最小的花费，将其转换成一个简单串。花费的计算规则如下：将a到z这26个小写字母从左到右排成一排，则每个字母都有左右两个邻居，

2017-03-16 21:13:14 661

原创北邮OJ-89. 统计时间间隔-13网研上机B

统计时间间隔时间限制 1000 ms 内存限制 65536 KB 题目描述给出两个时间(24小时制)，求第一个时间至少要经过多久才能到达第二个时间。给出的时间一定满足的形式，其中x和y分别代表小时和分钟。0≤x<24,0≤y<60。输入格式第一行为数据组数T(1≤T≤50000)。每组数据包括两行，分别代表两个时间输出格式每组数据输出一行，表示最少经过的分钟数。输入样例

2017-03-16 20:52:47 515

原创北邮OJ-88. 最值问题-13网研上机A

时间限制 1000 ms 内存限制 65536 KB 题目描述给出N个数，求出这N个数中最大值和次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。输入格式第一行为测试数据的组数T(T≤20)。请注意，任意两组测试数据之间是相互独立的。每组数据包括两行：第一行为一个整数N(1≤N≤1000)。第二行为N个正整数，每个整数均不大于106。输出格式

2017-03-16 20:40:59 449

原创北邮OJ-278. 图像识别-14计院上机C

Problem C. 图像识别题目描述在图像识别中，我们经常需要分析特定图像中的一些特征，而其中很重要的一点就是识别出图像的多个区域。在这个问题中，我们将给定一幅N x M的图像，其中每个1 x 1的点都用一个[0,255]的值来表示他的RGB颜色。如果两个相邻的像素点颜色差不超过D，我们就认为这两个像素点属于同一个区域。对于一个像素点(x,y) ，以下这8个点（如果存在）是与它相邻的：（x

2017-03-15 18:24:51 671

原创北邮OJ-277. 内存分配-14计院上机B

Problem B. 内存分配题目描述在操作系统中，内存分配是非常重要的工作。已知内存空间由N个内存块组成，这些内存块从1到N编号，进行内存分配时，操作系统将选择一块大小足够的内存全部分配给请求内存的进程。例如，当进程请求10MB的内存时，操作系统必须向该进程分配一个不小于10MB的内存块。内存块不能被重复分配。操作系统有三种基本的分配方式，分别为：首次适应：从1号到N号内存块

2017-03-15 17:51:13 550

原创北邮OJ-276. 中位数-14计院上机A

题目描述给定一个长度为N的非降数列，求数列的中位数。中位数：当有序数列的项数N为奇数时，处于中间位置的变量即为中位数；当N为偶数时，中位数则为处于中间位置的两个数的平均数。输入格式输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。对于每组测试数据：第一行是一个正整数N（1<=N<=100），表示数列长度。第二行有N个整数，整数之间用空格隔开，所

2017-03-15 17:27:46 577

原创北邮OJ-98. IP数据包解析-12计院上机D

Debug记录：本题被坑惨了对是的没错。就是被该gets却scanf坑的。搞了半天以为是引用传参在子函数内部无法自增。。。。原来是由于scanf读串导致串过短，在子函数内部遍历串的时候发生越界了题目描述我们都学习过计算机网络，知道网络层IP协议数据包的头部格式如下：其中IHL表示IP头的长度，单位是4字节；总长表示整个数据包的长度，单位是1字节。传输层的TCP协议数据段的头部格式如下：头部长

2017-03-14 22:15:11 614

原创北邮OJ-97. 二叉排序树-12计院上机C

题目描述二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；左、右子树本身也是一颗二叉排序树。现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点

2017-03-14 20:43:48 520

原创北邮OJ-96. 矩阵幂-12计院上机B

题目描述给你一个n*n的矩阵，求其矩阵的k次幂，即Pk输入格式第一行，一个整数T（0//#include <iostream>#include <cstdio>#define MAZSIZE_MATRIX 100using namespace std;struct Matrix{ int data[MAZSIZE_MATRIX][MAZSIZE_MATRIX]; i

2017-03-14 20:04:36 405

原创北邮OJ-95-二进制数-12计院上机A

题目描述大家都知道，数据在计算机里中存储是以二进制的形式存储的。有一天，小明学了C语言之后，他想知道一个类型为unsigned int 类型的数字，存储在计算机中的二进制串是什么样子的。你能帮帮小明吗？并且，小明不想要二进制串中前面的没有意义的0串，即要去掉前导0。输入格式第一行，一个数字T（T<=1000），表示下面要求的数字的个数。接下来有T行，每行有一个数字n（0<=n<=10^8），

2017-03-14 19:52:04 638

原创北邮OJ-268-进程管理-14网研上机C

本题典型的树模型。是的没错，没写过关于树的模板，回头写一个。没模板现场花半个小时有点吃不消。　　 Problem C. 进程管理题目描述在操作系统中，进程管理是非常重要的工作，每个进程都有唯一的进程标识（PID）。每个进程都可以启动子进程，此时我们称它为其子进程的父进程，除了PID为0的进程之外，每个进程有且只有一个父进程，在这个任务中，你需要实时维护操作系统运行中的三个基本操作：

2017-03-14 17:19:32 993 4

原创北邮OJ-267-最小堆-14网研上机B

算法分析：本来打算使用标准的二叉树模板自上而下递归检索是否是最小堆，然而题目给的输入结构竟然给了更好解法的提示：使用双亲表示法自下而上检索——是的没错，就是套用“并查集模板”。（复杂度nlog(n)，还可以继续优化（剪枝），不过优化完复杂度还是这个数量级，反正n很小不会超时，懒得写了）Problem B. 最小堆题目描述给定一棵带权二叉树，请判断它是不是一个最小堆。一棵二叉树是一个最

2017-03-14 16:23:12 881

原创北邮OJ-266-分数加法-14网研上机A

题目描述求2-a+2-b，其中a和b均为正整数，结果请用最简分数表示。输入格式第一行为测试数据的组数T（1<=T<=400）。请注意，任意两组测试数据之间是相互独立的。每组测试数据一行，包含两个整数a和b（2<=a,b<=20）。输出格式对于每组测试数据，在一行内输出结果，分子和分母用“/”隔开。输入样例 2 2 4 3 2 输出样例 5/16 3/8#inc

2017-03-14 14:33:18 1546 3

数据结构与算法分析（C语言描述）第二版

acm程序设计曾宗根

空空如也