归档: 2021/11 | 葛济维的博客

2021

11

30

五指山(线性同余方程、扩展gcd)

大圣在佛祖的手掌中。我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d。现在大圣所在的位置记为 x，而大圣想去的地方在 y。要你告诉大圣至少要飞多少次才能到达目的地。注意：孙悟

2021-11-30 算法

模板题线性同余方程扩展gcd

29

Java全栈知识体系笔记

Java全栈知识体系笔记https://www.pdai.tech/md/outline/x-outline.html 面向对象的三大特性面向对象的三大特性：封装、继承、多态封装：利用抽象数据结构将数据和基于数据的操作封装起来，使其构成一

2021-11-29 笔记

Java 面试

28

JavaGuide阅读笔记

JavaGuide阅读笔记1.面向对象和面向过程的区别进程和线程：进程是对一个程序的抽象，进程的创建和销毁就是一个程序的开始和结束。进程是资源调度的最小单位，一个进程可以有多个线程。进程进行上下文切换较慢，而线程进行切换很快。进

2021-11-28 笔记

Java 面试

26

算法笔记（长期更新）

算法学习目录时空复杂度分析基础算法排序二分高精度前缀和与差分双指针算法位运算离散化区间合并数据结构链表与邻接表：树与图的存储栈与队列：单调队列、单调栈kmpTrie并查集堆Hash表树状数组线段树搜索与图论 DF

2021-11-26 算法

笔记算法模板

23

付账问题（贪心问题、均值不等式）

付账问题（贪心问题、均值不等式）付账问题几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 ai 元。幸运的是，所有人带的钱的总数是足够付账的

2021-11-23 算法

蓝桥杯贪心均值不等式

22

糖果传递（贪心）——《算法竞赛进阶指南》,微软面试题 , HAOI2008

糖果传递（贪心）糖果传递有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 1。求使所有人获得均等糖果的最小代价。输入格式第一行输入一个正整数 n，表示小朋友的个数。接下来

2021-11-22 算法

贪心

20

大臣的旅费(树的直径、dfs、bfs、树形dp)

大臣的旅费很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。

2021-11-20 算法

蓝桥杯树的直径 dfs 树形dp

18

交换瓶子(图论、环、置换群、贪心)

交换瓶子有 N 个瓶子，编号 1∼N，放在架子上。比如有 5 个瓶子： 2 1 3 5 4 要求每次拿起 2 个瓶子，交换它们的位置。经过若干次后，使得瓶子的序号为： 1 2 3 4 5 对于这么简单的情况，显然，至少需要交换 22

2021-11-18 算法

贪心图论环置换群

18

日志统计（滑动窗口，双指针问题）

日志统计小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。其中每一行的格式是： ts id表示在 ts 时刻编号 id 的帖子收到一个”赞”。现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长

2021-11-18 算法

蓝桥杯滑动窗口双指针

17

三体攻击(3维前缀和)

三体攻击三体人将对地球发起攻击。为了抵御攻击，地球人派出了 A×B×C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i,j,k)）的生命值为 d(i,j,k)。三

2021-11-17 算法

模板题前缀和

17

线性同余方程(扩展欧几里得算法)

线性同余方程给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 $a_i * x_i≡ b_i (mod\ m_i)$，如果无解则输出 impossible。输入格式第一行包含整数 n。接下来 n 行，每行包含一组

2021-11-17 算法

模板题数学知识同余扩展欧几里得算法

17

1维2维3维前缀和

应用前缀和主要应用于对区间内每个数进行加或减操作时，如果遍历区间进行操作，时间复杂度较高，在数据量大时无法AC，如果对差分数组进行操作的话，可以把时间复杂度降为O(1)，可以AC 下面设b[]数组为前缀和数组，s[]数组为原数组一维前缀和

2021-11-17 算法

算法模板前缀和