拓展欧几里得算法 还是数论 欧几里得算法 就是求最大公约数的辗转相除法。 数学公式 gcd⁡(a,b)={gcd⁡(b,a mod b),b≠0a,b=0\gcd(a, b)= \begin{cases} \gcd(b,a\bmod b) &,b\neq 0\\ a &,b=0 \end{cases} gcd(a,b)={gcd(b,amodb)a​,b=0,b=0​ 模板 12

洛谷题目传送门 | CF 原题传送门 本题难度严重低于橙题 思路 这道题思考时，不妨设第 iii 个三角形的高为 hih_ihi​，面积为 SiS_iSi​，同时，题目还有已知条件底为222。 根据三角形面积公式，我们可以得到： S=S1+S2+⋯+Sn=(h1+h2+⋯+hn)×22=h1+h2+⋯+hn=kS=S_1+S_2+\cdots +S_n=\dfrac{(h_1+h_2+\cdots

洛谷题目传送门 | CF 原题传送门 基础回文数判断题。 感觉题目翻译并不是很好，需要注意回文串中不能出现 222，例如 102011 0 2 0 110201 不能作为最终答案。 思路 直接把数组从 111 到 $\lfloor \frac{n}{2}\rfloor $ 扫一遍即可。 有以下几种情况需要分类讨论： 如果原串首尾不同但不是 222，即形如 101001010010100 这样的，

洛谷题目传送门 | SP 原题传送门 本题双倍经验，同主题库P2926 思路 又是一道桶的题。 首先暴力，对于 N=100000N=100000N=100000，复杂度 O(n2)O(n^2)O(n2)，显然超时。 考虑优化。 看题面，不难想到用桶记录每个数字的出现次数，只需要遍历数组找到比 aia_iai​ 小的数即可。 但是这样仍然超时，继续优化。发现遍历数组时没必要全遍历一边，只需要遍历到

洛谷题目传送门 | AT 原题传送门 思路 这道题考察了桶的思想。 定义两个桶，分别存放给出招牌中的每个字母的数量和配件包中的每个字母的数量 有两个小问题需要注意： 当招牌需要这个字母，而配件包里没有，直接输出 −1-1−1 并结束程序； 需要特判当配件包里的每个字符数量如果是 000，就要跳过本次循环，避免除数为 000。 思路不难，看看代码和注释就能理解吧 代码 123456789

洛谷题目传送门 | AT 原题传送门 思路 这道题考察了桶的思想。 定义两个桶，分别存放给出招牌中的每个字母的数量和配件包中的每个字母的数量 有两个小问题需要注意： 当招牌需要这个字母，而配件包里没有，直接输出 −1-1−1 并结束程序； 需要特判当配件包里的每个字符数量如果是 000，就要跳过本次循环，避免除数为 000。 思路不难，看看代码和注释就能理解吧 代码 123456789

洛谷题目传送门 | AT 原题传送门 思路 桶的思想。 用数组 ttt 存储 aaa 出现的次数，然后循环，用 kkk 减每个数出现的次数，看在哪个数时满足 k≤0k \leq 0k≤0 的条件，直接输出这个数的下标即可。 注意不开 long long\texttt{long long}long long 见祖宗 代码 12345678910111213141516171819202122#inc

洛谷题目传送门 | AT 原题传送门 思路 分析题目可以很简单地得到，如果满足 pi=ip_i=ipi​=i 的条件，那么交换 pip_ipi​ 和 pi+1p_{i+1}pi+1​ 后得到的结果一定是最优解。 我们要做的只是从前到后遍历一遍 ppp 数组，如果 pi=ip_i=ipi​=i 就交换 pip_ipi​ 和 pi+1p_{i+1}pi+1​，同时 ansansans 累加。 看到楼下

洛谷题目传送门 | CF原题传送门 这个题是让求输入的连续几个月份是否合法。 直接模拟就行了吧。 需要注意闰年的情况。 大体思路 先打表确定每个月的天数，因为有 242424 个月，所以需要注意包含平年和闰年的全部情况。 因为输入是带有空格的，所以预先打表的月份天数之间也要带有空格，我们可以按照 平年、平年、闰年、平年、平年 的顺序预打表。 大概是这个样子： 12// |

洛谷题目传送门 | AT原题传送门 思路 这其实是一道递推题。 打眼一看，这道题和P1255 数楼梯是差不多的，只不过是本题又新增了一个条件：有 mmm 个楼梯是坏的。 如果没有这个条件，我们可以定义，第 iii 阶楼梯的总方案数为 fif_ifi​，从题目中可以很容易得出：fi=fi−1+fi−2(i≥2)f_i=f_{i-1}+f_{i-2}(i \geq 2)fi​=fi−1​+fi−2​(