Dawn-K's Blog

「CodeNote」次小生成树

次小生成树介绍次小生成树是就是第二小的生成树.其权值可能和最小生成树一样,也可能稍大于最小生成树. 另外还有严格最小生成树,就是指权值大于最小生成树的最小的生成树,以下先介绍非严格的. 算法次小生成树有现有的模板,思路主要是魔改最小生成树的模板.基于Prim和Kruskal . 在求出最小生成树(以下简称mst)后,尝试将其他边加入,这样必然会生成环,去掉环中除...

Posted by Dawn-K's Blog on September 26, 2019

「CodeNote」 JAVA简单语法

JAVA简单语法简介总结一下java的简单语法,比赛用格式 1 2 3 4 5 6 7 8 9 10 // 注意java没有 long long ,只有long import java.io.*; import java.util.*; import java.math.BigInteger; Scanner cin = new Scanner(new BufferedI...

Posted by Dawn-K's Blog on September 22, 2019

「CodeNote」 19牛客第四场D(数学+思维)

19牛客第四场D(数学+思维) 题目链接题目给出一个数n,要求输出尽可能少的一组数,使得这一组数或的结果恰好等于n,而且给出的数都是3的倍数,题目保证一定有解. 思路这个题咋看之下不太好做,因为3的倍数在二进制上并没有明显规律. 显然我们发现如果$n$本身就是3的倍数的话,那么直接输出n即可. 问题就在于如果$n$不是3的倍数的情况. 关于这种构造题,我们还是...

Posted by Dawn-K's Blog on September 17, 2019

「CodeNote」 19牛客多校第四场C(枚举+前缀和+单调栈)

19牛客多校第四场C(枚举+前缀和+单调栈) 题目链接题意给你两个长度为$n$的序列,第一个称为$a$,第二个称为$b$ .然后求$\displaystyle \max_{1 \le l \le r \le n} {min(a_{l \dots r}) \times sum(b_{l \dots r})}$ 分析首先不难想到通过前缀和以及ST表优化只有,此题有$O(n...

Posted by Dawn-K's Blog on September 17, 2019

「CodeNote」线性基

线性基参考资料参考资料2 模板来源概述线性基是一种擅长处理异或问题的数据结构.设值域为[1,$N$]，就可以用一个长度为$\lceil \log_2N \rceil$的数组来描述一个线性基。特别地，线性基第$i$位上的数二进制下最高位也为第$i$位。性质原序列里面的任意一个数都可以由线性基里面的一些数异或得到(也能异或得到一些不存在于集合的数) 线...

Posted by Dawn-K's Blog on September 14, 2019

「CodeNote」 __int128

__int128 介绍这是个玄学东西，应该是只能Linux评测机可以使用。但是能在使用的情况下还是非常方便的。 __int128（注意有两个下划线），也就是128位的整数数据类型.可以用scanf("%lld")方式输入(但绝对不能用cin&cout),不会报错,但是一般是自己写输入输出,或者仅仅在中途会爆数据范围的地方使用. 模板 1 2 3 4 5 6 7 8 9 1...

Posted by Dawn-K's Blog on August 19, 2019

「CodeNote」从KMP到AC自动机

从KMP到AC自动机 KMP KMP是个非常常见的算法了，但是一直没有详细总结，在此总结一下。简介 KMP算法是用于解决这样的问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置. 我们假设S的长度是n，P的长度为m，则暴力匹配的最坏复杂度是O(n*m) ,非常爆炸。因为其中间有非常多的重复比较，所以就从这个角度着手优化。 KMP算法通过模式串自身的性质，来减少匹配的...

Posted by Dawn-K's Blog on August 9, 2019

「CodeNote」 K短路

K短路简介 K短路是个图论中的著名问题，即给出一个图，给出起点和终点，要求输出第k短的路的长度（第1短的就是最短路，第2短的就是次短路）思想这个地方采用了A*算法（第一次写关于这个算法的模板）。我们慢慢分析。首先，用BFS，如果不设置vis[]数组，也就是让点只要可达就直接扩展，不考虑重复的情况下，第k次扩展到终点的路就是k短路。但是显然其时空复杂度非常高。我们就针对这个特点进...

Posted by Dawn-K's Blog on August 7, 2019

「CodeNote」马拉车算法

马拉车算法参考资料 [TOC] 简介马拉车算法是一种在O(n)时间内求一个字符串的最长回文子串的算法思路对于最长回文子串,我们可以有很多朴素算法比如穷举所有子串,然后验证这些子串是否是回文的,这样的复杂度是O(n^3), 比如我们遍历数组,对于每一个元素,我们都认为其是某个回文子串的中心,我们同时向两边伸展,然后取其中的最大值,这样的算法的复杂度是O...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」随手记

随手记链式前向星(临接表优化版) SPFA算法(解决负权图，如果瞎优化会变成指数复杂度) 反向建图(这个应该是和路径输出有关，具体再分析) 最大连续子序列和(动态规划大法好 O(n)复杂度)，或者也可以维护前缀和最小值，给出阶梯博弈(尼姆进阶版)先手必胜的条件：当且仅当所有奇数上的台阶的石子...

Posted by Dawn-K's Blog on August 6, 2019

Dawn-K's Blog

「CodeNote」次小生成树

「CodeNote」 JAVA简单语法

「CodeNote」 19牛客第四场D(数学+思维)

「CodeNote」 19牛客多校第四场C(枚举+前缀和+单调栈)

「CodeNote」线性基

「CodeNote」 __int128

「CodeNote」从KMP到AC自动机

「CodeNote」 K短路

「CodeNote」马拉车算法

「CodeNote」随手记

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」 次小生成树

「CodeNote」 JAVA简单语法

「CodeNote」 19牛客第四场D(数学+思维)

「CodeNote」 19牛客多校第四场C(枚举+前缀和+单调栈)

「CodeNote」 线性基

「CodeNote」 __int128

「CodeNote」 从KMP到AC自动机

「CodeNote」 K短路

「CodeNote」 马拉车算法

「CodeNote」 随手记

FEATURED TAGS

ABOUT ME

FRIENDS

「CodeNote」次小生成树

「CodeNote」线性基

「CodeNote」从KMP到AC自动机

「CodeNote」马拉车算法

「CodeNote」随手记