Irish_Moonshine-CSDN博客

原创 2021年复旦大学计算机科学与技术/电子信息/软件工程机试题解

声明：1、2021年复旦大学机试不采用OJ判定，无具体数据范围与测试数据以及输入输出规范。2、2021年复旦大学机试设定测试时间为150分钟，要求提交源代码+解题思路+自测数据。3、本人所提供的题解不一定为最佳题解或唯一解法，仅供参考。输入规范、输出规范、测试用例可由考生自己设定。若有谬误，欢迎指正。4、本次机试题，在Leetcoder上均有原题。第 1 题方法：深度优先搜索（DFS）思路：由测试数据可知此题为完全二叉树，不必建树。从根节点开始向下遍历，期间维护从根节点到当前节点 xxx .

2021-04-02 21:03:51 1669 2

原创 PAT (Advanced Level) 1135 Is It A Red-Black Tree (30分) 【红黑树】

PAT (Advanced Level) 1135 Is It A Red-Black Tree (30分)1节点是红色或黑色2根节点是黑色3所有NULL节点是黑色4所有红色节点的子节点是黑色5从任何一个节点到其每个叶子的所有路径都包含相同数目的黑色节点因为是递归的对每一个节点的左右子树进行判断，所以理论上左右子树到叶子节点的路径上的黑色节点的数量都是一样的。所以不必纠结 Get_Num 中的max。#include<iostream>#inclu

2020-09-04 02:13:16 232

原创 PTA L3-016 二叉搜索树的结构 (30分) 【BST|测试点细节】

L3-016 二叉搜索树的结构 (30分)Reference: 测试数据细节注意查询数据不在树内的情况，注意负数情况谨慎初始化数据#include<iostream>#include<cstring> //memset#include<string>#include<cstdio> //scanf#include<string>#include<utility> // pair#include<algori

2020-09-02 11:27:59 927

原创 PAT (Advanced Level) 1088 Rational Arithmetic (20分) 【模拟】

PAT (Advanced Level) 1088 Rational Arithmetic (20分) 题意：对两个分数进行加减乘除的操作分析：一定一定要采用函数化编程，不然会死人的！将分数规格化、分数运算、输出部分进行分块。将负号提出来，统一当做非负数处理。WA点：1/-6 需要转换成 -1/6在进行乘除运算和最后输出的时候，最好将负号提出来，对之后的非负数进行操作除零初始运算的时候，最好不要直接转换成假分数，以防增加编码复杂度。乘法的分母不要搞成最小公倍数一些测试点：0/5 0

2020-08-31 15:52:46 166

原创 PAT (Advanced Level) 1060 Are They Equal (25分) 【注释+简洁编码】

PAT (Advanced Level) 1060 Are They Equal (25分)Reference：测试用例题意：采用科学计数法来判断两个数字是否相等。分析：5 001234 1234 数据不规范的情况 YES 0.12340*10^45 123 0.1234 有效位数不足的情况 NO 0.12300* 10^3 0.12340*10^05 123 0.0012 幂指数为负的情况 NO 0.12300* 10^3 0.12000*10^-25 0.0 0.0000 出现0的情况

2020-08-29 17:51:41 135

原创 PAT (Advanced Level) 1057 Stack (30分)【Multiset||树状数组+二分||线段树分治】

PAT (Advanced Level) 1057 Stack (30分)题意：模拟一个栈，实现压入，弹出，查询栈中权值处于中间的元素。分析：对于老实人来说，肯定是踏踏实实的去模拟栈，然后另开一个数据结构用来保存栈内的元素。那么另一个数据结构理论上应该有排序的功能，而且每次插入和查询的效率应该不超过 log(N)log(N)log(N)Multiple Set，本着 PAT 特别爱考 STL 的特点。我一开始想到的就是可以自动排序的Set，然后考虑到可能有重复元素，那么就是 Multiset。理论

2020-08-28 17:59:29 140

