离散化
例题 分析 离散化事实上就是当这个数据范围比较大的时候但是能用到的数比较少的时候需要用到的算法。就比如这个题，a_i 和 b_i 的数据范围超大但 n 的数据范围只有 2\times 10^5。这个时候我们可以将其压缩，使得所有内容之间没有空位。 以样例为例，实现如下图：
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
7月前
评论
区间问题
线性差分：植树节 题目描述 植树节快要到了，学校要组织志愿者去给树苗浇水。 有一排树苗，编号依次是 0, 1, 2, ... 。 现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [a_i, b_i]，表示第 i 个志愿者将区间 [a_i, b_i] 内的每一棵树都浇一次水。 例如某个
[ABC378C] Repeating 题解
[ABC378C] Repeating 题解 解题思路 我们需要为每个 A_i 找到它在序列 A 中上一次出现的位置。你可能第一想法是使用桶来进行记录当前数在此之前的位置是什么。普通的桶在这一题显然是开不了的，因为数据量达到了 10^9。但其实使用map进行存储也同样可以通过本题。用map的思路比较
2024NOIP模板代码复习专用文章
最短路 dijkstra题目 代码 #include<bits/stdc++.h> #define ll long long #define N 200001 // 最大的顶点数和边数 using namespace std; // 初始化全局变量 int a[N],n,m,ver[N],nxt
8月前
评论
Sakurako 和 Water 题解
问题概述 因为题面翻译很清楚且题面容易理解，在这里就不再解释了。 解题思路 读完题后，先看时间复杂度，再选择实现方法。一看 n\le500 ，直接 n^2 暴力就可以了。下面将具体讲解实现方法。 对角线独立处理： 矩阵中的每条主对角线可以单独进行操作，因为一次操作只影响一个正方形区域内的主对角线。
【2024】CSP-S 二轮考前模板代码大杂烩
2024NOIP模板代码复习专用文章 复习用的文章 最短路 dijkstra题目 P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 代码 #include<bits/stdc++.h> #define ll long long #define N 200001 //
8月前
评论
【分块】算法专题
分块 此文章列出了几种分块的常见用法涉及的模板题目和代码，便于理解和复习分块算法。 数列分块入门 1 【区间加法+单点查询】 题面 题目描述 给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，
9月前
评论
E - I Hate Sigma Problems (atcoder.jp)
此文章为临时文章。 E - I Hate Sigma Problems (atcoder.jp) 一、分析原始代码的问题 您的代码如下： #include<bits/stdc++.h> #define ll long long #define mem(x) memset(x,0,sizeof(x))
10月前
评论
Labyrinth
题目：Labyrinth 题目描述： 你正在玩一款电脑游戏。在其中一关，你位于一个 n 行 m 列的迷宫。每个格子要么是可以通过的空地，要么是障碍。迷宫的起点位于第 r 行第 c 列。你每一步可以向上、下、左、右中的一个方向移动一格，前提是那一格不是障碍。你无法越出迷宫的边界。不幸的是，你的键盘快坏
