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 b)(1≤a,b...

欧几里得算法(辗转相除法) 求最大公约数 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) 与其的关系为: gcd(a,b)∗lcm(a,b)=a∗bgcd(a,b)*lcm(a,b)=a*b gcd(a,b)∗lcm(a,b)=a∗b 因此 lcm(a,b)=(a∗b)/gcd(a,b)lcm(a,b)=(a*b)/gcd(a,b) lcm(a,b)=(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', 'els...

概念与公式 完全图 完全图（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 的权值是graph[i][j]=graph[j][i]；若是有向图，那么graph...

快速幂 以下是快速幂的模板 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) \ \% p (a×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 \right| ​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，迫使对手进入必输局面。 异或和 = 0：任何移动都会破坏平衡，使得对手可以采取策略让异或和再次归零，...

回溯与剪枝 当递归所衍生出的子节点不符合条件时，就该“看到不对劲就撤退”——中途停止并返回。这个思路就是回溯。在回溯中用于减少子节点的拓展函数就是剪枝函数。 其难度主要在于拓展子节点的时候如何构造停止递归并返回的条件。 以HDU 2553 N皇后为例 题目 不同行: old_x≠new_xold\_ x \not= new\_ xold_x=new_x 不同列: old_y≠new_yold\_ y \not= new\_ yold_y=new_y 不同对角线: abs(old_x−new_x)≠abs(old_y−new_y)abs(old\_ x - new\_ x) \not= abs(old\_ y - new\_ y)abs(old_x−new_x)=abs(old_y−new_y) 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;int n,lie[11]...

容斥原理 集合 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 \right| ​i=1⋂n​Ai...

ITA练习赛2 B 这道签到题我交了7发… 最初把题目看成了任意两个元素互素，结果怎么提交都不对，就发现看错题了… 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int n,a[maxn];map <int,int> ma;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; a[0] = -1; bool pd; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=2;i<=n;i++){ if(__gcd(a[i],a[i-1]) != 1){ cout << "-1\n"; ...