原创 PAT (Advanced Level) 1033 To Fill or Not to Fill (25分)【贪心】

PAT (Advanced Level) 1033 To Fill or Not to Fill (25分)【贪心】题意：给你油箱容量 CCC，给你最远想要到达的距离 DDD，给你汽车每升油所能支持的距离 DavgD_{avg}Davg，给你加油站的数量 NNN。然后每个加油站，给你距离起点的位置以及油价。问，你最少可以花费多少美元到达终点。分析：作为老 DPDPDP 恐慌性选手，起手就是一顿动态规划，然而最后复杂度在 30000∗500∗50030000 * 500* 50030000∗500∗

2020-08-23 15:35:11 124

原创 PAT (Advanced Level) 1099 Build A Binary Search Tree (30分)【BST】

1099 Build A Binary Search Tree (30分)思路：依据二叉搜索树的性质，我只需要知道每个节点左子树的结点总数，以及每个节点右子树的结点总数，我就可以确定当前节点元素的取值。实现方式：① 对于节点排序，DFS 遍历整棵树得到每个节点子树的结点总数；② 根据当前取值区间和左子树节点总数确定当前位置的取值，递归继续赋值；③ 通过 BFS实现层序遍历。#include<iostream>#include<cstring> //memset#i

2020-08-16 13:54:42 130

原创 PAT (Advanced Level) 1128 N Queens Puzzle (20分)【化简】

PAT (Advanced Level) 1128 N Queens Puzzle (20分)首先声明，这个题直接双循环暴力就可以过，但是我觉得这样就没什么意思了。复杂度已经超过两亿 200∗1000∗1000200*1000*1000200∗1000∗1000 ，O(N2∗K)O({N}^{2}*K)O(N2∗K) 可能是浙大的OJ比较强劲。本算法复杂度 O(NK)O(NK)O(NK)首先解决的问题就是保证每行与每列的元素唯一，给出的数据就已经是行唯一了，对于列开一个标记数组解决一下。对于列上

2020-08-06 21:52:11 133

原创 PAT (Advanced Level) 1123 Is It a Complete AVL Tree (30分)【AVL】

PAT (Advanced Level) 1123 Is It a Complete AVL Tree (30分)构建一颗完全二叉树（相关代码有注释）通过BFS实现层次遍历（亦可与获取完全二叉树合并，在一个DFS中实现）通过DFS这棵树获取每个结点在完全二叉树的下标 indexindexindex，检查该完全二叉树是否有空位，即可做出判断在使用指针进行操作的时候，一定特别注意指针为空的情况！！！#include<iostream>#include<cstring>#

2020-08-04 21:06:46 144

原创简单决策树调用&可视化【Python】

决策树部分理论支撑1* 通过选取一定的特征来降低数据的不确定性（熵）2* 建议寻找多分类问题的最优特征的最优候选值。把多分类问题转换成多几层递归的二分类问题，防止数据对特征值的控制敏感。3* 停止条件取得了最够好的分类结果递归到了预定的最深深度叶子节点的纯度分裂次数达到极限最大特征数. . .4* 相关公式entropy(D)=−∑i=1nPilog2Pientropy...

2019-07-16 17:53:27 705

原创 Matlab 线性规划&非线性规划&零点问题实例

可编辑代码在EOF（Hhhhh）1%编写fun函数文件function f = fun(x)f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 +4*x(1)*x(2) + 2*x(2) + 1);end%编写约束条件nonlinearcondition函数文件function [c,ceq]= nonlinearcondition(x)c(1) = ...

2019-07-12 21:41:08 658

原创 Matlab 问题实例【循环、积分、微分、绘图、最值、极值】

可复制代码在末尾11466015503701Temp = 1;i = 0;Ans = 0;while(i<=20) Ans = Ans + Temp; Temp = Temp * 4; i = i + 1;endfprintf('%d\n',Ans);2x1 = 0.0000; x2 = 0.4839;Min = 3.871...

