JiWei Ge
  文章分类
博客搭建 3 算法 14 摘抄 1 项目 1 笔记 4
五指山(线性同余方程、扩展gcd) 五指山(线性同余方程、扩展gcd)
大圣在佛祖的手掌中。 我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d。 现在大圣所在的位置记为 x，而大圣想去的地方在 y。 要你告诉大圣至少要飞多少次才能到达目的地。 注意：孙悟
2021-11-30 算法
模板题 线性同余方程 扩展gcd
算法笔记（长期更新） 算法笔记（长期更新）
算法学习目录时空复杂度分析 基础算法 排序二分高精度前缀和与差分双指针算法位运算离散化区间合并 数据结构 链表与邻接表：树与图的存储栈与队列：单调队列、单调栈kmpTrie并查集堆Hash表 树状数组 线段树 搜索与图论 DF
2021-11-26 算法
笔记 算法模板
付账问题（贪心问题、均值不等式） 付账问题（贪心问题、均值不等式）
付账问题（贪心问题、均值不等式） 付账问题 几个人一起出去吃饭是常有的事。 但在结帐的时候，常常会出现一些争执。 现在有 n 个人出去吃饭，他们总共消费了 S 元。 其中第 i 个人带了 ai 元。 幸运的是，所有人带的钱的总数是足够付账的
2021-11-23 算法
蓝桥杯 贪心 均值不等式
糖果传递（贪心）——《算法竞赛进阶指南》,微软面试题 , HAOI2008 糖果传递（贪心）——《算法竞赛进阶指南》,微软面试题 , HAOI2008
糖果传递（贪心）糖果传递 有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。 每人只能给左右两人传递糖果。 每人每次传递一个糖果代价为 1。 求使所有人获得均等糖果的最小代价。 输入格式第一行输入一个正整数 n，表示小朋友的个数。 接下来
2021-11-22 算法
贪心
大臣的旅费(树的直径、dfs、bfs、树形dp) 大臣的旅费(树的直径、dfs、bfs、树形dp)
大臣的旅费 很久以前，T王国空前繁荣。 为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。 为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
2021-11-20 算法
蓝桥杯 树的直径 dfs 树形dp
交换瓶子(图论、环、置换群、贪心) 交换瓶子(图论、环、置换群、贪心)
交换瓶子 有 N 个瓶子，编号 1∼N，放在架子上。 比如有 5 个瓶子： 2 1 3 5 4 要求每次拿起 2 个瓶子，交换它们的位置。 经过若干次后，使得瓶子的序号为： 1 2 3 4 5 对于这么简单的情况，显然，至少需要交换 22
2021-11-18 算法
贪心 图论 环 置换群
日志统计（滑动窗口，双指针问题） 日志统计（滑动窗口，双指针问题）
日志统计 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。 其中每一行的格式是： ts id表示在 ts 时刻编号 id 的帖子收到一个”赞”。 现在小明想统计有哪些帖子曾经是”热帖”。 如果一个帖子曾在任意一个长
2021-11-18 算法
蓝桥杯 滑动窗口 双指针
线性同余方程(扩展欧几里得算法) 线性同余方程(扩展欧几里得算法)
线性同余方程 给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 $a_i * x_i≡ b_i (mod\ m_i)$，如果无解则输出 impossible。 输入格式第一行包含整数 n。 接下来 n 行，每行包含一组
2021-11-17 算法
模板题 数学知识 同余 扩展欧几里得算法
三体攻击(3维前缀和) 三体攻击(3维前缀和)
三体攻击 三体人将对地球发起攻击。 为了抵御攻击，地球人派出了 A×B×C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。 其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i,j,k)）的生命值为 d(i,j,k)。 三
2021-11-17 算法
模板题 前缀和
1维2维3维前缀和 1维2维3维前缀和
应用前缀和主要应用于对区间内每个数进行加或减操作时，如果遍历区间进行操作，时间复杂度较高，在数据量大时无法AC，如果对差分数组进行操作的话，可以把时间复杂度降为O(1)，可以AC 下面设b[]数组为前缀和数组，s[]数组为原数组 一维前缀和
2021-11-17 算法
算法模板 前缀和
铁路与公路(Floyd) 铁路与公路(Floyd)
4074. 铁路与公路 某国家有 n 个城市（编号 1∼n）和 m 条双向铁路。 每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。 除了铁路以外，该国家还有公路。 对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存
2021-11-14 算法
模板题 Floyd 单源最短路
小朋友排队(树状数组) 小朋友排队(树状数组)
小朋友排队(树状数组） n 个小朋友站成一排。 现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。 开始的时候，所有小朋友的不高兴程度都是 0。 如果某个小朋友第一次被要求交换，则
2021-11-14 算法
树状数组 逆序对 模板题
1 / 2