欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

图标是清爽葡萄柚汽水（确信）。

二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，强连通分量，Prim 算法，Kruskal 算法，Dinic 最大流，欧拉路。

模板——杂项

Clion 配置快捷键，KMP，LCA，SG 函数，二进制相关，数位 DP，费马平方和定理，对抗搜索。

模板——数据结构

ST 表，Trie 树，线段树，树状数组，并查集，动态开点线段树，主席树，lower_bound 用法，树套树，笛卡尔树，树链剖分。

模板——数学类

快速幂，质数线性筛，质因数分解，欧几里得（gcd），扩展欧几里得（exgcd），求欧拉函数 \(\varphi(x)\)，欧拉定理，扩展欧拉定理，中国剩余定理（CRT），在任意模意义下的逆元，同余最短路，组合数，Lucas 定理，卡特兰数，递推求逆元，拉格朗日插值，康托展开，高斯消元，矩阵快速幂。

• https://codeforces.com/gym/104090/problem/D

找规律 经过手动模拟几轮发现，设钱数总和为 \(s\)，则第一个人分得 \(2s/(n+1)\)，其余人分得 \(s/(n+1)\)。收敛速度很快。

I. Guess Numbers

https://codeforces.com/gym/104828/problem/I

• 求：! x y \(x\) 和 \(y\) 的值。
• 问：? a b 返回 \(\gcd(x+a,y+b)\) 的值。
• 限制询问次数：\(200\)。
• \(0≤x,y<2^{60},0≤a,b<2^{61}\)。

查询排序后的最大公约数

https://leetcode.cn/problems/sorted-gcd-pair-queries/description/

给你一个长度为 \(n(n\le10^5)\) 的整数数组 nums​，值域 \(5·10^4\) 。

两两组合出 \(n^2/2\) 个数对，对每个数对求出 gcd(nums[i], nums[j]) ，并放在一起升序排列成一个数组。

\(q(q\le10^5)\) 个查询，每次询问数组里下标为 \(q_i\) 的数是几。

Problem A

有 \(n\) 个字符串，\(t_1,t_2,…,t_n\)，这些字符串只由字符 s 和 h 组成。 定义这些字符串的连接为 \(t_1,t_2,…,t_n\) 首尾相接。

可以对这 \(n\) 个字符串进行任意次重排，希望重排后字符串的连接之中 sh 子序列出现次数最多，并求出这个最大值。

\(1≤n≤10^5\)，总长度不超过 \(10^5\)。