-
uniHk 2020-01-02 20:36:40
秩序魔咒（回文自动机+最长公共回文子串）
秩序魔咒 题意： 求两个串最长相同的回文子串的长度，并求出这种长度的子串有多少个 思路： 既然有回文串，自然会想到回文自动机或 m a
来自 uniHk00 -
uniHk 2020-01-02 20:37:01
Can You Solve the Harder Problem?（2018ICPC焦作H）（后缀自动机+单调栈）
Can You Solve the Harder Problem? 这题简直妙呀！可惜训练赛的时候 3 h
来自 uniHk00 -
uniHk 2020-01-02 20:37:21
Megumi With String（2019南昌网络赛F）（后缀自动机+数学期望）
Megumi With String 这题我T了40次左右。。。拿着别人的AC代码双向修改，我的一直T，别人的一直A。。。甚至感觉除了变量名不一样，其他的都完全一样了，还是T 噩梦经历 最后发现是初始化函数写跪了 题意：给定一个已知串
来自 uniHk00 -
uniHk 2020-01-02 20:37:41
火星商店（线段树分治套可持久化trie树）
火星商店 从开这题开始，到真正A掉它竟然花了两周！主要是这题前置知识没有掌握，因此花了一周搞定了主席树专题，再花了些时间搞定了可持久化 t r
来自 uniHk00 -
uniHk 2020-01-02 20:38:02
MET-Meteors（整体二分）
MET-Meteors 我决定以后二分的 m m m都写成
来自 uniHk00 -
uniHk 2020-01-02 20:38:22
超级钢琴（主席树+贪心+优先队列）
超级钢琴 我能说这是主席树板子题嘛？ 题意：给定一个序列，求长度在 L L L与
来自 uniHk00 -
uniHk 2020-01-02 20:38:43
Rhyme scheme（2019上海网络赛）（贝尔数+dp+dfs）
Rhyme scheme 赛后：原来就这么个简单题！ 题意：给定 n n n和
来自 uniHk00 -
uniHk 2020-01-02 20:39:03
Counting Sequences I（2019上海网络赛D）（暴力dfs or 打表）
Counting Sequences I 拿着OEIS上的一个类似的序列（当时以为是相同的）怼了半天。。。欲哭无泪 题意：问有多少长度为 n n
来自 uniHk00 -
uniHk 2020-01-02 20:39:44
Into Blocks（CodeForces Round #584）（优雅的贪心）
Into Blocks（不带修改的 E a s y
来自 uniHk00 -
uniHk 2020-01-02 20:40:04
Rotate Columns（CodeForces Round #584）（状压DP）
Rotate Columns 题意：给定一个矩阵，可以对矩阵的任意列进行上下滑动（或称旋转），使最大化每一行的最大值 之和。 E a
来自 uniHk00 -
uniHk 2020-01-02 20:40:25
最大异或和（可持久化01trie）
最大异或和 题意：转化后的题意是有一种操作+一种询问： 1. 操作：在序列末尾插入一个数 2. 询问：给定 l , r
来自 uniHk00 -
uniHk 2020-01-02 20:40:45
最长异或路径（01trie+最大异或对）
最长异或路径 板子题，但是如果把边权改成了点权的话好像就不好做了，暂时还没想好 题意：给定一棵带边权的树，求最大的异或路径。 思路： 令每个节点的权值为从根到当前节点的路径上边权异或值，则此问题就被转化为普通的最大异或对了 最大异或对就没啥说的了，按顺序（随便什么顺序）把每个点加入
来自 uniHk00 -
uniHk 2020-01-02 20:41:06
Nikitosh和异或（01trie+最大异或对）
Nikitosh和异或 因为下面这段代码卡了接近一小时！ int s=p&1<<i; // wrong int s=p>>i&1; // correct 题意：最大化两个异或对之和（还是看下面的题面吧） 思路： 预处理前缀最大异或对，然后从后
来自 uniHk00 -
铁柱锈死了 2020-01-02 20:41:15
python题解（官方）
解释：我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>=2时，第一次跳的时候有两种不同的选择： 第一次跳1级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1); 第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同
来自 铁柱锈死了150 -
uniHk 2020-01-02 20:41:26
旅行（树链剖分+动态开点）
旅行 果然树剖的题代码量都不小，不过还是学了一波动态开点，妙呀！ 题意：给定一棵带权带颜色的树，两种操作+两种询问： 操作1：更改某个点的颜***r> 操作2：更改某个点的权值 询问1：询问 x
来自 uniHk00 -
uniHk 2020-01-02 20:41:47
Codeforces 750E+2019南昌网络赛C（线段树维护自动机状态转移）
这个题解法之妙导致不想吐槽这场比赛了。。。 原题：Codeforces 750E New Year and Old Subsequence 复现：2019南昌网络赛C题 Hello 2019 原题题意：给定一个数字串，多次询问，每次询问使
来自 uniHk00 -
uniHk 2020-01-02 20:42:08
Fire-Fighting Hero（2019南昌网络赛）（最短路+新建源点）
Fire-Fighting Hero 赛后自己写了一个。。。因为舍不得开大数组，挂了三次。。。好在场上是队友做的， 1 A
来自 uniHk00 -
uniHk 2020-01-02 20:42:28
Colorful String（2019徐州网络赛）（回文自动机上dfs+状压）
Colorful String 比赛一开，我看的第一题就是这题。然后一看，回文串！那肯定回文自动机搞一下不就行了吗？再仔细一看，发现有个小地方我不敢确定，遂想用 m
来自 uniHk00 -
uniHk 2020-01-02 20:42:49
Random Access Iterator（2019徐州网络赛）（树形DP or 概率DP）
Random Access Iterator 唉！你能一手双向边秒了我？场上SB了，竟然天真的以为出题人给我的数据时会按照从父节点到儿子节点的顺序给我单向边。。。然后WA到mdbrsl 题意：给定一棵以 1
来自 uniHk00 -
uniHk 2020-01-02 20:43:09
query（2019徐州网络赛）（一点思维+树状数组）
query 这题和HH的项链简直是异曲同工之妙，只不过预处理不同，此题略巧妙些 题意：给定一个 1 1 1~
来自 uniHk00 -
uniHk 2020-01-02 20:43:30
动态逆序对（CQOI）（CDQ分治 or 主席树）
动态逆序对（重庆OI） 先写一个CDQ分治的写法吧，主席树。。。希望我以后会补。 题意：先给定一个 1 1 1~
来自 uniHk00 -
uniHk 2020-01-02 20:43:50
任务查询系统（主席树的差分性质）
任务查询系统 题意：区间修改（修改区间每个位置某个数的数量，注意每个位置有多个数）+单点查询前K小的权值和+强制在线 思路： 由于主席树运用了前缀和思想，每个位置保存了所有权值的前缀和；因此若此题的区间修改利用差分思想，则主席树的每个位置恰好就维护的是自身位置（差分与前缀和相互抵消了），
来自 uniHk00 -
uniHk 2020-01-02 20:44:10
森林（树上主席树+启发式合并）
森林 题意：有两种操作： 1. 将某两个点连起来（连边后保证为森林或者一棵树） 2. 询问两点之间路径上第K小权值（强制在线且保证询问合法） 思路：树上主席树+启发式合并 先离散化一下还是有必要的 连边后分别在每一棵树上建立主席树，每一棵树上的每一个节点的主席树维护从所在的树根到当前节
来自 uniHk00 -
uniHk 2020-01-02 20:44:31
粟粟的书架（主席树+二维前缀和）
粟粟的书架 一下子做了两个题？ 题意：一个问题求区间前K大的和，另一个问题求矩形内前K大的和。 思路： 前一个问题直接上主席树+二分搞定 后一个问题由于数据范围比较小，用 c
来自 uniHk00 -
uniHk 2020-01-02 20:44:51
矩形藏宝地（CDQ分治+伪四维偏序）
矩形藏宝地 这题虽然题面有种自相矛盾的感觉，但是样例还是清晰的，简单题 题意：在一个二维平面上，求有多少个矩形是被包含在一个更大的矩形中的。 思路：伪四维偏序 由于题目竟然没有给出坐标的范围，因此我们拿到坐标还是离散化一下吧 现将所有的矩形按照
来自 uniHk00 -
uniHk 2020-01-02 20:45:11
天使玩偶（CDQ分治+最小曼哈顿距离）
天使玩偶 题意：有两种操作： 给二维平面上加入一个点 询问二维平面上到某个点最近的一个点（用曼哈顿距离来表示） 思路：标准的CDQ分治，离线处理两种操作 当想到CDQ分治后本题的重点在于如何处理曼哈顿距离，毕竟看到绝对值都头疼 我们最希望的是能去掉绝对值！这里有一种处
来自 uniHk00 -
uniHk 2020-01-02 20:45:32
陌上花开（CDQ分治）
陌上花开 第二遍写这个题了 题意：若某个元素的三个维度的值都小于等于另外一个元素，则是真的小于等于；给出一些元素，求等级分别为 0 <mtext> <
来自 uniHk00 -
uniHk 2020-01-02 20:45:52
Continuous Intervals（线段树+单调栈）
Continuous Intervals 线段树好题呀！比赛的时候根本看不出来，赛后惊叹“学到了！” 题意：给定一个数组，求数组内有多少连续区间。“连续区间”的定义：将区间内数字按大小排序后，相邻元素差值不大于1，可以等于0。 思路：绝妙的思路！线段树+区间修改+区间最小值及最小值个数+单调栈
来自 uniHk00 -
uniHk 2020-01-02 20:46:13
2-3-4 Tree
2-3-4 Tree 介绍 Conclusion 2-3-4 is great regarding memory and time complexity. Why isn’t it widely used? You may have noticed that while understand
来自 uniHk00 -
uniHk 2020-01-02 20:46:53
工艺（最小表示法）
工艺 题意：给定长度为 n n n的序列，求字典序最小的长度为 n
来自 uniHk00 -
uniHk 2020-01-02 20:47:14
Censoring (Gold)（AC自动机多字符串匹配+栈）
Censoring (Gold) 题意：给了一段文本串，再给了含 N N N个字符串的字典。将文本从左到右，如果遇到了字典中的字符串，则删
来自 uniHk00 -
uniHk 2020-01-02 20:47:35
最短母串问题（AC自动机+BFS+状态压缩）
最短母串问题 题意：给定 n n n个子串，求最短且字典序最小的母串（母串性质：这
来自 uniHk00 -
uniHk 2020-01-02 20:47:55
主席树
主席树 小小总结： 1. 主席树静态区间第k小板子 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back
来自 uniHk00 -
uniHk 2020-01-02 20:48:16
2019牛客多校-10J-Wood Processing（斜率优化DP）
Wood Processing 题意：有 n n n块矩形，给出每块矩形底边长和高度，要将
来自 uniHk00 -
uniHk 2020-01-02 20:48:36
Codeforces Round #580 Shortest Cycle（Floyd求最小环）
Shortest Cycle 题意：给定 1 e 5 1e5
来自 uniHk00 -
uniHk 2020-01-02 20:48:56
斜率优化DP-玩具装箱TOY
简洁的学习 更进一步的学习 小总结 优化目的：在依次计算 d p [
来自 uniHk00 -
uniHk 2020-01-02 20:49:17
HDU-2121（有向图最小生成树，朱刘算法）
Ice_cream’s world II 题意：给定一个有向图，求最小生成树是否存在，若存在则求出根节点以及最小权值。 思路：利用朱刘算法，推荐博客 求最短弧集合E0 检查E0 收缩G中的有向环 展开收缩点 （以下代码节点下标从
来自 uniHk00 -
铁柱锈死了 2020-01-02 20:49:20
python题解（数学归纳）
解释：使用数学归纳法可以很容易的得出： n=1时有1种跳法 n=2时有2种跳法 n=3时有4种跳法 n=4时有8种跳法 固总结出f(n) = 2**(n-1) class Solution: def jumpFloorII(self, number): # write c
来自 铁柱锈死了61 -
uniHk 2020-01-02 20:49:37
2019牛客多校-8J-Just Jump（组合数+容斥原理）
Just Jump 题意： 求从 0 0 0跳到 L
来自 uniHk00 -
uniHk 2020-01-02 20:49:58
K短路-魔法猪学院（A*算法）+骑士精神（IDA*算法）
K短路-魔法猪学院 题意：给定一个能量值 E E E，以及一些单向边权。求所拥有的能量能从
来自 uniHk00 -
uniHk 2020-01-02 20:50:20
牛客多校2019-7H-Pair（两个数的数位DP）
Pair 考场上加了各种各样的优化也没能由T变AC。。。赛后题解“直接数位DP就行” 题意：给定 A , B
来自 uniHk00 -
uniHk 2020-01-02 20:50:41
牛客多校2019-6C-Palindrome Mouse（回文自动机+统计支配点）
Palindrome Mouse 题意：若把给定字符串的所有不同回文子串放到一个集合内，求集合内有多少对回文子串满足其中一个是另一个的子串。 思路： 建好回文自动机 若设 a
来自 uniHk00 -
uniHk 2020-01-02 20:51:01
Virus synthesis（回文自动机，DP）
Virus synthesis 回文自动机好题！ 题意：初始有一个空串，然后通过两种操作得到目的串t，求最少操作数。两种操作分别为： 在字符串前面或者后面任意加一个字符 在字符串前面或者后面加上当前字符串的镜像 思路： 思考一下，花费（操作数）要最小（少），那肯定操作2
来自 uniHk00 -
uniHk 2020-01-02 20:51:22
杭电多校2019-5B-Three arrays(01trie+最优匹配)
Three arrays 赛场上想了半年都没有一点思路。。。看了题解发现原来是我学过的东东。。。（标题我瞎编的名字） 题意：给了一个大小为 1 e
来自 uniHk00 -
uniHk 2020-01-02 20:51:42
康托展开
康托展开 什么是康托展开？ 就是关于全排列中某个排列的排名的问题 给出一个全排列，求出它是第几个全排列，这就叫康托展开 给出一个全排列的长度以及它的排名，让你求出这个全排列，这叫逆康托展开 （以上全排列都是从
来自 uniHk00 -
uniHk 2020-01-02 20:52:03
洛谷-P4287 双倍回文(回文自动机)
双倍回文 刚刚用Manacher写了一遍这个题，现在换种写法，舒服！！！优美的half数组求法 （Manacher的简单写法请走这里) 题意：若一个回文串左半部分和右半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。 思路：
来自 uniHk00 -
uniHk 2020-01-02 20:52:23
洛谷-P4287 双倍回文(Manacher)
双倍回文 Manacher算法用的还是不够熟悉啊，被卡了好久。。。一会再写个回文自动机的做法吧 清晰的回文自动机写法 题意：若一个回文串左半部分和有半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。 思路： 由于双倍
来自 uniHk00 -
uniHk 2020-01-02 20:52:44
回文自动机
回文自动机 小小总结： 别忘了写上初始化！ 当字符串下标从 0 0 0开始时，
来自 uniHk00 -
uniHk 2020-01-02 20:53:04
洛谷 P-2178 品酒大会(后缀自动机)
品酒大会 又一道黑题！以为自己 O ( n )
来自 uniHk00 -
uniHk 2020-01-02 20:53:25
找相同字符(后缀自动机)
找相同字符 题意：给定两个字符串，在两个字符串中任选子串，求两子串相同的方案数 思路： 用后缀自动机处理两个字符串，一般考虑在中间插入一个用不到的字符（比如’#’），然后将它们组成一个串(后来发现好像不能插’#’，毕竟我数组第二维只开了26的大小；然后有一个方法就是把数组开成27的，然后
来自 uniHk00 -
uniHk 2020-01-02 20:55:05
洛谷-P3804 后缀自动机板子题
后缀自动机板子题 题意：给了一个字符串，然后里面有些子串出现次数大于1，求这种子串的出现次数乘以子串长度的最大值。 思路： 正常建好后缀自动机，将所有的np节点出现次数赋值为1 记录所有的父节点有几个儿子(不是后缀自动机上的儿子数，而是parent tree上的儿子数) 利用to
来自 uniHk00 -
uniHk 2020-01-02 20:55:26
后缀数组
推荐博客 先记录个板子 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m
来自 uniHk00 -
uniHk 2020-01-02 20:55:46
洛谷 P-4045 密码(AC自动机+状态压缩+数位DP+乱搞)
洛谷 P-4045 密码 记AC的第一道黑题！ 题意：已知一段密码包含了一些字符串，然后求满足条件的密码有多少个，数量小于42时还得全部输出 思路： 一开始WA了两个点，不知道WA的什么，索性把读入的字符串去重了，实际上不需要 建好AC自动机，同时记录当前点是哪个字符串的结尾，方便
来自 uniHk00 -
uniHk 2020-01-02 20:56:07
洛谷 P3041 视频游戏的连击Video Game Combos(AC自动机+拓扑排序+数位DP)
洛谷 P3041 视频游戏的连击Video Game Combos 难度一般，不过这个数位DP其实应该叫做记忆化搜索 题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。 思路：
来自 uniHk00 -
uniHk 2020-01-02 20:56:28
洛谷 P-2292 L语言(AC自动机)
洛谷 P-2292 L语言 一道比较简单的题，结果自己脑补了各种奇葩(错误)的判断，搞了一个多小时。。。 题意：用已知字典去识别一个串，求最长可识别前缀（指能将此前缀分解为字典里面的单词） 思路： 建好AC自动机，记录好每个点所代表的字符串的长度 拿要匹配的串从前往后匹配，若某个点
来自 uniHk00 -
uniHk 2020-01-02 20:56:48
洛谷-P4052+P3311 （AC自动机+数位DP）
洛谷-P4052 文本生成器 题目地址 虽然这题应该称为记忆化搜索，但是就想当做数位DP(QAQ) 一开始数组开小了，导致了WA，TLE，RE以及两个AC，深深的体会到了数组开小了什么错误都有，哈哈 题意：给出一个字典，求长度为M且包含字典中至少一个单词的文本有多少个。 思路： 虽
来自 uniHk00 -
uniHk 2020-01-02 20:57:09
AC自动机(Automaton)
小小总结 千万记住insert完以后要build!!!老是忘掉QAQ insert函数就只是trie数的插入函数，可在结尾根据条件打一些标记 build函数(构建fail树)，主要利用BFS match函数中跑fail树其实就是反复跑后缀 fail树上倒过来建树以后可以进行很
来自 uniHk00 -
uniHk 2020-01-02 20:57:30
Manacher算法
洛谷-P3805板子题 关键点: 要有两个字符串，且处理后的字符串长度略大于原串2倍（肯定 < 2
来自 uniHk00 -
uniHk 2020-01-02 20:57:50
后缀自动机
最最详细的解析 基础学习 简洁明了的讲解 小小总结 总状态数不超过 2 n −
来自 uniHk00 -
uniHk 2020-01-02 20:58:11
牛客多校1-H XOR(线性基)
题目链接 题意：给定n个整数，求满足子集异或和为0的子集大小之和。 题解：相当于求每个数出现在子集中的次数之和。 先对n个数求线性基，设线性基大小为r，可以分别计算线性基内数的贡献和线性基外数的贡献 线性基外：共n-r个数，枚举每个数x，将线性基外剩余的n-r-1个数任意排列，显然共
来自 uniHk00 -
uniHk 2020-01-02 20:58:31
HDU-6579 Operation(多校1B)(线性基)
终于又做了一道线性基！ 前缀线性基求区间最大异或值 Operation Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1073 Ac
来自 uniHk00 -
uniHk 2020-01-02 20:58:52
洛谷-P1169 棋盘制作(悬线法)
国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8 × 8
来自 uniHk00 -
uniHk 2020-01-02 20:59:12
计算几何(模板总结)
极为舒服的 计算几何终极模板+总结 小知识点 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #
来自 uniHk00 -
uniHk 2020-01-02 20:59:33
洛谷-食物链(扩展域并查集)
原题地址 食物链 动物王国中有三类动物 A , B ,
来自 uniHk00 -
uniHk 2020-01-02 20:59:53
牛客-game with numbers(筛法)
game with numbers 给定大小为 n n n的集合 S
来自 uniHk00 -
uniHk 2020-01-02 21:00:14
树链剖分(洛谷P3384模板题)
题目描述 如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z
来自 uniHk00 -
uniHk 2020-01-02 21:00:34
凸包模板(Graham)
废话不多说，直接上模板 #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 using namespace std;
来自 uniHk00 -
uniHk 2020-01-02 21:00:54
LCA(最近公共祖先)
洛谷最近公共祖先模板题 题目描述：给出一棵有 N N N个节点的树，有
来自 uniHk00 -
uniHk 2020-01-02 21:01:15
树状数组求区间最值
闲谈一下 树状数组最基本的功能是加速前缀和的更新。 查询一个数组的前缀和本来是O(1)的复杂度，用树状数组则为O(logn)。 但树状数组优点在于单点更新时复杂度为O(logn)，而正常的为O(n)，这也就使得树状数组能够进行大规模的更新。 虽然查询速度(O(logn))稍有些慢(相对于O(1)
来自 uniHk00 -
铁柱锈死了 2020-01-02 21:01:35
python题解
解释：菲波那切数列本质 class Solution: def rectCover(self, number): # write code here if number == 0: return 0 if number
来自 铁柱锈死了30 -
uniHk 2020-01-02 21:01:56
洛谷-P3975 弦论(后缀自动机板子题)
弦论 一道板子题，让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&，导致内存爆了，2333，果然还是传引用好 题意：求字典序第K小子串以及本质不同的第K小子串 思路： 正常的建好后缀自动机 由于处理一个节点有多少endpos以及经过一个节点有多少子
来自 uniHk00 -
uniHk 2020-01-02 21:02:16
牛客-小w的基站网络(计算几何)
链接：https://ac.nowcoder.com/acm/contest/923/D 来源：牛客网 题目中隐含条件是给的图是一个 DAG，那么就是一个 DAG上求单源最短路的问题。首 先是肯定能写出一个 O
来自 uniHk00 -
uniHk 2020-01-02 21:02:37
奇偶染色、二分图着色
利用DFS 由于每个顶点和每条边都只访问了一次，因此 复杂度为O(V+E) const int maxn = 1e4+10; vector<int> g[maxn]; int n; //顶点数 int color[maxn]; //顶点i的颜色，1 or -1 bool dfs(
来自 uniHk00 -
uniHk 2020-01-02 21:02:57
线性基(线性无关的基底)
概述 所谓线性基，就是线性代数里面的概念。一组线性无关的向量便可以作为一组基底，张起一个线性的向量空间，这个基底又称之为线性基。这个线性基的基底进行线性运算，可以表示向量空间内的所有向量，也即所有向量可以拆成基底的线性组合。 定义 设数集
来自 uniHk00 -
uniHk 2020-01-02 21:03:17
概率DP
HDU 4089 Activation(推导公式) Activation Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5214 Ac
来自 uniHk00 -
uniHk 2020-01-02 21:03:38
数学（杂记）
逆元 逆元满足： a ∗ i n v
来自 uniHk00 -
uniHk 2020-01-02 21:03:58
强连通分量-tarjan缩点
强烈推荐的tarjan解释 HDU 3861 The King’s Problem 缩点后得到新图，在新图上跑最小路径覆盖，得到答案 The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/3
来自 uniHk00 -
uniHk 2020-01-02 21:04:19
数位dp练习题
随便记录几个题， 防止连数位dp的思路都忘了，2333 数位dp 先将上限各位保存到num数组 从高位到低位dfs（暴力） 记忆化，优雅的暴力，否则就是O(n)的算法了，对单个数据也有很大的加速 pos为-1时以及记忆存在时可直接返回 关键：时刻记住判断条件，做到不重不漏
来自 uniHk00 -
uniHk 2020-01-02 21:04:39
树的重心和直径
树的重心 性质： 最大的子树最小 找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样，则这两个点都是重心（即重心可以有两个） 把
来自 uniHk00 -
uniHk 2020-01-02 21:05:00
高斯消元法（模板）
高斯消元法（列选主元法） 唯一解：判定存在性并求值 a a a数组存增广矩阵（第
来自 uniHk00 -
uniHk 2020-01-02 21:05:20
KMP+扩展KMP
KMP(三位发明者名字首字母) next数组表示t[j]以前最长相同前缀后缀 若下标从0开始(以下模板就采用这种方式)，next[ i ] 表示前面下标0~i-1的字符串前缀和后缀相等的最大长度为 next[ i ] 。 若下标从1开始，则next[ i ] 表示前面下标1~i - 1的字符串中
来自 uniHk00 -
uniHk 2020-01-02 21:05:40
最大团+极大团计数(HDOJ 1530+POJ 2989, Bron-Kerbosch )
极大团：无法从图中再加入一个顶点使得此顶点集的顶点两两相连的顶点集 因此单个顶点也可能是一个极大团 最大团：一个包含顶点数最多的极大团 最大独立集=补图的最大团 定理：最大独立集=补图的最大团，最大团=补图的最大独立集 Bron-kerbosch模板 说明 all-已取顶点集，some
来自 uniHk00 -
uniHk 2020-01-02 21:06:01
稳定婚姻匹配(Stable Match， HDOJ 1435， HDOJ 1914， 详解)
稳定婚姻匹配 HDOJ 1435 Stable Match(此例基于发射点优先的匹配，但题目并未明确表明) Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submiss
来自 uniHk00 -
uniHk 2020-01-02 21:06:21
拓扑排序总结(Kahn算法)
随便记录点东西 在拓扑排序中，排序结果唯一当且仅当所有顶点间具有全序关系。 快速排序不是稳定的（偏序关系），因为相同元素之间的关系无法确定。 插入排序是稳定的（全序关系），因为相同元素可以通过位置的先后增加关系。 检测某DAG是否为全序关系，只需先进行拓扑排序，再检测结果中所有相
来自 uniHk00 -
uniHk 2020-01-02 21:06:42
2-Sat
2-Sat 算法 简介 什么是2-SAT呢？就是有一些集合，每个集合中有且仅有两个元素，同时每个集合需要选择一个作为代表，集合间的元素存在一定的选择关系，求解可行性及可行方案。 关键：连边(从"一定不能"中产生出"一定能") 2-SAT算法本身并不难，
来自 uniHk00 -
uniHk 2020-01-02 21:07:03
图论(要点)
独立集 独立集是指图的顶点集的一个子集,该子集的导出子图不含边.如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集.一个图中包含顶点数目最多的独立集称为最大独立集。最大独立集一定是极大独立集，但是极大独立集不一定是最大的独立集。 支配集 与独立集相对应的就是支配集，支配
来自 uniHk00 -
uniHk 2020-01-02 21:07:23
网络流（持续更新）
最大流模板（含三种模板） 最后一种最快， 前两种彼此彼此 紫书模板 #include<cstdio> #include<algorithm> #include<cstdlib> #include<cmath> #include<cstrin
来自 uniHk00 -
uniHk 2020-01-02 21:07:43
二分图匹配（持续更新）
二分匹配核心算法：匈牙利算法（最大流的写法后续更新） 注意：匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值 先上匈牙利算法基础模板（求最大匹配数） bool lj[MAXN][MAXN], vis[MAXN]; int link[MAXN]; int n; bool find(
来自 uniHk00 -
uniHk 2020-01-02 21:08:04
欧拉筛+欧拉函数+莫比乌斯函数
原理、思想 通过已知素数及当前自然数筛掉后面的合数。 同时让每一个合数只被筛去一次，摒弃重复的筛除操作。 记忆要点 两个数组：一个vis[]， 一个prime[]。 循环从2开始， 直到所给的上限n处（或者直接maxn）。 无论当前数是否是质数， 都要进行后续合数的
来自 uniHk00 -
uniHk 2020-01-02 21:08:24
线段树（附究极详解）
详解请点击此处 http://blog.csdn.net/zearot/article/details/48299459 递归版 （我的)线段树要点 开数组的时候开到4*n即可。 若只涉及线段树的点修改或要进行单点查询，则要记录每个单点区间的编号（用fat数组），并在修改此单点区间后
来自 uniHk00 -
uniHk 2020-01-02 21:08:45
最短路(最长路)
Dijkstra 补充：求次短路，只需要多维护一个“短路”就行了； 但在维护次短路时，要记得把更新前的最短路与更新后的最短路swap一下，留着给次短路更新； 注意：不能处理负边权， 有负边权就换SPFA， 当然也不能求最长路。 以下代码以HDOJ 1874(畅通工程续) 为例 题目链接 简洁好
来自 uniHk00 -
鬼鬼@ 2020-01-02 21:08:44
听说你也想知道_Java垃圾回收算法
今天就跟你一块知道知道垃圾回收算法 内容参考《深入理解Java虚拟机》 要谈垃圾回收，首先我们得知道究竟谁是垃圾？ 垃圾回收主要关注的是堆中的内存，而堆中存放的是各种各样的的对象实例，也就是说，我们要找到那些已经“死掉”的对象，怎么判断对象死没死呢，有一种非常简单理解的算法—引用计数算法 给对象
来自 鬼鬼@10 -
uniHk 2020-01-02 21:09:25
树状数组（一维+二维）
树状数组 原理思想 利用二进制提高对大数组的操作速度，但存储空间不变，依旧需要开出原数组大小。 可当做一种快速的前缀和。 每次更新与每次查找都是O(logn)，即更新变慢，但查找速度得到极大的提高。 缺点：无法删除和插入元素 主要函数（lowbit、add、sum） 1.
来自 uniHk00 -
uniHk 2020-01-02 21:09:46
字典树（Trie树）
字典树（Trie树，单词查找树） 基本要点 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。 基本操作 查找、插入、删除 实现过程 从根节点开始
来自 uniHk00 -
不见武陵豪杰墓 2020-01-02 21:15:19
设计模式之创建型
简单工厂 工厂方法 抽象工厂 建造者模式 原型模式之浅拷贝 原型模式之深拷贝 单例模式 恶汉式 懒汉式
来自 不见武陵豪杰墓00 -
npcxh 2020-01-02 21:43:23
POJ 3253 Fence Repair
Description Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,00
来自 npcxh00 -
枫201906201702851 2020-01-02 21:44:23
[编程题]第一个只出现一次的字符
O(n)极简内存版 public class Solution { public int FirstNotRepeatingChar(String str) { int[] counts = new int[58]; for(int i = 0; i <
来自 枫201906201702851230 -
npcxh 2020-01-02 21:44:45
POJ P1328 Radar Installation
Description Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating
来自 npcxh00 -
npcxh 2020-01-02 21:46:11
POJ 2385 Apple Catching
Description It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, e
来自 npcxh00 -
不见武陵豪杰墓 2020-01-02 21:46:48
设计模式之结构型
适配器模式 桥接模式 组合模式 外观模式 装饰模式这里装饰类的display调用了父类的display(),和自己的setScrollBar()方法。起到装饰其他对象的作用。 ***模式
来自 不见武陵豪杰墓00
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