2019-07-12 00:21:49 875

原创 POJ 3281 Dining【拆点+SAP网络流】

POJ 3281 Dining这里选择使用的是SAP网络流里的Dinic题意：有n头牛，f个食物，d个饮料。每头牛都有一些自己喜欢的食物和饮料，当且仅当这头牛获得了一个自己喜欢的饮料和一个自己喜欢的食物，他才会开心。求，最多可能有多少牛会开心。每种食物和饮料只有一个。一种解题思路：使用网络流，试图构建满流数量为答案的网络。一种建图思路：超级源点S指向所有食物的边的权值为1，被喜欢的食物...

2019-07-10 21:43:25 197

原创 HDU 1532 Drainage Ditches【HLPP网络流（最高标号预流推进）】

HDU 1532 Drainage Ditches最大流裸题（同POJ 1273）代码做了我所能理解的，比较详尽的注释。参考教程：最大流算法-最高标号预流推进(HLPP)【PS：这大哥为了缩行，太可怕了QAQ】#include<iostream>#include<cstring>#include<cstdio>#include<algor...

2019-07-10 19:32:48 251

原创 NOIP 2002 过河卒【记忆化搜索】

NOIP 2002 过河卒我大概是思维僵化了，我一直就在那里琢磨怎么怎么DP，然后。。。就忘记了记忆化搜索= =，太呆了QAQ#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<string>#include<ma...

2019-07-09 22:45:21 282

原创 NOIP 2002 产生数【建图+DFS+数乘大数】

NOIP 2002 产生数一种解决思路：可以考虑每一个数字可以最终变换成多少个不同的数字，数字关系可以考虑建成有向图，然后开始深搜广搜都可。注意答案会超过longlonglong longlonglong intintint#include<iostream>#include<cstring>#include<cstdio>#include&l...

2019-07-09 22:42:57 224

原创 NOIP 2002 选数【DFS】

NOIP 2002 选数暴力枚举所有可以发生的情况即可。试图素数筛，结果发现自己是个弱智= =，并不能优雅起来。#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<string>#include<map>...

2019-07-09 22:37:49 242

原创洛谷 P1035 级数求和【二分||枚举】

洛谷 P1035 级数求和Emmm，这个题吧，明明可以枚举。但是我非要二分，试图优雅，结果内存超限了一发。。。#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<string>#include<map>#...

2019-07-09 22:34:46 182

原创 BZOJ 1305 dance跳舞【二分+Dinic网络流】

BZOJ 1305 dance跳舞分析：Dinic没什么好说的，问题就是出在建图之上。一种建图思路：将所有的男生、女生，作为一个节点并且每个节点引出并指向两个新的节点分别表示’不喜欢’和‘’喜欢’两个节点。建立超级源点S 和超级汇点 T，通过 S 指向每个男生的主节点，每个女生的主节点指向T，来表示流量。二分答案，该答案等于每一条从S指向男生主节点的边权，同时等于每个女生主节点指向T...

2019-07-08 09:21:35 179

原创 BZOJ 1001 狼抓兔子【Dinic网络流】

BZOJ 1001 狼抓兔子一道非常裸的网络流问题，但是需要一定的优化。这个题的正解应该是SPFA+对偶图，但网络流也Ok。当前弧优化（注释了，没用到，比较弱的优化）多路增广（相比于朴素Dinic而言，是一个非常强的优化）炸点（将无法增广的点，深度标记为不存在，比较强的优化）#include<iostream>#include<cstring>#incl...

2019-07-07 19:59:27 189

原创 PAT (Advanced Level) 1041 Be Unique (20 分)【Python/C++】【字典，Numpy天坑】

