HLAIA-光子

2025牛客暑期多校1 E. 无尽的梯子 Time limit: 2 seconds Memory limit: 512 megabytes 在古老的平方王国，居民ccc (c=1,2,3,…)(c = 1,2,3,\ldots)(c=1,2,3,…)住在离地面c2c^2c2单位高的石柱上。 为了方便大家串门，平方国王打造了不同长度的梯子，长度为ddd的梯子可以让高度差的绝对值恰好为ddd的两个居民互相拜访。由于预算有限，长度为ddd的梯子被打造当且仅当存在两个居民的高度差的绝对值恰好为ddd，且同一长度的梯子仅会打造一架。 这些梯子按长度从小到大依次编号1,2,3,…1,2,3,\ldots1,2,3,…。这天居民aaa想要拜访居民bbb，你需要找出他们所用梯子的标号。 Input 输入的第一行包含一个整数TTT (1≤T≤104)(1 \leq T \leq 10^4)(1≤T≤104)，表示测试数据的组数。对于每组测试数据： 仅有的一行包含两个整数aaa和bbb (1≤a,b≤109,a≠b)(1 \leq a, b \leq 10^9, a \neq...

欧几里得算法(辗转相除法) 求最大公约数 C++的库有 __gcd()函数，赛时推荐直接用这个。博文里讲讲原理和实现 原理是：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数 gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b) 用递归来实现 123int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b);} 最小公倍数 先求最大公约数gcd(a,b) 123int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b);} 最小公倍数 lcm(a,b)lcm(a,b)lcm(a,b)...

