- 博客(57)
- 收藏
- 关注
RSS订阅原创 python课程作业——scipy
import matplotlib.pyplot as pltimport numpy as npimport seaborn as sns# 10-1 reference: https://docs.scipy.org/doc/scipy-1.1.0/reference/tutorial/linalg.htmlfrom scipy.linalg import lstsqm...
2018-06-11 01:35:41
362
原创 python课程作业——matplotlib
import matplotlib.pyplot as pltimport numpy as npimport seaborn as sns# 11-1def f(x): return np.sin(x-2)**2 * np.exp(-x**2)x = np.arange(0, 2, 0.001)plt.plot(x, f(x), label='$\sin^2(x-2...
2018-06-11 00:56:01
393
原创 python课程作业——numpy
以下是用jupyter notebook导出markdown格式的文件，对应输入输出。。import numpy as npfrom scipy.linalg import toeplitzn = 200m = 500A = np.random.randn(n, m)B = toeplitz(np.arange(m))I = np.eye(m,m)print(A)pri...
2018-06-10 23:22:26
488
原创 python课程作业——Leetcode 31. Next Permutation
DescriptionImplement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such arrangement is not possible, it must rearrange it as the lowe...
2018-06-09 21:13:03
130
原创 python课程作业——Leetcode 6. ZigZag Conversion
DescriptionThe string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H N...
2018-06-09 20:39:08
207
原创 python课程作业——Leetcode 3. Longest Substring Without Repeating Characters
DescriptionGiven a string, find the length of the longest substring without repeating characters.Solution维护一个lp, rp和mp，mp表示s(lp,rp]中所有字母-位置的dict，双指针扫描即可Codeclass Solution: def lengthOfLo...
2018-06-09 20:14:47
90
原创 python课程作业——Leetcode 2. Add Two Numbers
DescriptionYou are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers...
2018-06-09 19:43:43
130
原创 python课程作业——第11章 测试代码
第11章 测试代码 # 11-1# city_functions.pydef get_formatted_city_name(city, country): """生成规范格式的城市名""" return city.title() + ', ' + country.title()# main.pyimport unittestfrom city_func...
2018-06-09 00:35:33
229
原创 python课程作业——第10章 文件和异常
第10章 文件和异常# 10-11# number_writer.pyimport jsonnum_str = input("Please input your favourite number: ")num = int(num_str)with open('num.json', 'w') as fout: json.dump(num, fout)# number_...
2018-06-09 00:33:44
204
原创 python课程作业——第9章 类
第9章 类 # 9-2class User(): """用户""" def __init__(self, first_name, last_name): """初始化姓名""" self.first_name = first_name.title() self.last_name = last_name.
2018-06-08 22:28:16
657
原创 python课程作业——第8章 函数
第8章 函数# 8-12def printMaterial(name, *materials): print("costumer " + name + ":") for material in materials: print(material) print()printMaterial("John", "beef", "tuna")pri...
2018-06-08 22:27:37
119
原创 python课程作业——第7章 字典
第7章 字典# 7-8sandwich_orders = ['tuna sandwich', 'peanut sandwich', 'veal sandwich']finished_sandwiches = []while sandwich_orders: sandwich = sandwich_orders.pop() print('I made your ' + ...
2018-06-08 22:26:28
315
原创 python课程作业——第6章 字典
第6章 字典# 6-8pets = [ { 'name': 'miao', 'type': 'cat', 'owner': 'Sam', }, { 'name': 'wang', 'type': 'dog', 'owner': 'Bob', }]for pe...
2018-06-08 22:21:56
1110
原创 python课程作业——第5章 if语句
第5章 if语句# 5-8users = ["Alice", "Bob", "Cindy", "Doug", "Eric", "admin"]for user in users : if user == "admin" : print("Hello admin, would you like to see a status repor
2018-06-08 22:21:14
218
原创 python课程作业——第4章 操作列表
第4章 操作列表 # 4-1pizzas = ["fruit pizza", "beef pizza", "seafood pizza"]for pizza in pizzas: print("I like " + pizza)print("I really love pizza!")# 4-10a = list(range(1, 12))print(a)pri...
2018-06-08 22:20:01
266
原创 python课程作业——第3章 列表简介
第3章 列表简介# 3-4inviter = ["Alice", "Bob", "Cindy"]for member in inviter: print("Welcome " + member + ", you are invited to the dinner")# 3-5inviter = ["Alice", "Bob", "
2018-06-08 22:18:43
130
原创 python课程作业——第2章 变量和简单数据类型
第2章 变量和简单数据类型# 2-3name = "Eric"print("Hello " + name + ", would you like to learn some Python today?")# 2-4name = "Albert Einstein"print(name.upper())print(name.lower())print(name.titl...
2018-06-08 22:16:47
245
原创 python课程作业——第1章 起步
第1章 起步1. 浏览 Python 主页（https://www.python.org/），在博客上写下你有哪些发现和收获下载了最新Python 3.6.4 与 Python 2.7.14 点开文档查看最新的更新 看Use Python for … 版块，了解热门Python库2. 假设你已经成为一位 Python 编程高手，你打算实现怎样的程序？在博客上写下你的目标.学会如...
2018-06-08 22:15:07
398
原创 PQ树小结
【目标】 求一个排列，满足若干限制，限制内容是：某个集合中的数，在最后生成的排列中要放在一起。 【节点】 首先，PQ树是一棵树。 叶节点和两种非叶节点，定义一个点的类型： 叶节点：代表0~n-1的一个数 非叶节点P：表示其儿子节点可以任意交换顺序 排列 非叶节点Q：表示其儿子节点只可 正序 或 反序 排列（注意，只有儿子结点，不是子树）在每次新增过程中，首先会给叶子节点标注关键点（即需
2016-07-22 17:53:29
3767
原创 【BZOJ 2149】 拆迁队
题解先来确认一下题意。。 注意题目是说把某些位置上的数“改”成其他数，而不是把数“删”去。。换句话说题目求的不是简单的最长上升序列。。。 确认完题意后，第一问即是求d[i](其中d[i]=a[i]−i)d[i](其中d[i]=a[i]-i)的最长不下降序列。f[i]=max{f[j]}+1f[i]=max \{ f[j] \} + 1 其中jj满足j<i,d[j]<d[i]j<i, d[j]
2016-02-19 17:45:43
1573
原创 【URAL刷题记】 URAL 1090~URAL 1097
URAL 1090/*K行士兵站成N列，每个士兵都有自己的高度，一个士兵在该行中每有一个站在他左边而比他矮的士兵就跳一下，求哪一行跳的次数最多解答：就是求最大逆序数，我是用BIT写的*/#include<cstdio>#include<cstring>const int maxn=10010;int TN;int T[maxn];void add(int x,int v){ for(
2016-02-13 23:28:56
685
原创 URAL 1091 Tmutarakan Exams
题意求NN以内的大小为KK的数集个数，满足数集内的数的gcd>1gcd>1题解设f[x]表示公约数是x的倍数的情况数，g[x]表示公约数恰好是x的情况数 有： fn=∑n|dg(d)f_n=\sum_{n|d}g(d) gn=∑n|df(d)∗μ(dn)g_n=\sum_{n|d}f(d)*\mu(\frac{d}{n}) 其中fn=(⌊Nd⌋k)f_n=\binom{\lfloor\fra
2016-02-13 23:19:23
352
原创 URAL 1533 Fat Hobbits
题意构造最长反链题解先来回顾一下几个做法： 1. 求最长链——直接DP，然后还可能可以用二分优化 2. 求最小反链覆盖——类似拓扑排序，每次把度为0的点找出来删掉即可 3. 求最小链覆盖——即是在求路径覆盖，把每个点拆成i_0,i_1，原图i->j（注意要补全所有关系），则连i_0->j_1， (点数-最大匹配数)即为答案。构造即为把匹配边“对回去”“连起来” 4. 求最长反链——在3.那
2016-02-11 17:01:30
831
1
原创 【URAL 刷题记】URAL 1600 ~ URAL 1607
URAL 1600/*题意: 给三维空间中n个点, 且每个点有平均飞行的向量. 问是否存在一个时间, 2个东西距离<=d暴力枚举点对, 然后三分判最低点是不是小于等于d.如果是的话, 在其左侧二分寻找恰好距离为d的时间.（我是直接取一个平面以后看成射线与圆的交点问题。。。） */#include<cstdio>#include<cmath>double eps=1e-8;int dcmp(
2016-02-09 14:47:19
1109
原创 【URAL 刷题记】URAL 1317 ~ URAL 1326
URAL 1317/*A题题意：一个用高度为h的围栏围住的停车场里面有一个激光发射器，它可以消灭距离在R之内的冰雹（冰雹不能落到比围栏低的位置或者被围栏挡住），求可以消灭的冰雹的数量解法：先确定冰雹与凸包的位置关系，然后分类讨论（1）冰雹落点在凸包里面，直接计算最小距离是否大于R（2）冰雹落点在凸包外面，当冰雹恰好未被围栏挡住时距离最小，求出冰雹与发射器连线与围栏在平面上的交点，再利用相似三角形
2016-02-08 23:03:52
744
原创 【URAL 刷题记】URAL 1028 ~ URAL 1035
URAL 1028/*题意：求左下角点的个数。。。题解：把点按照x坐标排序，y轴建一棵树状数组即可。。*/ #include<algorithm>#include<cstdio>using namespace std;typedef pair<int,int>P;const int MAXN=40000;int T[MAXN];void add(int x, int v){ for
2016-02-05 19:43:55
985
原创 CF 333E Summer Earnings
题意给点集PP，求max{min{|AB|,|AC|,|BC||A,B,C∈P}}\max \{ \min\{|AB|,|AC|,|BC|\quad|\quad A,B,C \in P\}\}题解先说说正解： 先不考虑三点共线 注意到任何一个三角形都有一个角∈(π/3,π)\in(\pi/3,\pi)（因为内角和=π=\pi），所以我们枚举第ii个点作为这个角的顶点，把其他点极角排序，用一个单调
2016-01-28 20:01:45
382
原创 URAL 1733 Forgotten Technology
题意给一个矩形RR，给一个圆CC，圆心一定在矩形内部，再给出一个点PP，PP到矩形的距离>0，到圆的距离>0。问在不与RR接触的情况下，PP到CC的最短距离，题目保证答案一定存在。题解坑爹题。 分为两种情况： 1. 如果PP与圆心的连线不经过矩形，那么距离即是答案。 2. 否则，做圆与矩形的交点，观察可以发现，如果要与圆接触，到这些点一定是最近的。在第二种情况下，关键点有：圆与矩形的交点、矩形
2016-01-26 22:31:21
277
原创 URAL 1735 Theft of the Century
题意有两种物品：白金和金子，单位重量分别为x,yx,y，装在nn个袋子里，每个袋子里物品种类相同，并且分别有mm个。 现在要从每个袋子中拿出一些，一起称重，只能称一次，问是否一定能知道每个袋子里物品的种类是什么，如果可以，并输出方案。题解题目给定x<yx<y。那么，事实上，称一次重，可能有2n2^n种状态。 那么，原题转化为： 要求一个集合SS，f(S)f(S)定义为SS中元素的和，则有SS的
2016-01-26 22:17:19
329
原创 UVALive 5913 【NEERC 2011 K】 Kingdom Roadmap
题意给一棵树，问最少连几条边使得新图无割边，并输出方案。题解有很多方法。。这里说一种： 先找一个度大于1的节点作为根（否则一定是一个2个点的图，特判即可） 对每棵子树递归处理： 如果子树的儿子节点大于2，那么两两配对，这样每棵子树留下1 or 2个度为1的节点（尽可能地“留下”，即是说，仅当点数>2的时候，才在两个叶子上连边），并放回给父亲节点。 最后对于根，因为其度大于1，故一定有>=2个
2016-01-26 22:07:40
396
原创 UVALive 5913 【NEERC 2011 D】 Dictionary Size
题意给n个单词，用它们构成新单词，新单词串合法的条件是： 1. 与某个原单词相同 2. 是某个原单词前缀+某个单词后缀（前缀和后缀非空、前缀和后缀可以是整个单词、两个拼接字符串可以取自一个单词） 统计不同的新单词数量。 单词长度≤\leq40题解先不考虑重复， 那么每个前缀能对应所有的后缀，总单词数目是 不同非空前缀数×不同非空后缀数+原单词总数不同非空前缀数\times不同非空后缀数
2016-01-26 11:21:32
456
原创 51NOD 1210 矩阵查询
题解恩，二维线段树是个好办法。 下面介绍不用二维线段树的方法。。 设原矩阵为Ai,jA_{i,j}， 定义“前缀和”矩阵：σAi,j=∑1≤ki≤i∑1≤kj≤jAki,kj\sigma A_{i,j} = \sum_{1 \leq k_i \leq i}\sum_{1 \leq k_j \leq j} A_{k_i,k_j} 定义“差分”矩阵δAi,j\delta A_{i,j}有：Ai,
2016-01-10 00:31:37
952
原创 BZOJ 4373 算术天才⑨与等差数列
题解考虑一个数列AiA_i（排序后）为等差数列且公差为KK的充要条件是： n=0n=0， 或者K=0∧max=minK=0 \wedge \max = \min， 或者max−min=n×K∧gcd(di|2≤i≤n)=K\max - \min = n \times K \wedge \gcd(d_i | 2 \leq i \leq n)=K， 其中di=Ai−Ai−1d_i = A_i-A
2016-01-09 23:50:19
443
原创 51NOD 1020 逆序排列
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1020题解注意到数列中最大的数放下去以后，它所能产生的逆序对数是确定的。 那么我们依次从大到小放，每次产生的逆序对数x，有0≤x≤(n−已经下放的个数)0 \leq x \leq (n-已经下放的个数) 然后我们令f[i][j]f[i][j]表示已经下放了ii个数，逆序对
2015-12-29 12:41:59
419
原创 【2015新手赛网络赛】 1004 Good Subsets
题意给定一个数N，问所有满足下述性质的集合的个数： 集合中所有数的数码都只出现一次。 例如：{135,27,49}符合，{134,27,49}不符合（因为出现了两个4），{177,23}不符合（因为177出现了两次7）题解第一想法是：f[S]表示数码集为S的情况下，组出一个≤N\leq N的数，有多少种方案？ 这一步是一个数位DP，枚举每一位统计即可，唯一需要注意的是，同一个数中数码也只能出现
2015-12-21 00:33:07
415
原创 HDU 5561 【2015合肥现场赛】 Kingdom of Tree
按照w排序直接做？错，比如说 A B 3 B C 2 A D 2 每个子树选的时候，A-B是最大匹配边，而当两个连起来的时候，B-C A-D成了最大匹配边那么按照dp11-dp0排序？也是错的。 同样是上面的例子，这时候B子树如果不匹配A-B这条边，子树中最优情况是不找匹配边，而此时A-D连起来时，A-B反而又成了匹配边。。。 这个问题引出：如果不记录子树内选边情况，单记录是否与跟
2015-12-20 13:41:06
755
原创 POJ 1637 Sightseeing tour
题意给一个混合图（有向边、无向边均有），问是否存在欧拉回路题解经典题。 参见黑书p324，两种解法。 第一种是把边视为一类点，原来的点视为另一类点，构建二分图，进一步构建图 这里总结一下第二种做法： 基本定理是：对一个有向图，当且仅当其基图连通且每个点入度=出度。 先只看有向边，统计每个点入度和为In[i]In[i]，出度和为Out[i]Out[i]然后只看无向边，对所有无向边任意定向。
2015-12-07 22:03:32
276
原创 POJ 1273 Drainage Ditches
题意给m个点（窝巢！），n条边的有向图，求1~m最大流题解测试最大流模板（尼玛又是m个点）codeDinic#include <algorithm>#include <bitset>#include <cassert>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>
2015-12-07 18:16:21
265
原创 POJ 1149 PIGS
题意mm个猪圈，nn个顾客 依次 购买bib_i头猪，会到某些猪圈买。 每次交易过程如下： 1. 顾客开某几个猪圈的门 2. 卖猪 3. 任意分配这几个猪圈的猪的数量 4. 锁门 猪圈可容纳的猪的数量没有限制 问最多能卖出多少猪？题解注意到此题有 依次 ，这个限制 而基于 依次 的建图方法，与两个元素是否 相邻 很有关系。建图如下： 1. s->第一个开某个猪圈的顾客连边，
2015-12-07 16:32:58
234
原创 URAL 1223 Chernobyl’ Eagle on a Roof
题意经典的蛋碎问题 现在有n个蛋，有相同的坚硬程度。 每次测试从一个任意的高度H往下扔， 如果蛋碎了，则其坚硬程度题解直接考虑非常困难，有下面的设法： f(i，j)f(i，j) 代表用i个蛋砸j次可以确定的最大楼层数 边界初值显见f(1,i)=if(1,i)=i f(0,i)=0f(0,i)=0 f(i,0)=0f(i,0)=0 f(i,1)=1f(i,1)=1 对于(i,j)，
2015-12-07 10:12:21
311
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人