分类: 算法

24 篇文章

P5440 奇迹
本来以为自由活动时间给我了,洗完澡可以在机房享受,结果从5点调到7点,特此记录一下。 原题链接 [collapse title="题目描述"] 【XR-2】奇迹 题目背景 相信奇迹的人,本身就和奇迹一样了不起。——笛亚 《星游记》 题目描述 我们称一个日期为一个八位数,第 1~4 位构成年,第 5~…
CF1675G
题目大意 有 $ n $ 个箱子和 $ m $ 个小球,初始时第 $ i $ 个箱子有 $ a_i $ 个小球。每次操作可以将一个小球移到相邻的箱子里。求要使得最终数组 $ a_i \ge a_{i+1} $ 的最小操作次数 $ a_i $ 大于 $ 0 $ 。 解题思路 看完题解后发现是 dp 。…
CF1672A
题目大意 errorgorn与maomao90再进行一场比赛。有 $ n $ 段木头,每段长度为 $ a_i $ 。每个人可以将长度为 $ x $ 木头分为两段长度为 $ y $ 与 $ z $ 的木头, $ x \ y \ z $ 为正整数,且 $ x = y + z $ 。如果轮到一个人时,没有…
马拉车算法(manachar)
manachar (马拉车算法) 回文: 回文的定义十分简单,判断回文串的方法也很简单。对于一个字符串,只需要从他的最中心向两边扩展就足够了,可以将它称之为中心扩展法,我们的马拉车算法也是从中心扩展法扩展而来。 马拉车算法的运用之处: 对于一个字符串,询问它的字串中长度最大的回文串的长度。 显然,我…
高精度
以下为本人代码。 说明:(乘法为高精乘高精,除法为高精除低精) 高精度代码: #include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> using na…
倍增求区间最大值板子
日后在写解析(如果不鸽,大概率考试考完) #include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <cmath> usi…
判断质数
质数定义:一个数只能被1和自己整除,即因数只有1和本身 1.试除法 $O(\sqrt{N})$ 通过定义,我们清楚地明白,对于一个数n,我们只要判断它的因数有几个,就可以判断它是不是质数了。那么我们只要判断n能否整除2到n-1这个区间中的一个整数即可判断。 但是在数据过大时会有超时的现象,这时我们可…
最近公共祖先(LCA)
代码针对洛谷P3379 1.向上标记法 最朴素的求最近公共祖先的方法,两个子结点同时向上一个一个的跳,标记已经跳过的点,如果有一个点跳到了已经标记过的点,那么就说明这个点就是最近公共祖先。可以自己简单的推一下,查询的时间复杂度为 $ O(n) $ 。 2.倍增 总思路:用类似于二进制拆分的思想。 首…
浅谈树状数组
浅谈树状数组和线段树 树状数组 类比: 其实可以把树状树组简单的看成一个帮你求前缀和的树组,add为单点修改值,query(x)即为询问1到x的前缀和的值。(至少我是这样看的)。 简介: 树状数组和线段树具有相似的功能,但他俩毕竟还有一些区别:树状数组能有的操作,线段树一定有;线段树有的操作,树状数…
浅谈图论
链式前向星 众所周知,存图的方式有多种,例如邻接矩阵,邻接表,这两种一般初学者都在用,并且十分的便于理解和使用。但是当图的边数过大或者说点数较大时以上两种存图方式不是十分的合适。 所以说,这时就要用到我们的链式前向星了。本质上来说是用链表实现的临接表,先放代码。 int e[N],w[…