Python学习笔记 python是最好的语言.cpp 本篇文章用来记录py基本语法的概览。 可以去菜鸟教程上学习py的语法，菜鸟上有详细且免费的文本教程。 基本语法 标识符 python的标识符命名规则和C++相差无几，略有不同的是，py标识符长度没有限制，但还是以简洁性和区分性为原则。 关键字 py标准库提供了一个keyword模块，可以输出当前版本的所有关键字。 1234import keywordprint(keyword.kwlist)['False', 'None', 'True', 'and', 'as', 'assert', 'async', 'await', 'break', 'class', 'continue', 'def', 'del', 'elif',...

差分 差分是前缀和的逆运算，运用于区间修改和询问。当对数据集A的某个区间做修改时，引入差分数组D，只需要修改这个区间的端点，就能记录整个区间的修改，这个修改的复杂度为O(1) 。当所有修改都完成后，再利用差分数组计算出新的A。 差分数组D[]的定义是：D[k] = a[k] - a[k-1]，a[]是原数组 显然，a[i] = D[1]+D[2]+...+D[i]，a[]是D[]的前缀和 例如，把数组区间[L,R]内的每个元素都加上d，只需要对应的差分数组D[]做以下操作： 把D[L]加上d：D[L] += d; 把D[R+1]减去d:D[R+1] -= d; D[]只会修改区间[L,R]内的值，不会修改到区间外的，要查询a[i]时，做一个D[i]的前缀和即可 以HDU 1556 为例 题目 代码 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;const int maxn = 1e6+1;int a[maxn],D[maxn];int...

概念与公式 完全图 完全图（Complete Graph）是一个简单的无向图，其中每一对不同的顶点之间都恰好有一条边相连。换句话说，完全图是一个所有顶点都相互连接的图。 完全图的性质包括： 顶点数为(n)的完全图有(n(n−1)2)(\frac{n(n-1)}{2})(2n(n−1)​)条边。 完全图中的每个顶点的度数都是(n-1)。 完全图是连通的，且是((n-1))-连通的。 完全图是((n-1))-正则的。 完全图(K_n)的色数是(n)，即需要(n)种颜色才能给图中的顶点着色，使得任何两个相邻的顶点颜色不同。 图的储存 邻接矩阵 用矩阵graph[N][N]储存边，N为节点总数。若 i 和 j 是直连的邻居，则用graph[i][j]表示边(i,j)的权值；若 i 和 j 不直连，一般把graph[i][j]复制无穷大。 邻接矩阵适合稠密图(大部分边都有权值)，不适合稀疏图(大部分边都无穷大)。 邻接矩阵的空间大小是N2。能表示有向边或无向边，若是无向图，那么边 i -> j...

二叉树 三种遍历 前中后序遍历的区别其实就是根节点的位置不同： 前序遍历是 根–左子–右子 中序遍历是 左子–根–右子 后序遍历是 左子–右子–根 前序遍历（Preorder Traversal） 顺序：根节点 → 左子树 → 右子树 特点：先访问根节点，再递归遍历左右子树。 示例： 12345 1 / \ 2 3 / \4 5 前序遍历结果：1, 2, 4, 5, 3 中序遍历（Inorder Traversal） 顺序：左子树 → 根节点 → 右子树 特点：先遍历左子树，再访问根节点，最后遍历右子树。 示例： 同一棵树的遍历结果：4, 2, 5, 1, 3 后序遍历（Postorder Traversal） 顺序：左子树 → 右子树 → 根节点 特点：先递归遍历左右子树，最后访问根节点。 示例： 同一棵树的遍历结果：4, 5, 2, 3, 1 完全二叉树 完全二叉树的性质： 对于任意一个节点iii，其父亲节点是i2\dfrac{i}{2}2i​，左子节点是2×i2 \times i2×i，右子节点是2×i+12 \times...

快速幂 以下是快速幂的模板 123456789int fastPow(int a,int n){//计算aⁿ int ans=1; //用ans返回结果 while(n){ //把n看成二进制数，逐个处理它最后一位 if(n&1) ans*=a; //&按位与操作，如果n的最后一位是1，表示这个地方需要参与计算 a*=a; //递推：2次方--4次方--八次方··· n>>=1; //n右移一位，把刚处理过的n的最后一位去掉 } return ans;} 通常题目都会要求模p，根据模的性质： (a+b) % p=(a%p + b%p) %p(a+b)\ \% \ p = (a \% p \ + \ b \% p)\ \% p (a+b) % p=(a%p + b%p) %p (a×b) % p=(a%p ×b%p) %p(a \times b)\ \% \ p = (a \% p \ \times b \% p) \ \%...

组合数学 容斥原理 集合 SSS 的子集 A1A_1A1​ 有性质 p1p_1p1​ ，A2A_2A2​ 有性质 P2P_2P2​ ， …\dots… ， AnA_nAn​ 有性质 PnP_nPn​ 。 那么，集合 SSS 中具有性质 P1,P2,…,PnP_1,P_2,\dots,P_nP1​,P2​,…,Pn​ 的集合个数为 ∣⋂i=1nAi∣=∑i=1n∣Ai∣−∑1≤i≤j≤n∣Ai∩Aj∣+∑1≤i≤j≤k≤n∣Ai∩Aj∩Ak∣−⋯+(−1)n+1∣∩i=1nAi∣\Big|\bigcap_{i=1}^nA_i \Big| = \sum_{i=1}^n\left| A_i\right| - \sum_{1 \leq i \leq j \leq n} \left| A_i \cap A_j \right| + \sum_{1 \leq i \leq j \leq k \leq n} \left| A_i \cap A_j \cap A_k \right| - \dots + (-1)^{n+1} \left| \cap_{i=1}^n A_i...

算法竞赛中涉及博弈论的知识并不多 公平组合游戏 Nim游戏 Nim游戏是一个很经典的博弈论模型，这类题有个通法通解：求Nim和。以下面的题目为例 题目 给定 nnn 堆石子，每堆有 a[i]a[i]a[i] 个石子 ，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。 分析 类似于这种题，问是否有必胜策略，计算异或和(Nim和)。 定义异或和(Nim和)为： Nim=a1⊕a2⊕a3⊕⋯⊕anNim = a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n Nim=a1​⊕a2​⊕a3​⊕⋯⊕an​ 异或和 != 0 先手玩家有必胜策略，后手玩家输 异或和 == 0 先手玩家输，后手玩家有必胜策略 原因： 异或和 ≠ 0：意味着至少有一个堆的某些位是“不平衡”的，当前玩家可以通过调整某个堆的石子数，使异或和变为0，迫使对手进入必输局面。 异或和 =...

01背包 (这只是正式开始学习背包，但是由于做题的原因，之前已经接触了一些背包问题、零零散散地学了一些了) 01背包问题通常为：给定 nnn 种物品和一个背包，第 iii 个物品体积为 cic_ici​ ，价值为 wiw_iwi​ ，背包地容量为 CCC 。如何选择装入背包的物品，使装入背包中的物品的总价值最大？ 以 HDU 2602 为例 题目 用自底向上的递推完成转移过程， dp[i][j]dp[i][j]dp[i][j] 表示把前 iii 个物品(从第 111 个到第 iii 个)装入容量为 jjj 的背包中获得的最大价值。假设现在递推到 dp[i][j]dp[i][j]dp[i][j] ，分两种情况： (1) 第 iii 个物品的体积比 jjj 还大，则不能装入当前背包，直接继承前 i−1i-1i−1 个物品装入容量为 jjj 的背包，即 dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j] dp[i][j]=dp[i−1][j] (2)...