Zecheng's Blog

New post every day (with probability 0.000000003).

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

保研机试训练Day-01

Sorting && High precision

大纲 排序算法 快排 #include<iostream> using namespace std; const int N=1e6+10; int n; int q[N]; void quick_sort(int q[],int l,int r){ if(l>=r) return; int x=q[(l+r)/2] , i = l - 1,...

Posted by Jeffzzc on March 20, 2025

FEATURED TAGS
机试训练 科研
ABOUT ME

✉️ zuozecheng@bupt.edu.cn