- 博客(363)
- 收藏
- 关注
RSS订阅
原创 补题清单
Codeforces Round #364 (Div. 2) FBestCoder Round #84 EBC2周年 D2016 Multiset 1 C 2016 Multiset 1 G 2016 Multiset 1 H 2016 Multiset 1 I 2016 Multiset 1 J 2016 Multiset 1 K2016 Multiset 2 C 2016 Mult
2016-07-24 14:12:34
385
原创 概率论
随机试验 在相同的条件下重复进行。试验的全部结果提前知道不能预言出现的结果事件 随机试验的可能结果。必然事件不可能事件基本事件：最小的单位事件。(抛硬币，正反)复合事件：若干个基本事件的组合。样本空间：{样本点}，每个样本点对应基本事件。样本点：无限多或有限多->样本空间：有限或者无限。Venn图(文氏图)A∩B=ABA∩B=AB A\cap ...
2018-07-09 20:47:27
679
原创 LeNet-5网络结构解析
参考文章: 文章1 文章2 文章3特殊性神经元间的连接是非全连接的同一层中某些神经元之间的连接的权重是共享的（即相同的）权值共享 使用同一个Kernel池化 转:http://blog.csdn.net/geekmanong/article/details/50605340CNN的池化(图像下采样)方法很多：Mean pooling(均值采样)、Max pooling(最大值采样)、
2017-03-14 15:38:31
20617
3
原创 svm
优点:泛化错误率低，计算开销不大，结果易解释缺点:对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。适用数据类型：数值型和标称型数据。拉格朗日乘子法求在约束条件gj(x1,x2,...,xn)=0g_{j}(x1,x2,...,xn)=0的条件下,求f(x1,x2,...,xn)的极值f(x1,x2,...,xn)的极值引进拉格朗日乘子aa;建立方程 L(x1,x2,..
2017-03-12 21:29:22
858
原创 caffe mnist训练
1.数据集的准备在caffe根目录下运行./data/mnist/get_mnist.sh #获得mnist数据训练的四个数据包./examples/siamese/create_mnist_siamese.sh #将mnist date转化为可用的lmdb格式的文件,并将新生成的2个文件mnist-train-lmdb 和 mnist-test-lmdb放于create_mnist.sh同
2017-03-09 19:22:42
867
原创 svm
train_test_split功能是从样本中随机的按比例选取train data和test data。 **X_train, X_test, y_train, y_test = cross_validation.train_test_split(train_data,train_target, test_size=0.4, random_state=0)**test_size是样本占比
2017-02-12 16:59:23
364
原创 python训练
1001. A+B Formatformat的巧妙运用a,b = input().split()print('{:,}'.format(int(a)+int(b)))1002. A+B for Polynomials总结:字典的排序 sorted(iterable,key=None,reverse=False)sorted(iterable, key=None, reverse=False)
2017-01-29 13:09:28
442
原创 python学习笔记
if name == ‘main‘: name 是当前模块名，当模块被直接运行时模块名为 main 。这句话的意思就是，当模块被直接运行时，以下代码块将被运行，当模块是被导入时，代码块不被运行。 字典类似map,形成key-value(key可以是字符串，元组等，不能为可变的)创建方式:{key1:value1,…,keyn:valuen}利用dict函数字典无序存储两个列表组成字典:
2017-01-18 16:14:24
230
原创 python错误记录
错误:import urllib r = urllib.urlopen(‘http://z.cn/‘) html = r.read() print(html) 提示信息:AttributeError: module ‘urllib’ has no attribute ‘urlopen’ 解决方法: 用具体的urllib.request模块来调用它 import
2017-01-17 20:32:18
332
原创 编译原理总结
程序语言的基本知识符号串集合的运算A+B(A∪B)={w|w∈A,or w∈B} A+B(A \cup B) = \{w | w ∈ A , or \ w ∈ B \} A∗B(AB)={xy|x∈A and y∈B} A*B(AB) = \{xy | x ∈ A \ and \ y∈ B \}A0={ε},An=An−1A A^{0}=\{ \varepsilon \}
2016-12-16 15:28:38
1948
原创 BestCoder Round #82 (div.2)
A. ztr喜欢研究数学，一天，他在思考直角三角形方程组的Lower版，即n=x^2-y^2,，他想知道，对于给出的n，是否会有正整数解。 有T组数据,(T<=10^6),n<=10^18 思路: n=x^2-y^2=(x+y)(x-y),假设x+y=a,x-y=b,如果a+b的和可以凑成偶数而且a < b,那么一定能因式分解, 所以如果当n为奇数时,除了1之外,一定能凑成a=n
2016-12-07 19:05:25
332
原创 Codeforces Round #362 (Div. 2) F. Legen...(AC自动机+矩阵快速幂)
题意: 我们有n（200）个特殊单词，总长度不超过200。 我们要构造一个长度为l（1e14）的字符串。 如果字符串每包含一个给定单词i（可重叠匹配），则我们的权值计数+a[i] 问你最大可以得到的权值 思路: 对自动机上的状态,我们可以建立状态之间的转移可以获得的权值 ->对建立好之后的矩阵跑快速幂#include<cstdio>#include<algo
2016-11-09 16:57:08
362
原创 sgu 390 购票(上下界数位dp)
有一位售票员给乘客售票。对于每位乘客，他会卖出多张连续的票，直到已卖出的票的编号的数位之和不小于给定的正数K。然后他会按照相同的规则给下一位乘客售票。 初始时，售票员持有的票的编号是从L到R的连续整数。请你求出，售票员可以售票给多少位乘客。 数据规模：1 ≤ L ≤ R ≤ 10^18，1 ≤ K ≤ 1000。 思路: 此题需要上下界进行数位dp,且需要从小的开始放 dp
2016-11-08 17:05:08
494
原创 Hdu 5803 Zhu’s Math Problem(非记忆化数位dp)
思路: 数位dp,我们对每个数都拆分为二进制,对于数的每一位都进行考虑,可以发现 如果a+c-b-d<=-2则一定不满足,a+c-b-d有用的值肯定小于等于2,对另外一个不等式也是如此考虑 需要注意的一点的本题采用非记忆化搜索,因为有四个上界,四个都不为上界的情况会比较少#include<bits/stdc++.h>using namespace std;const in
2016-11-07 21:40:31
458
原创 Hdu 5921 Binary Indexed Tree(长春数位dp)
题意：用树状数组维护一个序列,在给区间[l,r]加上一个t的时候,要给[1,r]加上t,给[1,l−1]减去t,两次操作后值真正发生变化的节点个数就是这一次区间修改的代价，现在要修改每一个[1,n]的子区间,求总代价 对10^9+7取模后的结果。#include<bits/stdc++.h>using namespace std;const int MOD=1e9+7;int dig
2016-11-07 20:30:19
654
原创 ural 1057 Amount of Degrees(数位统计)
求给定区间[X,Y]中满足下列条件的整数个数:这个数恰好等于 K 个互不相等的 B 的整数次幂之和。(1<=X<=Y<=2^31-1,1<=K<=20,1<=B<=10) 思路: ans=Count(Y)-Count(X-1) 若一个数中有一个B进制的系数大于1->将这之后的系数均置为1#include<cstdio>#include<cstring>#include<iostr
2016-11-07 14:03:29
322
原创 BZOJ 1833: [ZJOI2010]count 数字计数(在[a,b]中的所有整数中，每个数码(digit)各出现了多少次)
题意: 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 思路: 一维数位dp,需保留之后的数的总方案数,以及每个digit的,注意前导0的特判#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;int dig[
2016-11-05 21:47:41
1256
原创 HDU 5069 Harry And Biological Teacher(fail树+线段树优化)
题意: 有n个字符串(n<=100000),总长度小于等于1e5,有m次查询,X,Y,问第X个的后缀和第Y个的前缀的最长公共子串 思路一: 总体思路 构造fail树,dfs序 按Y排序 X最后一个对应在字典树中的位置 首先，我们可以找到a在自动机上所对应的节点，考虑ac自动机的fail指针，那么从这个节点，往上一直到根的链上， 所有的节点所包含的子串，
2016-11-04 20:27:47
421
1
原创 BZOJ 2434: [Noi2011]阿狸的打字机(fail树+树状数组)
题目大意：初始字串为空，首先给定一系列操作序列，有三种操作： 1.在结尾加一个字符 2.在结尾删除一个字符 3.打印当前字串 然后多次询问第x个打印的字串在第y个打印的字串中出现了几次 思路: 构造出fail树,dfs序标号,查询按y排序,树状数组单点修改区间查询#include<cstring>#include<algorithm>#include<cstri
2016-11-04 20:22:03
309
原创 BZOJ 3172: [Tjoi2013]单词(fail树)
题意: 一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。 思路: ac自动机的本质如果一个串是另外一个串的子串,那么这个串是另外一个串的前缀的后缀,即另外一个串通过不停地fail指针可以移动 到这个串的末尾 知道了这个理论,那么其实fail指针就是一棵树,求这个串总共出现多少次->这个节点的子树的大小(通过循环传
2016-11-04 14:29:56
307
原创 Hdu 4008 Parent and son(给你一棵树(n<=1e5),有Q次查询,每次输入X Y,意思是以X为根,输出Y的儿子节点中节点标号最小和子树中标号最小)
题意: 给你一棵树(n<=1e5),有Q次查询,每次输入X Y,意思是以X为根,输出Y的儿子节点中节点标号最小和子树中标号最小 思路: 树形dp 先以1为根 处理出每个子树的最大值和次大值以及每个儿子节点对应的最大值和次大值 处理出每个点向上的最小值 以1建树就可以不用处理(Y等于1时需要特判) 处理出dfs序 分X的dfs在Y的dfs区间之内和
2016-11-03 21:06:45
1842
原创 Codeforces Round #135 (Div. 2) D. Choosing Capital for Treeland(从每个点出发最小需要修改几条边的方向可以到达其它所有点,输出最小改变几)
题意: 有n个点的树(n<=2e5),每条边定向,问从每个点出发最小需要修改几条边的方向可以到达其它所有点,输出最小改变几条边, 以及对应点 思路: 先不给树定向,向下dfs,向上dfs判断#include<bits/stdc++.h>using namespace std;const int N=2e5+100;struct Edge{ int to,next,
2016-11-03 21:04:31
296
原创 AIM Tech Round 3 (Div. 1) C. Centroids(每个点能否删掉一条边再添加一条边使得这个点成为重心)
题意: 给你n个点的树(n<=4e5),对于每个点能否删掉一条边再添加一条边使得这个点成为重心(每一个子树的大小都小于等于n/2) 思路: 对于每个点u,判断有多少个子树的大小大于n/2 每个子树维护这个子树中节点数小于等于n/2的最大值,次大值以及它们对应的节点 向上和向下dp一下就可以了#include<bits/stdc++.h>using namespace
2016-11-03 21:02:41
548
原创 Codeforces Round #263 (Div. 1) B. Appleman and Tree(给一棵树，每个点为白色或黑色，切断一些边，使得每个连通块有且仅有一个黑点，问划分方案数。)
题意：给一棵树，每个点为白色或黑色，切断一些边，使得每个连通块有且仅有一个黑点，问划分方案数。(n<=1e5) 思路: dp[u][0]表示没有被包含在黑色连通块中 dp[u][1]表示被包含在黑色连通块中 dp[u][0]=dp[u][0]*dp[v][1]+dp[u][0]*dp[v][0] dp[u][1]=dp[u][0]*dp[v][1]+dp[u][1]*dp[
2016-11-03 14:21:16
1885
原创 uva 12093 Protecting Zonk(在某个节点X使用A装置，此时与节点X相连的边都被覆盖)
题意: 有一个n(n<=10000)个节点的无根树。有两种装置A,B,每种都有无限多个。 1.在某个节点X使用A装置需要C1(C1<=1000)的花费,并且此时与节点X相连的边都被覆盖 2.在某个节点X使用B装置需要C2(C2<=1000)的花费,并且此时与节点X相连的边以及与节点X相连的点相连的边都被覆盖 求覆盖所有边的最小花费 思路: dp[u][0]:u没有安装
2016-11-03 14:19:42
1009
2
原创 BZOJ 3631 松鼠的新家
题意: 有一棵树,n个节点,从a1出发->a2->a3->…->an,(a为一个排列),每经过一个节点时,该节点加一,问最终每个节点的值 思路: 类似差分,lca(u,v)+1,u-1,v-1,从上往下统计答案就可以了 u+1,v+1,lca(u,v)-1,fa[lca[u,v]]-1,从下往上扫描#include<cstdio>#include<algorithm>#
2016-11-03 08:53:51
271
原创 UVALive 4015 Caves(树型dp)
题意:一颗有n个节点的有根树,有Q个查询,从根节点出发,走不超过x单元距离,最多能经过多少个节点,点可重复走(n<=500,Q<=1000) 思路: dp[u][k][flag]从u出发,经过k个点,是否回到u的距离的最小值 查询时暴力就可以#include<bits/stdc++.h>using namespace std;const int INF=0x3f3f3f3f;c
2016-11-02 20:20:26
305
原创 Hdu 5915 The Fastest Runner Ms. Zhang(环套树)
题意: 有一个n个点n条边的树,确定S,T,使得从S出发经过所有点最终到T，记长度为t,使得(t,S,T)的字典序最小思路: 环套树,破环成树 1.起点终点在同一个子树上,[S,T]上的边只走一次,环上的边只走一次2.起点和终点在不同的子树上,起点到U,终点到V只走一遍,环上U,V之间只走一遍,其余的边都走两遍 设置一个环上的起点,其余的点到这个点的距离设为dis[x] 则长度为2*
2016-11-01 16:11:54
751
原创 BZOJ 2115: [Wc2011] Xor
题目大意：给定一个无向图，每条边上有边权，求一条1到n的路径，使路径上权值异或和最大首先一条路径的异或和可以化为一条1到n的简单路径和一些简单环的异或和 先DFS求出任意一条1到n的简单路径以及图中所有线性无关的环 然后利用这些环和1-n的简单路径凑出最大的异或和就可以了#include<bits/stdc++.h>using namespace std;const int N=10001
2016-10-30 21:40:38
273
原创 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest
B. 题意： 有一个序列长度为n的数组,每次你可以选择两个数的下标,电脑会告诉你两个数的大小关系,判断次数不超过ceil(3*n/2)-2思路: 交互题,我们可以通过观察给出的次数观察出结论,两个数可以比较三次,所以我们可以先把1和2的大小关系加入,然后每次加入两个数,先确定这两个数的大小关系,然后大的与前面大的比较,小的与前面小的比较 C. 题意: 有n个城市,m条
2016-10-26 15:00:23
769
原创 Hdu 5765 Bonds(高维前缀和)
题意: 给一个n个点的无向连通图，求每条边被多少个极小割边集包括 (n<=20,m<=n*(n-1)/2)思路: 极小边->分成两个联通块1.先求出与每个状态相邻的点的状态集 2.bfs判断哪些点可以组成一个联通块 3.高维前缀和#include<bits/stdc++.h>using namespace std;const int N=21;int ans[1<<21],sta
2016-10-24 21:02:24
809
原创 Kattis yatp(斜率优化+树分治)
题意: 2e5个点的无根树，每个点有点权，每条边有边权，定义一条简单路径的花费=这条路径两个端点点权的乘积+边权和， （一条简单路径可以包含一个点，这样花费是该点权的平方），最后问从每个点出发的最小花费思路: ans[i]=min(a[i]*a[j]+d[i]+d[j]) ->y=-a[i]*x+ans[i] 有三个点X,Y,Z,现在要求X的答案 假设Y比Z更优, 则X*Y+
2016-10-24 19:35:32
436
原创 codechef Prime Distance On Tree(树分治+fft)
题意: 给出一棵树，边长度都是1。每次任意取出两个点(u,v)，他们之间的长度为素数的概率为多大？思路: 树分治，对于每个根出发记录边的长度出现几次，然后求卷积，用素数表查一下即可添加答案。 时间复杂度:nlognlogn#include<bits/stdc++.h>using namespace std;const int N=5e4+100;struct Edge{ i
2016-10-23 09:14:09
390
原创 spoj 1825 Free tour II(树分治+启发式合并)
题意: 有N个顶点的树，节点间有权值， 节点分为黑点和白点。 找一条最长路径使得 路径上黑点数量不超过K个。思路: 设当前节点x到根的路径上黑色节点数量为deep[x],路径长度为dis[x] 将子节点按照最大deep倒序处理,利用启发式合并使得合并复杂度降为nlogn#include<bits/stdc++.h>template <class T1, class T2>inline
2016-10-22 21:41:25
429
原创 Bzoj 3672 购票(树分治+凸壳维护)
题意：给出一棵有根树（1为根），边有长度。每个点u有三个属性（len[u],p[u],q[u]）,每次u可以转移到u的某个祖先节点v（v满足dist(u,v)<=len[u]）, 代价为p[u]*dist(u,v)+q[u]。求每个点都转移到1的代价。思路: 树分治+cdq+维护凸壳1.树分治找出重心 2.处理重心到1的路径上的点 3.处理出重心的答案 4.维护len[u]-到重心的
2016-10-22 18:06:14
580
原创 Codeforces Round #377 (Div. 2)（D.E.F）
D.有n天，m科考试，给出每一天可以过哪一科，以及每科需要多少天复习，求最少要多少天考完，或者不可能。(n,m<=1e5)思路: 我们可以进行二分答案,那么可以把每一科最后在那一天考计算出来,我们贪心让最早先结束的先做,最后判断一下答案就可以了。 E.题意: 有n个计算机和m个电脑设配器(只能一对一使用,且电压相同),每次我们可以对电脑设配器的电压降低一半(向上取整) 输出最多有
2016-10-21 21:08:45
359
原创 Tsinsen A1486. 树(树分治+字典树)
传送门:Tsinsen A1486. 树 题意:给你一棵树(n<=1e5),每个点有一个权值和喜欢不喜欢之分,找出一条路径至少包含K个喜欢的点,而且异或和最大 思路: 树分治,同时维护字典树 字典树每个点维护一个喜欢的点数的最大值 时间复杂度:nlogn*30#include<bits/stdc++.h>using namespace std;const int N=1
2016-10-20 21:20:14
473
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人