【库废案】

1、collections.deque。2、sysgetrecursionlimitstdin。3、itertoolspermutationscombinations。4、functools。5、date、time、datetime、timedeltaΔdatetime.strftime()date.isoformat,weekday,toordinal,replace。6、heapq、string、turtle、bisect。赶时间的废案快开比了笔记排列组合是数学基本内容可以利用枚举、dfs、二进制等方法构造但itertools库也有封装好的permutations(iterable,rNone),combinations函数可以自动返回一个含有全排列组合迭代器Python组合是基于下标构造的对于序列中有重复元素会致使出现重复排列因为它认为这是两个元素所以需要人为去重需要注意的是由于计算了所有组合其算法复杂度为阶乘级别。例题洛谷1036选数笔记对拍是比赛常用的做题方法Python在构造随机数据上有着极大优势可以利用其生成随机输入数据弥补题目样例有限的不足批处理文件并通过做题提交代码与低效检算暴力代码分别生成输出数据再进行比对判定算法正确性random[0,1)内随机数uniform[a,b]内随机浮点choice随机在列表中选一元素sample选多个shuffle乱序string.ascii_letters与string模块的digits字母数字字符列表Windows环境对拍方式如下生成测试数据文件makedata.py用文件函数写入文件data.in或执行命令D:set pathC:\Users\hp\AppData\Local\Programs\Python\Python39路径以实际Python目录为准与命令D:python makedata.pydata.in用两种测试代码hash.py与bb.py执行命令D:python bb.pydata.inbb.out以实际自取文件名为准最后执行文件比较命令D:fc bb.out hash.out/n另附输入拓展Python的基本输入语句及其单一而不像Cscanf可以利用格式字符串进行输入有且仅有一个整行字符串输入函数input3版本需要我们利用map、split、eval、类型转换等函数进行复处理才能变为有效实际数据有时我们会遇到没有明确终止输入的要求我们可以采用sys.stdin迭代逐行或异常处理以及判定读入是否为空的方式终止循环。例题多组输入abNC22165笔记时间问题虽然相对简单且也属于低频杂题考点但掌握还是很有必要的time库对于时间操作过于简单而且只能在时间零点1970后起用更复杂的操作建议使用datetime库里面date、time、datetime、timedeltaΔ四个类可以更方便的处理时间问题标准库1、math1求余取模是数学基本运算在枚举等题目中常常因为答案过大或答案为分数精确度不足的情况要求对答案进行取模最大公约数与最小公倍数也用到了整除即余数为0的计算。通常GCD代码需要我们利用辗转相除法或更相减损术手写当然实际上math库里也有封装好的gcd函数在3.9版本后lcm也加入了库中无论因子正负Python的gcd结果一定为正gcd(0,0)0除外但是Python的求余与实际取余不同是向下对齐的实际a%ba-bfloor(a//b)故运算结果符号与除数b相同需要注意的是有时我们会遇到分数取模的要求除法取模可以转换为乘法取模具体为商模等于被除数与除数逆元积的模(a/b)modm(ab⁻¹)modm这里的逆元并非C,复数乘法代数系统的逆元即倒数而是整数模m运算的逆元其满足性质gcd(b,m)1时(bb⁻¹)≡1modm注a≡b(modm)当且仅当amodmbmodm即m|(a-b)也就是(a-b)%m0为真所以(bb⁻¹)≡1modm有(bb⁻¹-1)%m0可以解丢番图方程bxmy1得到x另模m最好是一个大于b的素数。例题hdu5976Detachment。2ceil向上取整。例题P22B13H技能提升2129。2、queue1Queue(maxsize1)队列。例题洛谷P1996约瑟夫问题。2PriorityQueue()优先队列。例题http://oj.ecustacm.cn/problem.php?id1721丑数。3、random1对拍是比赛常用的做题方法Python在构造随机数据上有着极大优势可以利用其生成随机输入数据弥补题目样例有限的不足批处理文件并通过做题提交代码与低效检算暴力代码分别生成输出数据再进行比对判定算法正确性random[0,1)内随机数uniform[a,b]内随机浮点choice随机在列表中选一元素sample选多个shuffle乱序。4、datetime1date、time、datetime、timedeltaΔ四个类datetime.strftime()date.isoformat,weekday,toordinal,replace。例题P21A12F时间显示1452。5、collections1deque双端队列。例题511机器翻译。6、sys1系统栈大小通常是有限定的如1000尤其Python栈通常很小虽然判题系统一般栈足够大但若递归recursion层数较多搜索较深栈溢出会发生错误getrecursionlimit函数可以获取限制的嵌套次数可以用set方法进行修改手工扩栈至30w甚至100w当然剪枝等减层方法仍是重要的。例题C23A14B有奖问答3497。2有时我们会遇到没有明确终止输入的要求我们可以采用sys.stdin迭代逐行或异常处理以及判定读入是否为空的方式终止循环。例题多组输入abNC22165。7、bisect1bisect_left(a,x,lo,hi,key)利用二分法使用key比较方式在顺序列表a[左端lo:右端hi]中寻找待插入元素x的合适插入坐标若是right返回最右侧换言之一般情况下a[i-1]x≤a[i]right则a[i-1]≤xa[i]特殊情况下即ilo时仅有x≤a[i]ihi时仅有a[i-1]xright则ihi时仅有a[i-1]≤xilo时仅有xa[i]。例题3539买二赠一。8、time1time库对于时间操作过于简单而且只能在时间零点1970后起用。9、itertools1permutations(iterable,rNone),combinations函数可以自动返回一个含有全排列组合迭代器Python组合是基于下标构造的对于序列中有重复元素会致使出现重复排列因为它认为这是两个元素故需人为去重需注意的是由于计算了所有组合其算法复杂度为阶乘级别。例题洛谷1036选数。10、heapq1堆push,pop。例题洛谷P3045奶牛优惠券。11、基本库1string.ascii_letters与string模块的digits字母数字字符列表hex、oct十六八进制atan2坐标反正切hypot欧几里得范数radians、degrees角弧度d.copy()浅复制os.path、转换数学三角随机字符列表元组字典时间。12、turtle1forwardfd、backbk、rightrt、lt、done。13、functools等1map、filter过滤、reduce累积、zip。14、魔术1add、rmul*、lt、legt、eqne、getitem、attr iblue、sub-truediv/neg-int。