Jeffzuo的博客 | Jeffzzc Blog

保研机试训练Day-21

组合数

数论组合数1（递推法）给定 n 组询问，每组询问给定两个整数 a，b请你输出 C(a,b) mod(10^9+7) 的值。 #include<iostream> #include<algorithm> using namespace std; const int N = 2010, mod = 1e9 + 7; int c[N][N]; int n; v...

Posted by Jeffzzc on April 13, 2025

保研机试训练Day-20

中国剩余定理 && 高斯消元

数论中国剩余定理给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n], x ≡ **mi (mod** ai)。 #include<iostream> #include<cstring> #include<algorithm> using namespace std; typede...

Posted by Jeffzzc on April 12, 2025

保研机试训练Day-19

快速幂 && 裴蜀定理 && 扩展欧几里得算法

数论快速幂求逆元给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。 #include<iostream> #include<algorithm> using namespace std; typedef long long ll; // a^k mod p int qmi(int a...

Posted by Jeffzzc on April 11, 2025

保研机试训练Day-18

欧拉函数 && 快速幂

数论欧拉函数给定 n 个正整数 ai，请你求出每个数的欧拉函数。 #include<iostream> #include<cmath> #include<algorithm> using namespace std; int main(){ int n; cin >> n; while(n--){ ...

Posted by Jeffzzc on April 10, 2025

保研机试训练Day-17

约数

数论约数试除法求约数给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。 #include<iostream> #include<cmath> #include<algorithm> #include<vector> using namespace std; int n; vector<int...

Posted by Jeffzzc on April 9, 2025

保研机试训练Day-16

数论

数论质数试除法判定质数给定 n 个正整数，判定每个数是否是质数。 #include<iostream> #include<algorithm> #include<cmath> using namespace std; bool is_prime(int n){ if(n < 2) return false; for(in...

Posted by Jeffzzc on April 8, 2025

保研机试训练Day-15

最小生成树 && 二分图

最小生成树算法 Kruskal算法求最小生成树给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一...

Posted by Jeffzzc on April 7, 2025

保研机试训练Day-14

spfa && Floyd

spfa算法 spfa判断负环给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。 #include<bits/stdc++.h> using namespace std; const int N = 150010; int n,m; typedef pair<int,int> PII; int h[N...

Posted by Jeffzzc on April 6, 2025

保研机试训练Day-13

bellman-ford && spfa

bellman-ford算法给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。注意：图中可能存在负权回路。 #include<iostream> #include<cstring> #inclu...

Posted by Jeffzzc on April 5, 2025

保研机试训练Day-12

单源最短路

单源最短路算法朴素Dijkstra求最短路给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 #include<bits/stdc++.h> using namespace std; const int N = 510; const int INF...

Posted by Jeffzzc on March 31, 2025

Zecheng's Blog