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

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

模板——图论

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\)。

G. Omg Graph

https://codeforces.com/contest/2117/problem/G

给定无向带权连通图，定义一条路径的花费为：路径经过的边中，边权最大值 + 最小值。求从 \(1\) 到 \(n\) 路径中的最小花费（注意不一定是简单路径）。

\(2≤n≤2⋅10^5,n−1≤m≤\min(2⋅10^5,n(n−1)/2),1≤u,v≤n,1≤w≤10^9\)