4 zipper112

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 16w+

47. 全排列 II

开始在力扣上写一些题,由于以前经常用的是C++但是以后会经常用Python,鉴于我Py的基础本身不扎实,所以觉着有比较记录一下自己的错误(题目:链接首先直接可以想到的就是暴力,可以dfs,然后每次从list中选择一个字符并删除,最后得到所有排列再用set去重。list不能进行hash,所以我就想着转str由于受之前numpy的影响,导致我认为list的切片也是原list的引用,但事实上并不是Py可以写内部函数,这样可以简化代码list转str很费时间class Solution:

2020-09-18 22:11:36

ST表

非常小巧好用的数据结构,在处理静态的RMQ非常有力思想思想就是伟大的 倍增思想,O(nlogn)O(nlogn)O(nlogn)的预处理O(1)O(1)O(1)的查询。预处理设数组maxx[i][j]maxx[i][j]maxx[i][j]为从i开始长度为2j2^j2j的区间内的最大值那么maxx[i][j]=max(maxx[i][j−1],maxx[i+2j−1][j−1])maxx[i][j] = max(maxx[i][j - 1], maxx[i + 2^{j - 1}][j-1])ma

2020-09-05 14:51:45

D. Maximum Distributed Tree(Codeforces Round #665 (Div. 2))

思路题意就不说了。首先看这个式子,∑i=1n−1∑j=i+1nf(i,j)∑\limits_{i=1}^{n−1}∑\limits_{j=i+1}^nf(i,j)i=1∑n−1​j=i+1∑n​f(i,j)可以发现,其实就是所有的点对都连了一遍,也就是任意两个点都不重复的连了一遍。那么假设有一条边L,L左边有xxx个节点,那么L右边一定就有n−xn-xn−x个节点,那么通过L的次数就是(n−x)x(n -x)x(n−x)x那么只需要dfs一遍就可以算出所有边的经过次数了。然后对于给的m个质数需要分情

2020-08-22 14:05:28

机器学习--线性回归

简介简单线性回归可以用于解决据有线性关系数据的回归问题,线性回归的英文名是:Linear Regression算法思路高中课本讲过一个东西叫做线性回归,在高考中曾经也考过。回忆一下当时的题目,都是给出一些散点,然后让你套公式求出一条直线,然后这条直线就可以很好的拟合这些点。怎么才算很好的拟合呢?假设有一些如下的点,我们拟合出一条直线,那么该怎么评判这条直线的好坏呢?设直线方程为y=ax+by = ax + by=ax+b,假设有一个点为(x(i),y(i))(x^{(i)},y^{(i)})(x

2020-08-21 09:02:29

基础算法-快速排序

算法过程快排的基本思想是分治,每次都把一个大规模的问题转化成相同形式的小规模问题。选取标定点,常取中间点或者左右边界点把小于标定点的点放在标定点左边,大于标定点的点放在右边递归处理标定点左右两边简单的来说就是每次找到一个点,然后以这个点为边界把所有的点进行分类分到左右两边,然后递归处理。代码实现void qsort(int l, int r, int p[]){ if(l >= r)return;//只剩一个点或者边界不正确时直接退出 int x = p[(l + r

2020-08-17 10:03:07

FFT模板+题目

#include<iostream>#include<cstdio>#include<cmath>using namespace std;const int MAXN=1e7+10;const double Pi=acos(-1.0);struct complex{ double x,y; complex (double xx=0,double yy=0){x=xx,y=yy;}}a[MAXN],b[MAXN];complex oper

2020-08-14 17:27:52

机器学习--KNN算法

最近开始正式学机器学习的算法了,按照我的习惯学每个新的算法都喜欢记笔记,刚开始可能会有很多错误的地方如果大家发现了还请多多指正文章目录KNN简介:算法的思路简单的实和sklearn的中的KNN的简单使用简单的实现sklearn的中的KNN的简单使用导入数据集使用KNN分类精确度分离数据手动分离使用sklearn分离精确度超参数KNN简介:KNN算法属于分类算法,英文名称为K-NearestNeighbor,直译过来就是K个最的邻居。他可以通过计算并找到要预测的数据和训练数据中前K个最近的数据,然后对他

2020-08-13 23:01:31

费马小定理&欧拉定理&扩展欧拉定理(欧拉降幂)

费马小定理定理:若ppp为质数且ppp和aaa互质那么就有ap−1≡1(mod  p)a^{p - 1}\equiv1(\mod p)ap−1≡1(modp)证明:ap=(a−1+1)pa^p = (a - 1 + 1)^pap=(a−1+1)p然后二项式展开ap=(a−1)p+Cp1(a−1)p−1+...+1a^p = (a - 1)^p + C_{p}^1(a - 1)^{p -1} + ...+1ap=(a−1)p+Cp1​(a−1)p−1+...+1由于Cpi=p!i!(p−i)!,

2020-08-04 17:07:26

Python--类属性,实例属性,类方法,静态方法

类属性&实例属性类属性类属性属于所有对象共有的,也就是所有对象都会使用同一个类属性,类属性定义在类的内部。类属性可以直接通过类名调用,修改类属性则所有对象使用时就都会改变。class Student: name = 'chiruno'#类属性 height = 1.56obj1 = Student()# 实例对象obj2 = Student()print(obj1.height)# 通过实例调用类属性print(obj2.height)Student.heigh

2020-08-02 10:41:31

F Fraction Construction Problem

题意:给两个数a,b求另外四个数c,d,e,f满足cd−ef=ab\frac{c}{d} - \frac{e}{f} = \frac{a}{b}dc​−fe​=ba​d < b and f < b1≤c,e≤4×10121≤c,e≤4×10^{12}1≤c,e≤4×1012如果不存在就输出-1 -1 -1 -1思路:看了题解之后来写一下思路,当时做一个笔记。...

2020-07-25 09:43:20

置换(群)&(J Just Shuffle)

牛客上多校第二场的J题,下来补的时候发现要置换群,于是就来学了,然后就想着记个笔记。置换(群)置换先说置换是啥对于一个n个元素集合S={a1,a2...an}S = \{a_1,a_2...a_n\}S={a1​,a2​...an​},排列P={p1,p2...pn}P = \{p_1,p_2...p_n\}P={p1​,p2​...pn​},将排列P每个元素当做S的下标替换掉原本S每个元素的位置,就得到一个置换f={ap1,ap2...apn}f = \{a_{p_1},a_{p_2}...a_{

2020-07-20 23:05:32

Python-列表推导式&生成器

列表推导式格式:list1 = [生成元素的表达式 for 原列表的元素 in 原列表 if 需要满足的条件]使用:以下面代码为例子,可以看到最终的list1里存了所有list0中的偶数元素的平方。其运行的过程是,从list0中挨个取出元素存在变量i,然后判断i是否被2整除,如果被整除就执行最开始的表达式,即i * i,然后把这个元素放到新的列表中可以看做,列表推导式就是从旧的列表之中推出新的列表list0 = [2, 5, 6, 7, 4]list1 = [i * i for i in

2020-07-19 11:48:53

模拟哈希表&字符串哈希

模拟哈希表引入哈希表就是根据一个关键值key进行高效访问的数据结构,可以通过哈希函数把一个数据当做key进行映射得到一个储存地址从而进行访问。比如想要查询100个数字范围在(1 ~ 1e8),查询它们是否有重复的值,那么就可以用哈希表来解决这个问题。对于小的数字我们就会习惯的会去一个数组进行标记,但是对于大的数字,开一个很大数组用来标记是很浪费空间,而且要处理的数只有100个,开一个1e8的数组实在是划不来,而且当数据再增大时,对于C++可能就无法直接开出这样的数组。哈希函数此时就可以对此些数字

2020-07-17 16:25:36

二分图最大匹配(匈牙利算法&Dinic算法)

二分图最大匹配:给出一个二分图,左边有若干个节点,右边有若干个节点,左边的节点想到匹配右边的节点,每个左边的节点每个都有若干个可以选择的对象,每个左边节点只能选择一个右边节点,每个右边节点也只能被选择一次。现在问你左边的节点能完成匹配的做多能有几个?通俗一点就是,有一群人,有一堆奖品,每个人都有自己心仪的奖品,每种奖品只有一份,问你最多能有多少能拿到自己心仪的奖品(每个人只能拿一份,而且每个人可能有多重心仪的奖品)?匈牙利算法:匈牙利算法的做法就是,先让每个左边节点去匹配,如果存在没有被匹配到的右边

2020-07-16 15:52:10

最小割&费用流

最小割:对于一个网络流图,把整张图分割成两个部分,一部分包含源点,一部分包含汇点的分割方式叫做割。割的容量即切割边时所切去边的容量之和,其中使割的容量最小的割叫做最小割求法:一张网络流图的最小割等于它的最大流,至于怎么证明可以看一下这篇博客这里本人太菜就不证明了。既然知道了它们相等,那么就可以跑最大流的模板来找最小割了常见模型:小M的作物上面有一道题,里面就用到了一个最小割的模型,即二选一模型。这种模型大概就是,有一些点集可以被分到连个集合中,分到A花费为XXX,分到B花费为XXX。费用

2020-07-16 15:23:48

网络流-最大流(Ford-Fulkerson算法&Dinic算法)

#include<bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 1e5 + 5;int n,m,cnt = 2,h[maxn];int st,ed;bool vis[maxn];struct node{int w,e,nex;}e[maxn * 2];void add(int a,int b,int c){e[cnt].e = b;e[cnt].nex = h[a];e[

2020-07-14 10:13:34

Python--lambda表达式

lambda表达式就是一种函数,可以说是匿名函数。格式:lambda 参数1,参数2..参数n:表达式例子:fun1 = lambda a, b: a * bfun2 = lambda *args: args[0]fun3 = lambda a: a + 1 if a % 2 == 0 else a - 1fun4 = lambda x, y: print("这里:{}".format(x + y))print(fun1(3, 4))print(fun2(5, 4, 3))print(

2020-07-07 22:15:09

Dance Links(板子)

struct DLX{ int n, m, cnt; int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; int H[MAXM], S[MAXM]; int ansd; void init(int _n, int _m){ n = _n; m = _m; for (int i = 0; i <= m;

2020-07-07 09:16:36

Python-闭包&装饰器

闭包:闭包的格式:看下面一段代码def fun(a): b = 10 def inner_fun(): print(a + b) return inner_funx = fun(5)print(type(x))print(x)x()'''输出:<class 'function'><function fun.<locals>.inner_fun at 0x000001BB0CB02948>15'''

2020-07-04 21:38:45

双向BFS

作用双向BFS本质还是bfs,不过是在已知起点和终点的状况下从起点和终点两头开始bfs,这样可以节省时间避免单bfs时所带来的组合爆炸,而且在解决起点和终点均可移动且移动速度不同等鬼畜问题时有奇效模板#include<bits/stdc++.h>#define ll long longqueue<类型> qu[2];bool bfs(int id){ int s = qu[id].size();//每次只扩展当前这一层 while(s--){

2020-07-03 10:23:47

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。