2 Murphyc

尚未进行身份认证

喵喵喵!

等级
TA的排名 7w+

博客迁移

怎么说呢,ACM退役后想有个新的开始,所以做了个新的博客,已迁移至https://murphyc.cn/

2019-02-01 16:01:45

初探K-means聚类算法

K-means聚类算法到底是什么?K-means算法实际上就是将目标数据集划分为k个样本空间,最后使得每个样本空间的点到其空间中心点的距离最小K-means聚类算法中的距离我们稍微深入思考一下上面那段话便可以得到一个疑问,k-means算法中描述样本之间距离的定义到底是什么?我们该如何度量这个距离呢?在这里我们引入明可夫斯基(Minkowski)距离.明可夫斯基(Minkows...

2018-12-22 02:11:09

SPOJ 1811 LCS - Longest Common Substring(后缀自动机)

传送门题意:如题这题其实就是SAM上跳fail的一个应用,我们一开始匹配的节点就在root,随着扔进去匹配不同的字符,我们不断的跳fail直到匹配到当前的字符,如果跳的图中pos变为-1了,即为跳回root之前的最初的未加入任何字符节点,这则表示失配,更新cnt就好了如果找到一个pos不为-1的即匹配成功,那么我们更新cnt为len[pos]和cnt中较小的那个再加一即可(加一表示...

2018-10-04 16:59:42

国庆七天乐_day2 bzoj4566 找相同字符(广义后缀自动机)

传送门 广义后缀自动机实际上就是对于多串而言去建立后缀自动机这道题写起来很简单,我们对于两个串建立一个后缀自动机,与对于一个串去建立后缀自动机不同的是,对于第二个串,我们在线的构造后缀自动机的时候,需要去判别一下当前这个前缀是否已经为当前后缀自动机上的某一个状态.在构造后缀自动机的时候我们顺便计一下两个串分别在各个节点的访问次数,在topo之后再加上fail节点结束的个数最...

2018-10-02 17:40:18

国庆七天乐_day2 bzoj3998弦论(后缀自动机)

传送门 题意:求字典序第k小的字串对于T为0的情况,每个状态我们计数都为1对于T为1的情况,对于每个状态他的计数应加上他fail树结束节点的个数(实际的对应串的个数)然后随便DFS就好了 #pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize(4)#include<bits/...

2018-10-02 17:29:56

国庆七天乐day2_bzoj3238 差异(后缀自动机)

传送门最开始想到的是SARMQ预处理,不过既然在写SAM那就用SAM来解决一下这个问题 其实写起来SAM远比SA简洁 我们这样想,对于两个后缀,他的lcp的长度就是两个对应的接收态在fail树上的LCA的深度如果已经想明白了上面这点,那么对于这个问题,算得就是对于所有节点,求他的所有子节点对的LCA的sigma 在下面的代码中,除了模板部分就添加了两个数组,r...

2018-10-02 17:20:35

SPOJ - DISUBSTR Distinct Substrings(SAM)

 传送门题意:求本质不同的子串的个数 写这题就为了赛前测一下SAM板子,毕竟是个裸得不能再裸的裸题了,然而,居然出问题了.................. 问题出在初始化,一开始为了节省时间,是对每个节点一个一个去初始化-----fail[cnt]=-1;然而这样对于数据有多组的问题,可能就会出问题,在debug了近1h后,把这里改成了memset就过了,难受...

2018-10-01 17:13:37

国庆七天乐_day1_2012 Asia Tianjin Regional Contest HDU - 4436_str2int(SAM)

 传送门题意:给你多个串,求他们的所有子串中本质不同的串的和对2012取模 把所有串连起来建一个后缀自动机.对于每个节点的和而言,他实际的和应加上---------过该他子节点的次数×该节点所代表的数值+他的子节点的sum×10而实际过他这个节点的次数就更简单了,把他所有子节点的经过次数加起来就是了. 最后对所有节点求和取模即可. 这道题debug了一个...

2018-10-01 15:52:58

国庆七天乐day1_2016中国大学生程序设计竞赛(长春)hdu5918_Sequence I(kmp)

 传送门题意:问a从存在多少子序列满足子序列在a中的下标间隔为p且该子序列就是b. 直接把个子序列拿出来,依次kmp求和即可,每次询问复杂度为 #pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize(4)#include<bits/stdc++.h>usingnames...

2018-10-01 14:04:08

ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 K-Dimensional Foil II(二分瞎搞)

 传送门这题其实没有题面看起来复杂,实际上我们贪心的去想:对于下式                                      如果我们有这么一种操作可以把某个减一,现在问一次操作后S的最小值,那么很容易便可以知道我们肯定是去找最大的那个去减一,最后的结果才会最小.对于这道题其...

2018-09-22 21:53:28

Educational Codeforces Round 37 (Rated for Div. 2) E. Connected Components?(bfs+stl乱搞)

 传送门 题意:给定一个点数为n的完全图,现在给你m条边,表示这些边会从这个完全图中删去,问剩下图中的的联通块的个数以及大小 这题虽然算个E,但是吧确实比较容易解决,朴素的思路就是暴力bfs,但是肯定会t稍微改进一下写法,因为每个点在确定是某个联通块的部分之后就没用了,但是bfs还是会遍历到,所以说在每次判定完一个点的所属后,就直接把他从需要check的vector中删...

2018-08-27 16:53:07

hdu4280 Island Transport(毒瘤卡常最大流)

 传送门题意:n个岛屿有m个航道,每个航道能运送一定的人,问从最左端的岛屿到最右端的岛屿能运送的最大人流量最大流裸题,但是这个N和M都是1e5的,dinic很容易被卡,如下图所示这题10000ms,最后9999ms萌混过关(-ω-)过程就没什么好讲了,交就完事了,交个10发总有一发能A逃走(o>▽<) #pragmaGCCoptimi...

2018-08-24 17:34:09

POJ 2195 Going Home(最大流)

 传送门题意:给你一个n*m的矩阵,矩阵内m代表man,H代表hotel,每个man都要到hotel去,一个hotel只能住一个人,一个人移动(上下左右)一步的cost为1,求每个人都到hotel的最小总cost 最大流裸题首先每个人到所有hotel对应的cost都可以得到(就是哈夫曼距离),那么每个人和所有的hotel都建一条边,流量为1,cost为它们之间的哈夫曼距...

2018-08-24 12:50:16

POJ 3281 Dining(最大流)

 传送门题意:有N头牛,每个牛都有自己喜欢的food和drink的type,但是对于food和drink,每个type都只有一个,现在问最多能让多少牛满意. 最大流裸题,将food和drink的每个type作为点放在两端,将牛放在中间,将牛拆出两个点,一个点连接左边的food一个点连接右边的drink,将源点与次源点相连,次源点与所有food相连,汇点与所有drink相连,每个...

2018-08-23 17:14:12

2018 Multi-University Training Contest 10 Problem L.Videos(最小费用流)

 题意:一个video拥有四个属性-----开始时间,结束时间,happiness,type,给定K个人,一部片子只能被一个人看,一个人连续看x次同类型的片子(x>=2)会失去x*W的happiness,问K个人一天内看video的最大happiness和.首先我们将一个video看作一个点.之后,由于限定了连续看同类型的片子会掉happiness,所以我们这里引入一个拆...

2018-08-23 13:48:20

2018 Multi-University Training Contest 9 Rikka with Nash Equilibrium(dp)

  题意:矩阵中某个数,对于他所在的行列都是最大的,问这种数在矩阵中只有一个的矩阵能够造出多少个. 我们假设左上角那三个块表示已经放了数字那么如果要拓展出新的一列,我们能放的只有右边如图所示同理,如果要拓展出新的行,能放的位置只有如图所示 如果不拓展行列的话,那么就是在已被确定的的块内找未被占据的方块去填,对于图中的情况,能放的只有这一个块...

2018-08-21 09:45:15

2018 Multi-University Training Contest 9 Rikka with Stone-Paper-Scissors

  题意:yuta和rikka在玩石头剪刀布,不过他们用卡片表示这三种状态,每个人的卡片个数是一样的,rikka先出牌(yuta最初看不见,yuta出牌后才可见),假设rikka出牌是随机的且两个人都知道对方各类牌有几张,问最优出牌情况下,yuta能得到的最大分数期望. 比赛的时候这题其实自己没有仔细想,就直接凭感觉猜了个结论(感觉各类牌的贡献仅和sum和他的个数有关),然...

2018-08-21 09:17:25

Codeforces Round #505 (rated, Div. 1 + Div. 2) D. Recovering BST(区间dp/bitset优化)

题意:给定n个点,若是两个点的点权的gcd==1,那么这两个点之间可以连一条边,问是否可以构建出二叉搜索树. 区间dp,记忆化搜索,dp[i][j][fa]表示[i,j]区间的数可以构建出合法的二叉搜索树,并连接到父节点fa上要注意的是这种做法所需的空间卡的比较紧,bool都卡不过去,我们需要用bitset优化内存 #include<bits/stdc++.h&gt...

2018-08-21 08:50:55

Codeforces Round #505 (rated, Div. 1 + Div. 2) B. Weakened Common Divisor

 题意:定义弱因数x为满足对于一对数{a,b},{x|!(x%a)||!(x%b)}现在问你n对数的公共弱因数 这场比赛没打,但是吧赛时看了下题,和室友口胡了下正解是sqrt(a)+sqrt(b)时间计算出某对数的所有因数,设去重后一共有x个,之后for一遍所有对,总复杂度是 然后早上一写,submit,TLEontest99woc???t最后一组?...

2018-08-20 10:48:35

SPOJ 220 PHRASES - Relevant Phrases of Annihilation(SA)

  传送门题意:给定n个串,问n个串中对于每个串都出现了至少2次的最长不重合子串. 这个其实就是对于两个串的最长公共子串稍微改一点,我们把所有串用不同的分隔符连起来,同时记录每个下标对应的串的下标,然后我们可以去二分LCP,之后我们便可以发现对于LCP(i,j)>=x的所有后缀他们肯定都是在连续的一个组里面,这个随便写个串然后打出排序后的后缀便可以直接看出. ...

2018-08-18 17:29:16

查看更多

勋章 我的勋章
    暂无奖章