- 博客(86)
- 收藏
- 关注
RSS订阅
原创 初探K-means聚类算法
K-means聚类算法到底是什么？K-means算法实际上就是将目标数据集划分为k个样本空间，最后使得每个样本空间的点到其空间中心点的距离最小K-means聚类算法中的距离我们稍微深入思考一下上面那段话便可以得到一个疑问，k-means算法中描述样本之间距离的定义到底是什么？我们该如何度量这个距离呢？在这里我们引入明可夫斯基(Minkowski)距离.明可夫斯基(Minkows...
2018-12-22 02:11:09
370
原创 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
270
原创 国庆七天乐_day2 bzoj4566 找相同字符(广义后缀自动机)
传送门 广义后缀自动机实际上就是对于多串而言去建立后缀自动机这道题写起来很简单，我们对于两个串建立一个后缀自动机，与对于一个串去建立后缀自动机不同的是，对于第二个串，我们在线的构造后缀自动机的时候，需要去判别一下当前这个前缀是否已经为当前后缀自动机上的某一个状态.在构造后缀自动机的时候我们顺便计一下两个串分别在各个节点的访问次数,在topo之后再加上fail节点结束的个数最...
2018-10-02 17:40:18
309
原创 国庆七天乐_day2 bzoj3998弦论(后缀自动机)
传送门 题意：求字典序第k小的字串对于T为0的情况，每个状态我们计数都为1对于T为1的情况，对于每个状态他的计数应加上他fail树结束节点的个数(实际的对应串的个数)然后随便DFS就好了 #pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include<bits/...
2018-10-02 17:29:56
277
原创 国庆七天乐day2_bzoj3238 差异(后缀自动机)
传送门最开始想到的是SA RMQ预处理，不过既然在写SAM那就用SAM来解决一下这个问题 其实写起来SAM远比SA简洁 我们这样想，对于两个后缀，他的lcp的长度就是两个对应的接收态在fail树上的LCA的深度如果已经想明白了上面这点，那么对于这个问题，算得就是对于所有节点，求他的所有子节点对的LCA的sigma 在下面的代码中，除了模板部分就添加了两个数组，r...
2018-10-02 17:20:35
277
原创 SPOJ - DISUBSTR Distinct Substrings(SAM)
传送门题意：求本质不同的子串的个数 写这题就为了赛前测一下SAM板子，毕竟是个裸得不能再裸的裸题了，然而，居然出问题了.................. 问题出在初始化，一开始为了节省时间，是对每个节点一个一个去初始化-----fail[cnt] = -1;然而这样对于数据有多组的问题，可能就会出问题，在debug了近1h后，把这里改成了memset就过了，难受...
2018-10-01 17:13:37
175
原创 国庆七天乐_day1_2012 Asia Tianjin Regional Contest HDU - 4436_str2int(SAM)
传送门题意：给你多个串，求他们的所有子串中本质不同的串的和对2012取模 把所有串连起来建一个后缀自动机.对于每个节点的和而言，他实际的和应加上---------过该他子节点的次数×该节点所代表的数值+他的子节点的sum×10而实际过他这个节点的次数就更简单了，把他所有子节点的经过次数加起来就是了. 最后对所有节点求和取模即可. 这道题debug了一个...
2018-10-01 15:52:58
329
原创 国庆七天乐day1_2016中国大学生程序设计竞赛（长春）hdu5918_Sequence I(kmp)
传送门题意：问a从存在多少子序列满足子序列在a中的下标间隔为p且该子序列就是b. 直接把个子序列拿出来，依次kmp求和即可，每次询问复杂度为 #pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include<bits/stdc++.h>using names...
2018-10-01 14:04:08
390
原创 ACM/ICPC 2018亚洲区预选赛北京赛站网络赛 K-Dimensional Foil II(二分瞎搞)
传送门这题其实没有题面看起来复杂，实际上我们贪心的去想：对于下式 如果我们有这么一种操作可以把某个减一，现在问一次操作后S的最小值,那么很容易便可以知道我们肯定是去找最大的那个去减一，最后的结果才会最小.对于这道题其...
2018-09-22 21:53:28
882
1
原创 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
244
原创 hdu4280 Island Transport(毒瘤卡常最大流)
传送门题意：n个岛屿有m个航道，每个航道能运送一定的人，问从最左端的岛屿到最右端的岛屿能运送的最大人流量最大流裸题，但是这个N和M都是1e5的，dinic很容易被卡，如下图所示这题10000ms，最后9999ms萌混过关(-ω- )过程就没什么好讲了，交就完事了，交个10发总有一发能A逃走(o>▽<) #pragma GCC optimi...
2018-08-24 17:34:09
718
2
原创 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
301
原创 POJ 3281 Dining(最大流)
传送门题意：有N头牛，每个牛都有自己喜欢的food和drink的type，但是对于food和drink，每个type都只有一个，现在问最多能让多少牛满意. 最大流裸题，将food和drink的每个type作为点放在两端，将牛放在中间，将牛拆出两个点，一个点连接左边的food一个点连接右边的drink，将源点与次源点相连，次源点与所有food相连，汇点与所有drink相连，每个...
2018-08-23 17:14:12
193
原创 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
1144
原创 2018 Multi-University Training Contest 9 Rikka with Nash Equilibrium(dp)
题意：矩阵中某个数，对于他所在的行列都是最大的，问这种数在矩阵中只有一个的矩阵能够造出多少个. 我们假设左上角那三个块表示已经放了数字那么如果要拓展出新的一列，我们能放的只有右边如图所示同理，如果要拓展出新的行，能放的位置只有如图所示 如果不拓展行列的话，那么就是在已被确定的的块内找未被占据的方块去填，对于图中的情况，能放的只有这一个块...
2018-08-21 09:45:15
193
原创 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
238
原创 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>...
2018-08-21 08:50:55
248
原创 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，TLE on test99woc？？？t最后一组？...
2018-08-20 10:48:35
203
原创 SPOJ 220 PHRASES - Relevant Phrases of Annihilation(SA)
传送门题意：给定n个串，问n个串中对于每个串都出现了至少2次的最长不重合子串. 这个其实就是对于两个串的最长公共子串稍微改一点，我们把所有串用不同的分隔符连起来，同时记录每个下标对应的串的下标，然后我们可以去二分LCP，之后我们便可以发现对于LCP(i,j)>=x的所有后缀他们肯定都是在连续的一个组里面，这个随便写个串然后打出排序后的后缀便可以直接看出. ...
2018-08-18 17:29:16
170
原创 SA模板(DA||DC3)
DA版本的SA速度相较DC3慢了些，很容易被卡，但是他在所需空间上优越于DC3#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include<bits/stdc++.h>using namespace std;using namespace std;typedef long l...
2018-08-17 17:54:48
495
原创 FFT/NTT/FWT模板
非递归版FFT源自快速傅里叶变换(FFT)详解#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=5e6+5;in...
2018-08-17 14:33:51
334
原创 牛客网暑期ACM多校训练营（第九场）A.Circulant Matrix(FWT)
A.Circulant Matrix 传送门 我们首先观察一下这几个等式 之后对于易得这样一则等式 那么稍作转化我们便可以得到...
2018-08-17 13:26:31
271
原创 树上差分(点覆盖/边覆盖)
树上差分树上差分实际上类似于树链剖分，将一条链分为轻链和重链，再分别对两个直链去做差分标记，最后再去对于每个点dfs他的子节点求树上前缀和.类似的题目自己做过的不多，这里推荐两道比较简单的题目，都是边覆盖问题.EOJ Monthly 2018.8 D. Delivery Service|| P2680 运输计划树上边差分（边覆盖）struct Point_pair{ ...
2018-08-14 17:35:34
1104
原创 EOJ Monthly 2018.8(A,B,C,D)
EOJ Monthly 2018.8A. A Simple Convolution卷积#include<bits/stdc++.h>using namespace std;typedef long long ll;int mi[105][105];int conv[105][105];i...
2018-08-14 16:21:53
326
原创 c++读入优化(模板)
今年的多校(nowcoder)，被卡常卡到自闭，然而隔壁队挂个读入挂就过了,emmmmmm，自此以后，自带大常数，逐渐进入卡常的节奏，哈哈哈哈哈 之所以会有读入优化这种东西是因为getchar()的速度比scanf和cin都要快，所以在读入数据比较多的时候可以尝试读入优化，顺带inline一下，会更快一点.scanf实际上也是读入字符，不过我们给了他格式说明符(例如d)，所以他...
2018-08-14 15:33:29
678
原创 牛客网暑期ACM多校训练营（第八场）B.Filling pools
B.Filling pools 这题算的实际上是 如果不直接打算看oeis的递推式，可以看下下面的wiki以及递推式(推广)证明论文对于这个问题你需要知道Narayana number然后Generalized Small Schr¨oder numbers这篇论文是对 做...
2018-08-11 17:00:03
498
原创 Codeforces Round #339 (Div. 2) （已更新A，B，C，D）
Codeforces Round #339 (Div. 2) 传送门因为明晚又有cf了，所以顺手摸了场出题人__以前出的一场，然后我发现， 这个problem setter（__,其实还有_） 好duliu啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊_kun_出过题的场子ch_egor出过题的场子场内他...
2018-08-11 09:46:55
218
原创 2018 Multi-University Training Contest 5 | Everything Has Changed(圆交点模板)
Everything Has Changed(圆交点模板) 传送门又到了考验板子的时候了，1A就很舒服，挂个all ok的板子#include<bits/stdc++.h>using namespace std;typedef long long ll;const double eps=1e-8;int cmp(do...
2018-08-06 17:07:48
182
原创 Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix(思维/构造）
D. Vasya And The Matrix 传送门 emmm,想不出来C，最后15mins溜出来写个D的题解● 3●题意：给你每行每列的异或让你去构造这个矩阵. 其实很简单，首先我们可以发现n和m都很小，那么排除算法题，肯定是往暴力的方向想。那么我们暴力什么呢？题目给的是连续异或，那么...
2018-08-04 00:47:04
398
原创 牛客网暑期ACM多校训练营（第五场）H-subseq
H-subseq 传送门题意：稍微转化一下题意就可以发现这题问的其实就是a序列中字典序第k大的递增子序列.为了解决这道题，我们可以定义一个表示从i到后面的所有的递增自序列个数的总和，这个用树状数...
2018-08-03 14:04:13
373
2
原创 牛客网暑期ACM多校训练营（第五场）F-take（树状数组）
F-take 传送门题意：从左往右依次看箱子，箱子里有pi的概率存在大小为di的diamond，每次看到比自己大的diamond就会换掉自己手上的diamond，问看完箱子换取diamond的期望. 这题其实不难，仔细一想就可以发现会贡献期望的就是之前比自己大的全都没选的概率...
2018-08-03 13:17:42
222
原创 Codeforces Round #500 (Div. 2) [based on EJOI] D. Chemical table(dfs)
D. Chemical table 传送门题意：对于一个N*M的方框，一开始给你q个点，问是否能通过题中给出的操作填满这个方框，这个操作就是假设如果有L型的三个点已经在方框内，那么可以在对应的第四个点自动生成一个点，问最少要填几个数使得这个方框在任意次操作后能够被填满.对于给定点的row或者是c...
2018-07-31 10:56:19
344
原创 Codeforces Round #499 (Div. 1) C. Border || Codeforces Round #499 (Div. 2) E.Border(数论/贝祖定理）
Codeforces Round #499 (Div. 1) C. Border Codeforces Round #499 (Div. 2) E. Border (数论/贝祖定理） 题意：给你n个数字(十进制)，每个数字都可以使用无限次...
2018-07-27 09:41:26
847
6
原创 牛客网暑期ACM多校训练营（第二场）C.message
C.message 这题，没啥好说的，把求直线相交转化为求，之后就是构造凸包同时三分凸包上的极值点.尽管如此，还是丢人的wa了11发.......写个博客就当扔个凸包板子进来....... #include<cstdio>#include<cstrin...
2018-07-25 09:24:20
276
原创 2018 Multi-University Training Contest 1 | Balanced Sequence（暴力贪心）
Balanced Sequence 传送门今天这题，完全是我的锅，读错了题意（看成了有多少个匹配的字串）然后还决然的自己去敲了这道题，到了最后50mins在和队友关于算法完备性的争论中才发现自己读错了题......最后再次5题gg，如果能早点发现读错题，6题兴许可能还能到第一页......自己看题和解...
2018-07-23 18:37:46
345
原创 牛客网暑期ACM多校训练营（第一场）I.Substring(SA|后缀数组）
I.Substring 传送门 题意：找出最大的集合内串互不同构的子串的集合的大小. 因为串内字符只存在所以我们暴力处理出原串的所有同构串，并重构一个包含原串所有同构的新串，新串的长度为原串的长度 那么对于这个问题就转化成了计算新串中不同的子串的个数，这个问题用...
2018-07-21 10:30:42
502
原创 牛客网暑期ACM多校训练营（第一场）E.Removal(dp)
牛客网暑期ACM多校训练营（第一场）E.Removal传送门 昨天下午，牛客多校第一场，开局两道题，之后盯上了这题，一直挂机到比赛结束，本蒟蒻挂机期间机队友推出了A题的规律，最后3题gg赛后看了眼榜葫芦爷真的 赛时想的dp[i][j]是枚举到第i个长度为j的方案数，然后就转移不出来了,emmmmm赛后看了题解pdf，发现挂机期间队友给的思路...
2018-07-20 10:48:34
776
2
原创 The 2014 ACM-ICPC Asia Xi’an Regional Contest Problem F. Color（二项式反演）
Problem F. Color 传送门题意：长度为n的一个连续串让你染色，使得相邻位置的颜色不能一样，且串中恰好一共出现k种颜色，问若是你有m种颜色（m>=k)，一共有多少种染色方法满足给定条件.我们易推得如果仅仅是要求相邻位置的颜色不一样那么 ...
2018-07-18 20:51:08
508
原创 2018 UESTC Training for Math P.集合？ 集合！
2018 UESTC Training for Math P.集合？ 集合！ 今天路过lutece准备摸一题，找了个题目最短的题，一看这不是两个月前cf contest980的D原题吗，连样例都没改啊喂 两个月前写的博客又水了一篇博客真香...
2018-07-17 15:08:15
234
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人