MGblog
让信息成为常识
-
离散化
例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：
22106 -
OI的一点点数论
排列数：A_n^m=\frac{n!}{(n-m)!} 组合数：C_n^m=\frac{n!}{m!(n-m)!} 最小公倍数：lcm[a,b]=\frac{a}{gcd(a,b)}\times b 余数公式（两两互推）： a=kb+r k=\lfloor{\frac{a}{b}}\rfloor r
0039
-
爆炸的平衡树, 替罪羊树 - 指针神教教主Defad
爆炸的平衡树, 替罪羊树 由于Defad不太喜欢旋转, 所以一般用替罪羊树. 这里写个博客介绍一下. 什么是二叉搜索树 可以维护一个集合, 相比于权值线段树 (动态开点) 的时间复杂度 \(\log{N}\) 空间复杂度 \(N \log{N}\), 二叉搜索树理论上来说只需要 \(\log{N}\
-
莫队2 这次需要带修改了 - 指针神教教主Defad
莫队2 这次需要带修改了 莫队1 走上骗分之路 实现修改 莫队是不支持修改的, 但是有后人加以改进, 就有了代修版本. 我们现在有一个东西叫时间轴 (类似函数式线段树的每个根都是关于某次之前的根修改或查询的), 每次询问都记录一下当前的时间轴, 每次修改都在时间轴上新建一个版本. typedef s
-
莫队1 走上骗分之路 - 指针神教教主Defad
莫队1 走上骗分之路 新坑介绍莫队, 第一篇是不带修的线性莫队. 什么是莫队 一种硬往两边扩展 (可能是收缩) 的玄学算法, 是老前辈莫涛老师发明的算法, 又因为莫老师进了国家队, 所以叫莫队. Google搜索需要搜索"Mo's Algo". 莫队能解决什么问题 很多, 只要 \([l, r]\)
1
C++算法
严选优品，精准分类
例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：
排列数：A_n^m=\frac{n!}{(n-m)!} 组合数：C_n^m=\frac{n!}{m!(n-m)!} 最小公倍数：lcm[a,b]=\frac{a}{gcd(a,b)}\times b 余数公式（两两互推）： a=kb+r k=\lfloor{\frac{a}{b}}\rfloor r
分块 此文章列出了几种分块的常见用法涉及的模板题目和代码，便于理解和复习分块算法。 数列分块入门 1 【区间加法+单点查询】 题面 题目描述 给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，
逆序对是指在一个数列中，任意两个数满足前面的数大于后面的数，这两个数就构成了一个逆序对。计算逆序对的目的是衡量一个数列“乱序”的程度。 逆序对的定义： 对于一个序列 a_1, a_2, ..., a_n ，如果存在 i < j ，并且 a_i > a_j ，那么 (a_i, a_j) 就称为一个逆序
战功统计 1 时间限制： 2 秒 内存限制： 128M 题目描述 小可将军统率着n个士兵，士兵分别编号为1~n。已知他们现在的战功 a[i]，要为他们统计接下来的战功，战功可以透支使用，即战功可能为负数 杀敌可以增加战功，且战功可以兑换物资，所有战功会有增有减，统称为战功的变化 将军经常爱拿某一段编
亲戚 时间限制：1秒 内存限制：128M 题目描述 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
计数排序和桶排序是两种不同的排序算法，但它们有一些相似之处。以下是对它们的详细解释： 计数排序 (Counting Sort) 计数排序是一种非比较排序算法，适用于对一定范围内的整数排序。其基本思想是利用数组下标作为值来记录每个数出现的次数，然后通过这些计数值直接构建有序的输出数组。 计数排序步骤：
2
C++算法模版题
严选优品，精准分类
最短路 dijkstra题目 代码 #include<bits/stdc++.h> #define ll long long #define N 200001 // 最大的顶点数和边数 using namespace std; // 初始化全局变量 int a[N],n,m,ver[N],nxt
题目：Labyrinth 题目描述： 你正在玩一款电脑游戏。在其中一关，你位于一个 n 行 m 列的迷宫。每个格子要么是可以通过的空地，要么是障碍。迷宫的起点位于第 r 行第 c 列。你每一步可以向上、下、左、右中的一个方向移动一格，前提是那一格不是障碍。你无法越出迷宫的边界。不幸的是，你的键盘快坏
题目：奇怪的电梯 题目描述： 假设一栋大楼有一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼（1 \leq i \leq N）上有一个数字 K_i（0 \leq K_i \leq N）。电梯只有四个按钮：开、关、上、下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的
题目：小猫爬山 题目描述： 翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了。翰翰和达达只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C_1, C_2, \dots, C_N。每辆缆车上
题目：P2622 关灯问题 题意： 有 m 盏灯，n 个开关。第 i 个按钮控制第 j 盏灯。 分三种情况： 输入 0 时，不管。 输入 1 时，灯必为关。 输入 -1 时，灯必为开。 求从全开到全关的最小步数。
3
C++题解
严选优品，精准分类
线性差分：植树节 题目描述 植树节快要到了，学校要组织志愿者去给树苗浇水。 有一排树苗，编号依次是 0, 1, 2, ... 。 现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [a_i, b_i]，表示第 i 个志愿者将区间 [a_i, b_i] 内的每一棵树都浇一次水。 例如某个
[ABC378C] Repeating 题解 解题思路 我们需要为每个 A_i 找到它在序列 A 中上一次出现的位置。你可能第一想法是使用桶来进行记录当前数在此之前的位置是什么。普通的桶在这一题显然是开不了的，因为数据量达到了 10^9。但其实使用map进行存储也同样可以通过本题。用map的思路比较
问题概述 因为题面翻译很清楚且题面容易理解，在这里就不再解释了。 解题思路 读完题后，先看时间复杂度，再选择实现方法。一看 n\le500 ，直接 n^2 暴力就可以了。下面将具体讲解实现方法。 对角线独立处理： 矩阵中的每条主对角线可以单独进行操作，因为一次操作只影响一个正方形区域内的主对角线。
此文章为临时文章。 E - I Hate Sigma Problems (atcoder.jp) 一、分析原始代码的问题 您的代码如下： #include<bits/stdc++.h> #define ll long long #define mem(x) memset(x,0,sizeof(x))
提示： 题解已在洛谷本题题解栏目展出，可选择进入洛谷查看此博客文章。 题目传送门：洛谷 / codeforces 题意简述 翻译已经给的很明确了，实际上就是给定 n 个点，然后 x 个操作： 选择 2 个不同的数
美妙数组题解 为了确认数组 a 是否美丽，我们需要找到两个不同的数 a_i 和 a_j（ 其中 1 \leq i, j \leq n 且 i \neq j），使得数组中的每个元素都能被 a_i 或 a_j 整除。如果这样的两个数存在，则数组是美丽的，否则不是。 解决方案： 对数组进行排序：这有助于快
