- 博客(4431)
- 收藏
- 关注
RSS订阅转载 手写朴素贝叶斯（naive_bayes）分类算法
朴素贝叶斯假设各属性间相互独立，直接从已有样本中计算各种概率，以贝叶斯方程推导出预测样本的分类。为了处理预测时样本的（类别，属性值）对未在训练样本出现，从而导致概率为0的情况，使用拉普拉斯修正（假设属性值与类别均匀分布）。代码及注释如下：一、离散值1，朴素贝叶斯算法计算相关参数并返回，预测使用这些参数即可# 手写拉普拉斯修正的朴素贝叶斯import numpy...
2019-10-03 05:43:00
765
转载 SVM之KKT条件理解
在SVM中，我们的超平面参数最终只与间隔边界上的向量（样本）有关，故称为支持向量机。求解最优超平面，即求最大化间隔，或最小化间隔的倒数：||w||2/2，约束条件为yi(wTxi+b)>=1因为此函数为凸函数（拉格朗日乘子法的前提条件），可用拉格朗日乘子法转化为对偶问题，当满足KKT条件时，对偶问题=原始问题。关于约束：1. 目标函数极值点在约束范围内：此时不等式约...
2019-10-02 11:10:00
628
转载 手写BP（反向传播）算法
BP算法为深度学习中参数更新的重要角色，一般基于loss对参数的偏导进行更新。一些根据均方误差，每层默认激活函数sigmoid（不同激活函数，则更新公式不一样）假设网络如图所示：则更新公式为：以上列举了最后2层的参数更新方式，第一层的更新公式类似，即上一层的误差来自于下一层所有的神经元，e的更新就是不断建立在旧的e上（这里g可以当做初始的e）下面上代码：1...
2019-10-01 21:02:00
866
转载 2019 ccpc 秦皇岛
D如果1/n是有限小数，不停乘以10，一定在有限次之后成为一个整数。10的质因子只有2和5，只要保证分母的质因子只有2和5即可#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorith...
2019-09-30 15:06:00
304
转载 决策树（基于增益率）之python实现
如图，为使用到的公式，信息熵表明样本的混乱程度，增益表示熵减少了，即样本开始分类，增益率是为了平衡增益准则对可取值较多的属性的偏好，同时增益率带来了对可取值偏小的属性的偏好，实际中，先用增益进行筛选，选取大于增益平均值的，然后再选取其中增益率最高的。以下代码纯粹手写，未参考其他人代码，如果问题，请不吝赐教。1，计算信息熵的函数import numpy as np# 计...
2019-09-30 00:38:00
377
转载 word2vec之tensorflow（skip-gram）实现
关于word2vec的理解，推荐文章https://www.cnblogs.com/guoyaohua/p/9240336.html代码参考https://github.com/eecrazy/word2vec_chinese_annotation我在其基础上修改了错误的部分，并添加了一些注释。代码在jupyter notebook下运行。from __future_...
2019-09-28 18:05:00
165
转载 2018 icpc 徐州
A矩阵树定理可以用于最小生成树计数，最直观的做法就是求个mst，再用矩阵树定理求最小生成树个数，但是n<=1e5，显然不是o(n^3)可以做出来的。考虑随机数据生成器，固定1e5的边，但是边权在unsigned long long的范围内随机指定，由样例看出，即使是点数很少的情况下，最多也只有一个生成树于是，我们猜测，只需要做一遍最小生成树，并假定不会有更多的生成树就可...
2019-09-25 23:25:00
189
转载 ORACLE数据库，Timestamp 的时间格式转换
1、字符型转成timestampselect to_timestamp(loga006,'dd-MON-yyhh:mi:ss.ff AM')from loga_t;2、timestamp转成date型selectcast(to_timestamp(loga006,'dd-MON-yyhh:mi:ss.ff AM')asdate) timestamp_to_d...
2019-09-25 10:41:00
415
转载 hdu6599 I Love Palindrome String
由样例可知，题目中求的回文串数量，其实是本质不同的回文串数量，这个可以直接用回文树来做。考虑前半段是回文串这个限制，这个东西回文树不好做，可以再套一个马拉车，然后记录一下插入到回文树的节点中最后一个字符的位置，使用马拉车快速判断这一段的前半段是不是回文串#include <iostream>#include <cstdio>#include &...
2019-09-23 21:51:00
208
转载 iOS 超级签名详解
一、原理把安装设备当做开发设备进行分发。说的明白一些，开发者可以在开发者后台添加手机的UDID，然后重新打包一个IPA文件，分发平台，然后被添加的UDID就可以下载。二、优缺点优势：直接分发，安装即可运行，不需要用户做企业证书的信任操作目前稳定，不会有证书吊销导致的业务风险(后续苹果政策风险非常高)缺点：单开发者账号的iPhone设备数量只有100个，导致...
2019-09-20 15:48:00
1095
转载 Codeforces Round #570 (Div. 3) B. Equalize Prices、C. Computer Game、D. Candy Box (easy version)、E. Su...
B题题意：给你n个物品的价格，你需要找出来一个值b，使得每一个物品与这个b的差值的绝对值小于k。找到最大的b输出，如果找不到，那就输出-1题解：很简单嘛，找到上下限直接二分。下限就是所有物品中最小的价格。上限就是所有物品中最大价格加上k代码： 1 #include<stdio.h> 2 #include<string.h>...
2019-09-20 10:22:00
128
转载 win10重置电脑后，创建用户名无法输入和开机一直提示系统准备工具3.14的处理办法...
电脑是联想的，系统是WIN10。前几天心血来潮，想要把电脑清理一下，本来想重装系统的，后来发现win10有一个“重置此电脑”的功能，可以满足我的需要，就用了这个功能，然后就产生了两个折腾了我两天的问题。。。要不是问题顺利解决了，我真的想骂自己手贱；记录一下这个过程，也许可以帮到遇到同样问题的人重置电脑的过程大家可以参考这个使用Windows 10设置菜单的重置此电脑选项会发生...
2019-09-20 10:20:00
17687
转载 Codeforces Round #575 (Div. 3) B. Odd Sum Segments 、C Robot Breakout
传送门B题题意：给你n个数，让你把这n个数分成k个段(不能随意调动元素位置)。你需要保证这k个段里面所有元素加起来的和是一个奇数。问可不可以这样划分成功。如果可以打印YES，之后打印出来是从哪里开始断开的。否则打印出NO题解：加上奇数可以使和的性质改变，原来使偶数则变为奇数，奇数则变为偶数。加上一个偶数就不会有这样的变化。所以第一步就找出来有多少个奇数。因为要保...
2019-09-18 08:34:00
109
转载 Codeforces Round #575 (Div. 3) F. K-th Path
传送门题意：这道题把我看得懵懵的(不敢相信)，其实就是给你n个点和m条边(无向图)，你要找出来任意两点之间的的最短距离，然后再从其中找出来第k个最小值题解：正常思维就是floyd多源最短路算法跑一遍，然后把任意两点之间的距离取出来放在数组里面，再排序。之后打印出第k个就可以了但是n的范围是2e5，然而数组开不了这么大的，所以这里有一点优化的。因为要求第k大的距离...
2019-09-18 08:14:00
92
转载 Codeforces Round #575 (Div. 3) E. Connected Component on a Chessboard
传送门题意：给你一个黑白相间的1e9*1e9的棋盘，你需要从里面找出来由b个黑色的格子和w个白色的格子组成的连通器(就是你找出来的b+w个格子要连接在一起，不需要成环)。问你可不可以找出来，如果可以就先打印YES，再打印出所有格子的坐标，否则打印出NO。题解：参考博客如果b和w相等的时候，那么就可以用棋盘的一行来表示。对于不相等的情况：如果ma...
2019-09-17 10:43:00
89
转载 windows 右下栏 WIFI不显示 红叉
转载于:https://www.cnblogs.com/LandingGuy/p/11530639.html
2019-09-16 22:13:00
191
转载 使用console.log打印的内容不一定可信
在工作中遇到，使用console.log()输出对象信息时，出现输出的信息跟自己想的不一样的问题，导致调试bug时，思路走偏。当时参考了别人的issues已经讲的很清楚了。这里自己再记录一下问题描述：即使我直接在赋值语句const obj = {age: 20}后面紧跟console.log(obj)，在浏览器的控制台，看到的也不一定的age字段，也不一定是20。因为，如果...
2019-09-16 20:44:00
398
转载 Codeforces Round #575 (Div. 3) D2. RGB Substring (hard version)
传送门题意：给你一个长为n的仅由'R','G','B'构成的字符串s，你需要在其中找出来一个子串。使得这个子串在“RGBRGBRGBRGB........（以RGB为循环节，我们称这个串为str）”里面也是一个子串，这个子串的长度是k可是有可能s字符串中找不到，那么这个时候就可以改变s字符串中某些位置的字母来完成任务。问最少需要改变多少个字母题解：主要看暴力的姿...
2019-09-16 20:40:00
94
转载 2018 icpc 沈阳
https://codeforces.com/gym/101955J签到#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<string>#include <set>#...
2019-09-15 21:24:00
162
转载 Codeforces Round #582 (Div. 3) A. Chips Moving
传送门题解：给你n个数的坐标，你需要把他们移动到一个位置，有两种移动方式1、向左或者右移动22、向左或者右移动1，但是耗费1求最小耗费题解：很简单就可以想到，看一下偶数坐标多还是奇数坐标多减一加一改变奇偶性，但是减二加二不改变代码： 1 #include<stdio.h> 2 #include<string...
2019-09-14 15:54:00
88
转载 Codeforces Round #582 (Div. 3) C. Book Reading
传送门题意：给你n，k。表示在[1,n]这个区间内，在这个区间内找出来所有x满足x%k==0，然后让所有x的个位加到一起(即x%10)，输出。例如：输入10 2那么满足要求的数是2 4 6 8 10那么2%10+4%10+6%10+8%10+10%10=20那么就输出20题解：满足x%k==0的x，肯定是k与某个因数y的乘积，即1*k,2*k,3*k...
2019-09-14 15:48:00
82
转载 Codeforces Round #582 (Div. 3) F. Unstable String Sort
传送门题意：你需要输出一个长度为n的字符序列(由小写字母组成)，且这个字符串中至少包含k个不同的字符。另外题目还有要求：给你两个长度为p和q的序列，设字符序列存在s中那么就会有s[Pi]<=s[P(i+1)] (i<p) s[Qi]<=s[Q(i+1)] (i<q) 如果你能找出来满足这些条件的字符串s，就输出YES和s...
2019-09-14 15:33:00
85
转载 牛客小白月赛17 A 小sun的假期
传送门题意：第一行两个数n,m，代表总共有n天，m个安排。接下来有m行，每行是一个安排l,r，代表从第l天到第r天，小sun有安排了。安排可能会重复。小 sun 非常喜欢放假，尤其是那种连在一起的长假，在放假的时候小 sun 会感到快乐，快乐值等于连着放假的天数，现在小 sun 把他的安排表告诉你，希望你告诉他在他的安排表中， 他的最大快乐值。 当某天没有安排的时候就是放假...
2019-09-14 13:08:00
157
转载 牛客小白月赛17 A 小sun的假期
题意已经很明显了，但是我首先是用暴力方法先把数字离散，再用离散后的值当下标来存这个数字出现了几次 1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 #include<map> ...
2019-09-14 12:55:00
217
转载 牛客小白月赛17 G 区间求和
传送门题意：题解：原本想着使用暴力方法： 1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 #include<map> 6 using namespac...
2019-09-14 12:43:00
91
转载 CodeForces 731C Socks 并查集
1 //题意：有n只袜子，m天，k个颜色，每个袜子有一个颜色，再给出m天，每天有两只袜子，每只袜子可能不同颜色， 2 //问要让每天的袜子是相同颜色的，要重新染色的袜子数最少是多少。 3 // 4 //这里要注意一点，就是他是一次处理完，之后不会继续染色。这就意味着像 5 //4 3 2 6 //1 1 2 2 7 //1 2 8 //2 3 9 /...
2019-09-11 19:39:00
164
转载 Slim Span POJ 3522 （最小差值生成树）
题意：最小生成树找出来最小的边权值总和使得n个顶点都连在一起。那么这找出来的边权值中的最大权值和最小权值之差就是本题的结果但是题目要求让这个输出的结果最小，也就是差值最小。那么这就不是最小生成树了题解：思路1、让所有边这个权值从小到大排序，之后一个权值一个权值的枚举，枚举那个权值就证明我们肯定会用到这个权值，然后让这个权值和其他边的权值做差用这个差来代替原来...
2019-09-11 17:39:00
143
转载 [POJ 2585] Window Pains 拓朴排序
题意：你现在有9个2*2的窗口在4*4的屏幕上面，由于这9这小窗口叠放顺序不固定，所以在4*4屏幕上有些窗口只会露出来一部分。如果电脑坏了的话，那么那个屏幕上的各小窗口叠放会出现错误。你的任务就是判断一下这个电脑到底坏了没有。题解：要注意1.2.3....9这几个窗口的位置是不变的，它只会被其他窗口挡住刚开始我想的是，让这9个窗口叠放的顺序枚举一下，记录下来它...
2019-09-11 17:27:00
106
转载 Keras之注意力模型实现
学习的一个github上的代码，分析了一下实现过程。代码下载链接：https://github.com/Choco31415/Attention_Network_With_Keras代码的主要目标是通过一个描述时间的字符串，预测为数字形式的字符串。如“ten before ten o'clock a.m”预测为09:50在jupyter上运行，代码如下：1，导入模块，好像并没...
2019-09-10 11:05:00
2269
转载 POJ 2594 Treasure Exploration 最小可相交路径覆盖
最小路径覆盖DAG的最小可相交路径覆盖：算法：先用floyd求出原图的传递闭包，即如果a到b有路径，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。这里解释一下floyd的作用如果1->2->3->4那么1可以到达2，3，4只要需要借助一些点，那么就可以直接把1与2，3，4相连，这就是floyd要做的事。证明：为了连通两个点，某条路径可能...
2019-09-09 21:38:00
133
转载 hdu 1045 Fire Net 二分图匹配 && HDU-1281-棋盘游戏
题意：任意两个个‘车’不能出现在同一行或同一列，当然如果他们中间有墙的话那就没有什么事，问最多能放多少个‘车’代码+注释： 1 //二分图最大匹配问题 2 //难点在建图方面，如果这个图里面一道墙也没有，那么可以说就是在横坐标（1...n）和纵坐标(1...n) 3 //中个挑选出来一个，那个点就是我们要放置炮台的地方，么个点只能用一次，这样就能保证正确性 4...
2019-09-09 21:12:00
127
转载 HDU 3488-Tour KM
为什么可以这样拆点在 这道题 都已经证明过代码： 1 //题目上面说了“The only exception is that the first and the last city should be the same and this city is visited twice.” 2 //我还以为是起点要使用两次，没想到题意就是全部点连接之后出入度都为1 3...
2019-09-09 20:40:00
105
转载 二分图最大权匹配问题&&KM算法讲解 && HDU 2255 奔小康赚大钱
作者：logosG链接：https://www.cnblogs.com/logosG/p/logos.html （讲解的KM算法，特别厉害！！！）KM算法：现在我们来考虑另外一个问题：如果每个员工做每件工作的效率各不相同，我们如何得到一个最优匹配使得整个公司的工作效率最大呢？这种问题被称为带权二分图的最优匹配问题，可由KM算法解决。比如上图，A做工作a...
2019-09-09 20:36:00
188
转载 HDU -1151 二分匹配与DAG图
题意：t组输入。每组数据第一行代表有n个城市，第二行表示有m个街道，而且这些街道都是单向的,它是一个DAG图（有向无环图），每次你派到一个城市一个机器人，它就会沿着道路走下去，你只需要用最少的机器人把所有城市都走一遍就可以了。问你最少多少个机器人题解：那么很显然像1->2->3->4这样的图，只需要一个机器人就可以了。我们这个时候可以利用拆点就是把{1...
2019-09-09 20:11:00
140
转载 POJ 3189
题意：给你B个谷仓和n头牛，每个谷仓最多容纳m头牛。此时每头牛对每一个谷仓都有一个喜悦值，你需要把每一头牛都安排某个谷仓内，并且找出来那个每一头牛对它所住的谷仓打的分值，我们对这所有的分值取一个区间，使这个区间包含这每一个值。并且尽量使这个区间小一点。题解：对着区间的两个端点[l,r],先让l==r==1，之后如果在区间[l,r]中分配不成(就使用二分图多重匹配算法来判...
2019-09-09 19:52:00
66
转载 POJ_2112 二分图多重匹配
题意：//题意就是给你k个挤奶池和c头牛，每个挤奶池最多可以来m头牛，而且每头牛距离这k这挤奶池//有一定的距离，题目上给出k+c的矩阵，每一行代表某一个物品距离其他物品的位置//这里要注意给出的某头牛和某个挤奶池的距离有可能不是最短的，所以这里要用最短路//来找出来某个物品到其他物品的最小距离，题目上要求出来在满足每头牛都能到达挤奶池的情况下//使所有牛中到达挤奶池中的最大值尽量小...
2019-09-09 17:33:00
88
转载 二分图多重匹配问题
解决什么问题：二分图最大匹配要求每个顶点只使用一次，即一连一。那么多重匹配就是解决一连多的问题的。比如给你n个联系人，你要把他们分在m个 组里面，给你每一个联系人可以放在那个组里面。再给你一个限制条件——每个组里面最多可以放入多少人，问你可不可以分组成功解决方法：二分图多重匹配分为二分图多重最大匹配与二分图多重最优匹配两种，分别可以用最大流与最大费用最大流解决。...
2019-09-09 17:25:00
556
转载 2019 Nanchang Onsite
D.Interesting SeriesF(n)实际上是一个等比数列的和，将它从递推式转变为通项公式(a^n-1)/(a-1)，这里只需要确定n就可以。题目要求选取k大小的所有子集的答案求和，可以先求a^n部分的和，把它写成母函数的形式(x+a^s1)(x+a^s2)...(x+a^sn)，这样不断的分成两半，分别求出，然后再用fft卷积合并这两半，这一部分的和就是x^(n-k)...
2019-09-09 16:23:00
150
转载 二分图匹配问题
一、二分图基础：参考链接：https://blog.csdn.net/jeryjeryjery/article/details/79596922 https://www.cnblogs.com/penseur/archive/2013/06/16/3138981.html什么叫二分图：给你一些点，其中这些点之间的某两个点是相连的。如果你可以把全部点分成两个集合...
2019-09-09 16:20:00
77
转载 一般图最大匹配带花树
参考博客：http://blog.sina.com.cn/s/blog_95ec9e7401018bga.html https://www.cnblogs.com/owenyu/p/6858508.html用Dinic实现的二分图匹配的时间复杂度其实是O(M*N^0.5)，这也许能够解释为什么一般网络流算法比Hungry要快了。另外，带花树算法的正确性的证明比较困难；...
2019-09-07 21:32:00
99
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人