Jeffzuo的博客 | Jeffzzc Blog

保研机试训练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

保研机试训练Day-11

树的深度优先遍历 && 树与图的广度优先遍历 && 拓扑排序

图的存储树的深度优先遍历给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。详细分析：树的深度优先遍历dfs(u)最大的好处: 在遍历过程中可以算出以u为根节点的树中结点...

Posted by Jeffzzc on March 30, 2025

保研机试训练Day-10

DFS && 哈希函数

图论DFS AcWing842. 排列数字给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。 #include<iostream> using namespace std; const int N = 10; int n; int path[N]; bool st[N]; void dfs(int u){ ...

Posted by Jeffzzc on March 29, 2025

保研机试训练Day-09

字符哈希

大纲字符哈希给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数，请你判断两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。 #include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int n,x,m=0,k; int a[N],sz,ph[N],...

Posted by Jeffzzc on March 28, 2025

保研机试训练Day-08

完整堆操作 && 哈希函数

大纲完整堆操作维护一个集合，初始时集合为空，支持如下几种操作： I x，插入一个数 x； PM，输出当前集合中的最小值； DM，删除当前集合中的最小值（数据保证此时的最小值唯一）； D k，删除第 k 个插入的数； C k x，修改第 k 个插入的数，将其变为 x；现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。 #include...

Posted by Jeffzzc on March 27, 2025

保研机试训练Day-07

Trie && 并查集 && 堆排序

大纲 Trie:高效存储和查找字符 Trie应用：在给定的 N 个整数 a1 a2 … an 中选出两个进行xor（异或）运算，得到的结果最大是多少？ #include<iostream> using namespace std; int n,m; const int N=1e5+10; const int M=31*N; int a[N]; int son[M][2];...

Posted by Jeffzzc on March 26, 2025

Zecheng's Blog