Jeffzuo的博客 | Jeffzzc Blog

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

保研机试训练Day-06

单调队列 && KMP

大纲单调队列 #include<iostream> using namespace std; int n,k; const int N = 1000010; int a[N],q[N]; int hh=0,tt=-1; int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++){ ...

Posted by Jeffzzc on March 25, 2025

保研机试训练Day-05

链表 && 区间合并 && 模拟栈 && 模拟队列 && 单调栈

大纲链表首先是单链表：实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第 k 个插入的数后面的一个数；在第 k 个插入的数后插入一个数。 #include<bits/stdc++.h> using namespace std; const int N=100010; // head表示头节点下标 // e[i]表示结点...

Posted by Jeffzzc on March 24, 2025

保研机试训练Day-04

离散化 && 区间合并

大纲离散化思路：因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实有人可能会提出用哈希表，哈希表可以吗？答案也是不可以的，因为哈希表不能像离散化那样缩小数组的空间，导致我们可能需要从-e9遍历到1e9 本题使用离散化，离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。本文用于存储这个关系的数组是alls[N];特地说明下，为什么...

Posted by Jeffzzc on March 23, 2025

保研机试训练Day-03

差分 && 双指针 && 位运算

大纲差分(重点处理数列区间值改变的问题) 差分可以看成前缀和的逆运算一维差分板子 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m; int a[N],b[N]; void insert(int l,int r,int c){ b[l]+=c; b...

Posted by Jeffzzc on March 22, 2025

保研机试训练Day-02

前缀和 && 二分

大纲前缀和(重点处理数列区间和的问题) 前缀和板子 #include<bits/stdc++.h> using namespace std; const int N = 1e6+10; int a[N],s[N],n,m; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin...

Posted by Jeffzzc on March 21, 2025

Zecheng's Blog