PAT (Advanced Level) 1041 Be Unique (20 分)这个题理论上来说没什么好说的，处理效率和读入效率是一个级别的。用C++来解决的话，开个vis数组即可。然而Python Numpy库却给我开了天坑，理论上来说，Python的字典结构要优于列表结构，这是显然的，因为一个O(n)O(n)O(n)级别的，另一个是O(log(n))O(log(n))O(log(n...

2019-07-04 20:32:01 227

原创 PAT (Advanced Level) 1031 Hello World for U (20 分)【Python/C++】【模拟】

PAT (Advanced Level) 1031 Hello World for U (20 分)C++里直接开了个答案数组用来存答案了。注意空格的ASCII码是32，‘0’的ASCII码是48，Python里开了个头指针，尾指针直接模拟。Python：from math import *import sysimport numpy as npstr_in = input()...

2019-07-04 15:59:00 167

原创 PAT (Advanced Level) 1027 Colors in Mars (20 分) 【Python/C++】【进制转换】

注意：Python中，直接将返回值转换成str类型即可（我蠢得要死在到处找char类型）。Python：from math import *import sysimport numpy as npstr_in = input()length = len(str_in)b = [int(n) for n in str_in.split()]x = b[0]y = b[1]z = ...

2019-07-04 14:59:26 193

原创 Python 基本数据分析基础实战【Numpy入门】

import numpy as npx = np.array([1,2,3,4])print(x)y = np.array((1,2,3,5))print(y)z = np.array(([1,2],[3,4],[5,6]))print(z)"""use list or tuple to new an array"""a = np.arange(10)print(a)"""ne...

2019-07-03 21:03:07 144

原创 PAT (Advanced Level) 1023 Have Fun with Numbers (20 分) 【Python/C++】【大数乘法】

PAT (Advanced Level) 1023 Have Fun with Numbers (20 分)按位做大数乘法即可Python:import sysfrom math import *str_in = input()length = len(str_in)b = [int(n) for n in str_in.split()]n = b[0]a = [0]*100...

2019-06-23 10:26:14 201

原创 PAT (Advanced Level) 1019 General Palindromic Number (20 分) 【Python/C++】【进制转换】

PAT (Advanced Level) 1019 General Palindromic Number (20 分)Python：import sysfrom math import *str_in = input()a = [int(n) for n in str_in.split()]n = int(a[0])d = int(a[1])vis = [0] * 50k = ...

2019-06-23 09:33:18 174

原创 PAT (Advanced Level) 1015 Reversible Primes (20 分) 【Python/C++】【进制转换】

PAT (Advanced Level) 1015 Reversible Primes (20 分) 题意不清的沙雕狗屎题！给你一个数，判断是否是素数，然后将它转换成d进制，然后再在d进制里逆序，再视作十进制，判断是否是素数。Python：import sysfrom math import *#str_in = input()def is_prime(x): flag = ...

2019-06-22 21:56:57 169

原创 PAT (Advanced Level) 1011 World Cup Betting (20 分) 【Python/C++】【枚举】

PAT (Advanced Level) 1011 World Cup Betting (20 分)直接取每一行的最大值就OkPython：import sys#str_in = input()str_in = input()a = [float(n) for n in str_in.split()]str_in = input()b = [float(n) for n in st...

2019-06-22 20:50:49 242

原创 PAT (Advanced Level) 1008 Elevator (20 分) 【Python/C++】【模拟】

PAT (Advanced Level) 1008 Elevator (20 分) 注意：连续两个人都处于同一层，仍需要停留5秒。Python：import sysstr_in = input()a = [int(n) for n in str_in.split()]#print(a)n = int(a[0])res = int(0)ans = int(0)for i in r...

2019-06-22 20:18:36 241

原创 Python 基本数据分析基础实战【第三方库扩展，数组，矩阵，广播，numpy】

第三方库扩展（以vs2017下安装pandas为例）Reference：https://blog.csdn.net/weixin_40184249/article/details/80720015工具—Python—Python 环境—在PowerShell 中打开pip install --index https://pypi.mirrors.ustc.edu.cn/simple/ ...

2019-06-21 15:15:42 166

原创 Python 基本排序算法基础实战【O(nlogn or C*n)：归并排序、快速排序、桶排序（基数排序）、堆排序、希尔排序】

C++实现请参考：近乎所有排序——Irish_MoonshinePython实现：其中堆排序完全是按照面向对象设计的，写起来感觉就很繁琐，引起强烈不适。如有更优或更简的正规实现方法，望各位巨巨指教！！！from random import *maxn = 100000 + 10a = [-1,9,1,2,3,8,16,85,24,984,35198,168,325,35384,84,6...

2019-06-20 20:47:04 238

原创 Python 基本排序算法基础实战【O(n^2)：冒泡排序、插入排序、选择排序】

from random import *maxn = 100000 + 10a = [-1,9,1,2,3,8,16,85,24,984,35198,168,325,35384,84,61,684]#从id = 0开始共计17个元素def Bubble_Sort(L, R):#冒泡排序 for i in range(L, R + 1): for j in rang...

2019-06-19 21:39:48 249

原创 Python 面向对象设计基础实战【私有成员、保护成员、公有成员、数据成员、实例化、方法】

Reference：《Python程序设计基础（第2版）》Reference：《Python中的装饰器》https://www.jianshu.com/p/417ac7d95db9#面向对象，基础类#cls 用于定义类方法，self 用于定义实例方法class Car(object): def infor(self): print("This is a Cat!...

2019-06-19 21:08:42 557

原创 Python 基本算法类型基础实战【LIS】

最长上升子序列【LIS】实话说Python解决这种问题,确实不如C++，在编码量上，估计手速签到题和大数计算Python占优势。Python：dp = [0]*30a = [0, 389, 207, 155, 300, 299, 170, 158, 65]len = 1n = 8dp[1] = a[1]def lower_bound(l, r, x): ans = ...

2019-06-19 20:01:59 535

原创 Python 基本结构类型基础实战【Deque、GCD、Part of Quick_Sort】

from collections import deque #双端队列q = deque(range(20))q.rotate(3)#元素循环右移三位（非位运算）print(q)q.rotate(-3)#元素循环左移三位（非位运算）print(q)#Answer:deque([17, 18, 19, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

2019-06-18 15:56:04 183

原创 Python 基本结构类型基础实战【生成器函数、迭代器、切片】

#生成器函数def f(): a, b = 1, 1 while 1: yield a #暂停执行，需要时再产生一个新的元素 a, b = b, a+b#这样做可以节省内存，而不用开list保存所有的中间结果#也不必要一次性print所有中间结果a = f()for i in range(10): print(a.__next_...

2019-06-18 12:40:18 192

原创 Python 基本数据类型基础实战【Lambda】

#Reference:https://blog.csdn.net/program_developer/article/details/82024468#Reference:Python程序设计基础（第2版）#lambda效率不及operator#冒号前是输入参数，冒号后是返回值add = lambda x,y:x**yprint(add(2,5))g = lambda x, y=2,...

2019-06-17 15:55:56 254

原创 Python str & C++ char[] & C++ string【字符串数据处理效率分析】

本次测试采用 25万条 csv 格式的地铁信息字符串数据进行处理，我们需要找到其中的一个关键位置的时间并提取。前提声明：Python str、C++ char[] 、C++ string采用同样的算法编写实现采用同样的数据进行处理避免 includeincludeinclude 或 importimportimport 不必要的文件产生干扰避免 strlen()strlen()strl...

2019-06-17 13:29:07 622

原创 Python Traceback (most recent call last)【StopIteration】

预期处理结果：出现异常后的结果：对比后可以发现：该异常出现之后，后面的语句不再解释进行。异常产生原因：迭代器next读到了尾部（这里是文件尾），无数据可读。异常解决方案：try: #Python next()迭代器完成会引发StopIteration异常 prestr1 = next(reader) #此行做你本来的期望做的迭代操作except ...

2019-06-17 12:30:48 29494

大数据开发——从放弃到入门.docx

空空如也