- 博客(142)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 吴恩达机器学习错题集
Week 3 Regularization第 1 题You are training a classification model with logistic regression. Which of the following statements are true? Check all that apply.A.Introducing regularization to the m...
2018-10-23 20:43:31
392
原创 HYSBZ - 3534 重建 变元矩阵-树定理
这题真心不错，，刷新了我对matrix-tree定理的认识，现在我对MT定理的认识是：可以计算有向图的每颗外/内向树的边权值的乘积的和 无向图图的每颗生成树的边权值的乘积的和特别的，当边权为1时，就是生成树的数量 #include<bits/stdc++.h>using namespace std;#define INF 0x3...
2017-08-31 09:00:54
465
原创 UVALive - 5542 Commedia dell' arte 三维n数码问题
其实，，，不管二维三维的这类问题，本质都是一个置换群的对换问题一置换中的一个长度为k的循环，至少需要k-1次对换才能恢复对换有个性质就是，一个对换不管变奇偶性都是相同的我们来看这道题，，其实移动一次0的，，就相当于一个对换，，我们先将这个三维n数码化为置换，找出有w个循环，那么就说明至少需要对换n*n*n-w次，再看0到最终位置最小步数x如果x和n*n*n-x同奇偶性，就说
2017-08-28 13:42:47
479
原创 POJ - 2888 Magic Bracelet burnside引理 有限制的计数
因为珠子之间有限制，不能利用polya，我们只能回归到最原始的burnside引理看看能不能解决问题burnside引理说的是什么那，，就是你只要给我每个置换对应的不动点个数，我就可以给你方案数我们来尝试找出一个置换对应的不动点因为只有旋转，所以，对于旋转k次这个置换，置换群被分为g=gcd(n,k)个循环，我们会发现，对于不动点，每个循环中柱子应该是一样的，所以我们只需要看连续的长为
2017-08-28 13:36:09
381
原创 UVA - 11255 Necklace 母函数型polya
就和普通的母函数差不多。。展开。。组合数求一下。。恩#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define INF
2017-08-27 22:40:43
352
原创 POJ - 2154 Color polya定理+欧拉函数
，，赤果果的裸polya，，但是n略大，，所以我们不能直接旋转从 0到n,我们需要优化一下，我们可以枚举循环的个数k，那么0到n中有多少是循环个数是k的那，，就是phi(n/k)个。。我们可以先处理处n的素数因子，然后可以快速dfs出所有可行的k。。注意，，P不是合数，，不能到最后才除以n（置换群的个数），可以在中间快速幂的时候幂次减一避免最后除P#include#include#
2017-08-27 22:33:47
290
原创 POJ - 3590 The shuffle Problem
根据置换群的基本知识知道，一个置换P,对于P^k=P的最小k，其实等于P所有循环大小的LCM所以问题转化为给你一个数n，将它分为几个数，使得和为n，并且LCM最大很显然和最终的数中的每个素数因子的次数有关，我们设dp[i][j]，和小于等于i的数，现在考虑到了第j个素数的最大LCM是多少就是可以写DP了还有一题加强版的是：http://www.lydsy.com/Jud
2017-08-27 12:47:52
263
原创 UVA - 11077 Find the Permutations 置换群+斯特林数
我们可以将这个排列写成循环的形式，可知，一个大小为x循环，需要对换x-1次才能对换完成所以题目的意思就是有多少种排列有n-k个循环，等价于n个数分成n-k个园排列的方案数，这正是第一类斯特林数。。不过要注意，，这题要用ULL。。#include#include#include#include#include#include#include#include#include#
2017-08-27 10:20:34
299
原创 hdu 6134 Battlestation Operational 莫比乌斯反演
题目链接点这里#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("in.txt","r",stdin);#define mem(x,y) memset(x,y,sizeof(x));typedef
2017-08-17 21:23:25
667
2
原创 HDU - 4773 Problem of Apollonius 圆的反演
题目链接点这里圆的反演主要有3条性质//1.不过反演中心的圆经过反演变换仍然是一个不过反演中心的圆.//2.不过反演中心的直线经过反演变换是一个经过反演中心的圆.//3.反演变换不改变图形的相切性.然后这道题就解决了。。//注意精度，直接用rad计算圆弧中点，#include#include#include#include#include#include#
2017-08-16 01:01:56
381
原创 UVALive - 2572 Viva Confetti 极角排序
题目链接点这里大白上的经典题，，但是比较难想。。。安装大白的思路，我们可以用圆弧的中点，前后偏移eps，用点代替圆弧里外的区域，就转化过来了。。。。这题精度有毒，，，还是看了代码仓库里的代码，，才A的。。计算几何精度太麻烦了，，反正原则就是，，，对于，，sqrt()，cos，sin这些函数能不用就不用，，，对于除法也能不用就不用，，这些写法大概都需要积累吧。。。//注意精度，直接用
2017-08-15 21:54:04
271
原创 Gym - 101234G Dreamoon and NightMarket
题目链接点这里这题感觉和图上k短路很类似，，用优先队列一直弹弹弹直到弹满k个就好了/*%%%%%%%%%%%%%lcy%%%%%%%%%%%%%%%%%%%%*/#include#include#include#include#include#include#include#include#include#include#include#include#i
2017-08-10 10:02:23
585
原创 ZOJ - 3871 Convex Hull 极角排序
题目链接点这里联想到我们算多边形面积时，用源点到边的叉积计算， 我们可以先枚举一个点u，然后以这个点极角排序枚举其他点v,就可以枚举点，这样可以方便计算在计算uv左边的点，从而求出他为边的凸包个数。。。#include#include#include#include#include#include#include#include#include#include#incl
2017-08-05 18:14:40
452
原创 UVALive - 7281 Saint John Festival logn判断点是否在凸多边形内
题目链接点这里对于判断点是否在凸多边形内有logn的算法，，可以看这一篇博客HLG 1429 凸多边形【快速判断点在凸多边形内】#include#include#include#include#include#include#include#include#include#include#include#include#include
2017-08-04 09:36:50
598
3
原创 HDU - 4373 Mysterious For Lucas+crt
题目链接点这里显然，第一类型循环可以将循环分为k块，每一块可以单独计算，根据打表+查OEIS(雾)，可得式子为:C(n-1+i,n-1)（i是相邻一个一类循环到接下来一个一类循环之间循环的个数(加上一个一类循环)）然而因为这个东西不是素数 364875103=97*364875103，所以我们可以分别将P为97和364875103算一次对应的，，然后用crt合并出答案我们可以预处理
2017-07-21 19:40:03
270
原创 loj 6197. 法克 最小路径覆盖 好题
题目链接点这里传统的最小路径覆盖算法是不能多次经过一个点的，解决方法有以下三种：1：构造floyd闭包，对于间接到达的边也加边，转化为传统路径覆盖来做。可以看这题，缺点是仅适用于n较小的情况2：我们可以知道，每个点必须经过一次，对于x拆点成x和n+x后，加一条下届为1的边，然后我们可以利用上下界最小流，直接跑出最小流，这就是答案。。可惜我超时了一组数据3：就是题解中所说的，，就是在
2017-07-18 11:49:48
884
原创 HYSBZ - 1005 明明的烦恼 （挖坑待补）
题目链接点这里今天好累啊，，脑子一片糊涂的做完这道题，，交了一发wa了，，定眼一看，要写大数，，mdzz，，然而今天感觉身子被掏空，，丝毫不想敲代码了，，留着以后补。。关于prufe序列的学习强烈推荐这一篇，特别全树的计数 + prufer序列与Cayley公式 学习笔记#include#include#include#include#include#incl
2017-07-17 21:28:48
226
原创 HDU - 5322 Hope cdq分治+ntt
题目链接点这里、#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x
2017-07-16 15:21:56
534
原创 ifrog 1044 - H. Quailty and Binary Operation cdq分治+fft
题目链接点这里应该想一下就知道需要用fft，，但是怎么用那？在cdq分治中我们发现，他在递归的将[l,mid对[mid+1，r]的贡献计算出来。。所以对于这题在分治的时候计算x[l,mid对y[mid+1，r]的贡献（x=y)就好了。。然而对于x==y的时候，无法在分治中计算我们可以在l==r的时候单独计算#include#include#include#include#inc
2017-07-14 23:12:51
307
原创 HDU - 5958 New Signal Decomposition 原根下标变换+fft(未完待续)
题目链接点这里过程看这里http://blog.csdn.net/u013368721/article/details/53001532，，然而，，这位大佬的程序也gg了，，可能改过数据了，，不过思路是这样的，，然而我与标程对拍，，答案总是差0.00几。。反正，，我写的fft自带低精度，大内存，高常数。。，，以后再看吧#include#include#include#incl
2017-07-14 17:19:33
456
原创 ZOJ - 2619 Generator 高斯消元
题目链接点这里浮点数高斯消元精度爆炸，，long double 都卡不过去。。因为只有一个串，，期望一定是整数，最后改成了整数高斯消元才过。。#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",s
2017-07-13 15:15:41
221
原创 HDU - 3058 Generator AC自动机+高斯消元（未完待续）
题目链接点这里高斯消元精度爆炸，，卡不过去了，，网上博客里的代码也都wa了，，先放着吧。。#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#d
2017-07-13 15:08:44
238
原创 HDU - 5955 Guessing the Dice Roll AC自动机+高斯消元
题目链接点这里主要要注意的是，， 对实数高斯消元，注意判断奇怪的情况，比如-0.00。。输出的时候加个eps就好。。wa了好几发#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",stdin)#de
2017-07-13 10:33:10
363
原创 HDU - 5730 Shell Necklace CDQ分治+fft
题目链接点这里#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",stdin)#define mem(x,y) memset(x,y,sizeof(x))typedef unsigned long l
2017-07-11 23:07:59
283
原创 shu 423 密码破解
题目链接点这里#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",stdin)#define mem(x,y) memset(x,y,sizeof(x))typedef unsigned lo
2017-07-10 10:49:25
391
原创 shu 419 膜一下将带给你好运
题目链接点这里#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",stdin)#define mem(x,y) memset(x,y,sizeof(x))typedef unsigned lo
2017-07-10 10:02:58
584
1
原创 7月记录贴
7月9号： 如何将变一个无向图边最少使得其边-双联通，输出方案： 解决：在Q巨的帮助下，终于明白了.我们现将k个联通快用k-1条边联通此时随意连。然后就缩点成一颗树，，我们将叶子节点权值看程1，，其他看成0，，找出他的带权重心作为根。我们知道边双联通的条件就是没有桥，，，此时，，我们每个子树的边其实都是桥，，我们现在要做的就是消去这些桥，，，因为是带权重心，，每一颗子树的叶子节点
2017-07-09 00:25:06
174
原创 51nod 1597 有限背包计数问题
题目链接点，，，，不想给了。。这题真的是跪烂啊，，怎么想出这种解法的，，无敌，，，#includeusing namespace std;#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f3f#define FIN freopen("input.txt","r",stdin)#define mem(x,y) mem
2017-07-09 00:07:20
327
原创 csu 1951: 图样 AC自动机
题目链接点这里我们把两种字符串都插入到自动机中，用End[u] = mask来状压记录下以u节点结尾的喜欢字符串有哪些（比如这个点结尾有第i个字符串和第j个字符串，，那么End[u]=（1<<i）+(1<<j) ）。之后那我们把讨厌字符串的End[u]记为-1.。构造出自动机之后，套路状态转移建图。然后bfs就好了 ，什么？你不会ac自动机上的状态转移？请做这题 #
2017-06-23 08:00:16
277
原创 csu 1950: 谈笑风生 卡特兰数
题目链接点这里基佬出的毒瘤题啊。。。看完题目我们很容易把第x个左括号和其右括号内的看成独立一部分设为Q，枚举这个里面的括号数。这里很简单，，然后那？，，然后还剩下Q左右的2部分。。接下来该怎么考虑？。。一开始我是把2部分放在一起考虑的，结果非常复杂，考虑的东西非常多其实那，我们只需要单独考虑2部份就可以了。我们需要知道一个公式：Cm(i,j)=C(i+j,
2017-06-23 07:51:14
230
原创 cf 815C Karen and Supermarket 树形dp
题目链接点这里把他看成一棵树，dp[i][j][k]是对于j点用不用优惠券（i）已选k个的最小花费。。。很明显对子树做一个分组背包即可。然而乍一看分组背包的复杂度不是n（n个点）*n*n（dp复杂度）是n^3次方吗？这里有2种dp方式1.dfs过程中处理u时初始siz[u]=1，搞完u的一棵子树v，花O(siz[u]*siz[v])dp，然后在siz[u]+=siz[v]，继续其他子树 2
2017-06-21 21:12:37
572
原创 51nod 1675 序列变换 莫比乌斯反演
题目链接点这里莫比乌斯反演模板题看到互质什么的个数，，就想到莫比乌斯反演了吧，，我们将f(n)设为下标gcd刚刚为n的组数，F(n)为下标的gcd为n的倍数的组数。。根据反演公式：#include#include#include#include#include#include#include#include#include#include#inc
2017-06-21 15:01:55
358
原创 「美团 CodeM 初赛 Round A」二分图染色 容斥原理
题目链接点这里首先绿色不用管然后只有2种颜色，很显然需要用容斥原理求，先算全部的数量，然后容斥减去不合法的数目我们n个点设单种颜色的方案数为F(n)，所以2种颜色的方案数就是F（n）^2（包含不合法），先看直接列出来的式子：#include#include#include#include#include#include#include#in
2017-06-21 13:22:05
796
原创 美团CodeM 初赛 A轮 数列互质 莫队
题目链接点这里应该很容易想到用莫队做，然后那？我们现在已经知道了一个区间内各个数出现的次数，及其次数出现的次数，我们应该怎么算他互质的数的个数？我们先要知道这么一个事实，一个区间内次数的不同最多是sqrt（n）个，，所以整个算法的复杂度是，，nsqrt（n）（莫队的）+msqrt（n）*（求互质的复杂度）这个（求互质的复杂度），，一般有三种方法，，第一种直接logn求gcd。。第二种现
2017-06-20 20:30:27
732
原创 美团CodeM 初赛 A伦 最长树链 xjb枚举+dfs
[编程题] 最长树链时间限制：1秒空间限制：32768K树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1。请求出这条树链的长度。 输入描述:第1行：整数n（1 ≤ n ≤ 100000），表示点的个数。第2~n
2017-06-19 16:48:58
876
原创 美团CodeM 初赛 A伦 合并回文子串 区间dp
[编程题] 合并回文子串时间限制：2秒空间限制：262144K输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能的C中价值最大的
2017-06-19 14:40:12
467
原创 计蒜客 腾讯狼人杀（困难） 最大权密度子图变种
题目链接点这里历经一个星期，，终于做好了。。《最小割模型在信息学竞赛中的应用》这篇论文必看啊。。。#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace s
2017-06-17 13:30:35
310
原创 HDU - 5669 Road 线段树优化建边+分层图最短路
题目链接点这里线段树优化建边太厉害了，，这题题解说的很清楚了：点这里不过实现上有很多小技巧，，强烈建议做一下#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namesp
2017-06-17 07:32:49
769
数字图像处理与分析 中科院刘定生 2010春 整合版课件 带目录
2019-02-10
吴恩达机器学习课件pdf版
2018-10-17
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人