4 zipper112

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 15w+

机器学习--梯度下降法

基本原理假设有一个函数,想要寻找的它的极值,该如何得出呢?最直观上可以直接使用公式得出。但是有时用公式计算的速度可能并不快,比如使用正规方程解出当前样本的最佳拟合直线,这个的计算量就很大,而且有时有些函数可能没法找到一个合适的公式来直接得出,这时就需要用到梯度下降法了。高等数学中有这么一句话,沿着梯度方向下降/上升的速度最快。举个例子,比如二次函数,随意找一个点,沿着它的梯度方向(这里也就是导数)肯定是最快的。同时,可以发现,如果沿着梯度的反方向前进的话就可以逐渐的逼近极值。所以就可以大概的

2020-10-15 19:31:32

几道置换群题目

最近学了置换群,然后就想着写几道POJ - 1026 CipherVJ题意:题目意思是给一个置换,然后给一些字符串和一个整数k,要求对这些字符串进行k次置换思路:非常基础的题,要求置换k次,那么就把置换中的每一个环向右转k−1k - 1k−1次,然后再置换即可。代码:这里我写复杂了#include<cstdio>#include<algorithm>#include<vector>#include<iostream>#include&

2020-10-10 13:25:41

置换群

参考的资源:oiwiki-置换群置换群快速幂运算+研究与探讨-潘振浩建议至少先把OIWIKI的基础内容看了置换的概念按照oiwiki的说法,置换是一种有限集合到自身的双射。如果不懂,可以粗略的理解为以是一种数组下标到下标的映射。置换的表示p1,p2,p3...pnp_1,p_2,p_3...p_np1​,p2​,p3​...pn​其中pip_ipi​为下标,这种表示的意思是把原本第iii个位置的数换成原本的第pip_ipi​位置的数f=(a1,a2,...anap1,ap2...apn)f

2020-10-10 13:25:25

KMP算法

把之前的kmp博客删了,现在重新写一下kmp暴力字符串的匹配假设给两个字符串s和p,要求查询s是否在p中出现过,那么该如何进行进行实现呢?朴素的想法是从每次枚举p在s中的开始位置然后开始暴力向后匹配,每次匹配失败后就直接从下一个s的位置开始继续匹配。这种做法很容易想到,但是仔细一算就可以发现很耗时。假设s和p分别长为n和m那么这样匹配最差情况下大概是O(n∗m)O(n*m)O(n∗m)级别。KMP字符串匹配KMP匹配实际上是对暴力匹配的改进。假设P在和S匹配时匹配失败了(在下图蓝色后面处匹配

2020-10-08 08:17:30

Manacher(马拉车)算法&模板

简介Manacher算法可以在O(n)复杂度内解决一些回文串问题,例如求最长回文子串等。该算法由Manacher发明。思路Manacher预处理部分首先对于一个字符串,他的回文字串按长度可以分为偶数长度和奇数长度的回文子串,两种回文串的对称中心不同,这就可能会导致在处理时出现麻烦。所以要对字符串进行处理,把奇偶子串进行统一。比如:ababaManaher的做法是插入一些无关字符(比如#)#a#b#a#b#a#这样的好处很明显,对于偶数子串它的对称中心就会变成#,这样就可以在处理

2020-10-06 07:10:25

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

查看更多

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