寒假复习之各种课程笔记(1)
2026-02-04 20:39:44
发布于：北京
现在大概有洛谷，xmw，数学三个课。
到时候集训上完了可能还有。
集训
Day1
D1学习前缀和，差分，单调栈，单调队列。
早上是前缀和与差分。
在进行这两个算法的时候，你往往要注意到一件事：
如何体现其处理优势？
有的时候，它们的用处可能仅仅是优化掉一次方N.
但有的时候，它们可能可以优化很多。
仅仅只是做区间和还不够体现它们的优势。
T1 优美子数列
链接描述
这道题的大意是让你在一段序列中找出和为k的倍数的子序列。
1.浅层运用前缀和：
首先预处理出所有子序列的前缀和。
然后枚举左右两个端点。
但不容易发现这样其实是在前缀和无效化。
那么如何更好地去运用前缀和？
2.前缀和理解加深
当需要查找最终值为定值的序列中，我们首先需要观察等式的关系：
pre[r]-pre[l-1]=-k -2k -3k -4k k 2k 3k ……
发现这里我们要查找的是k的倍数。
即%k=0的数
(pre[r]-pre[l-1])%k=0
也就是
(pre[r]%k-pre[l-1]%k)%k=0
在这种式子里，我们只需要确定两个未知数的一个即可知另一个未知数。
那么大概就能够得出如何去做了。
额注意一下负数取模。
要复习的题目：
课前小测-优美子数列
体现前缀和处理优势？
区间段和为定值：
pre[r]-pre[l-1]=x
当x被确定后
构造回文数组
模型：积木堆叠
上升：操作增加
下降：操作不变
本题本质上是一个差分，但需要再次分析一下。
在进行前缀和操作的时候，或者其他累加累乘操作的时候
要注意小心，开Longlong 会爆int
mex
统计：利用前缀和 找出e前面有多少个m e后面有多少个x
比较复杂的代码要学会分块，更加容易调试。
前缀和与差分 - 区间操作
现在开始缓慢地写题解。
T1 优美子数列
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
typedef long long ll;
ll a[N];
ll d[N],s[N],t[N];
ll c[N];
//申请到第k人时，礁石数量是否足够
bool check(int k){
//1.差分，做完前k次的区间修改
for(int i=1;i<=n;i++)c[i]=a[i]-a[i-1];
for(int i=1;i<=k;i++){
c[s[i]]-=d[i];
c[t[i]+1]+=d[i];
}
//2.前缀和，推出当前的教室剩余数量，检查是否有负数，如果有，则说明当前位置不合法
for(int i=1;i<=n;i++){
c[i]=c[i-1]+c[i];
if(c[i]<0)return 0;
}
return 1;
}
int main(){
//天数和订单数量
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>d[i]>>s[i]>>t[i];
//随着申请人的增多，教室数量不断减少，教室数量越少，就可能遇到不合法情况
int l=1,r=m;
//区间枚举订单
ll ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}else{
ans=mid;
r=mid-1;
}
}
if(ans!=0){
cout<<-1<<endl;
cout<<ans;
}else cout<<0;
return 0;
}
下午开始学单调栈和单调队列
单调栈模板：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+5;
int a[N];
int ans[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>s;//栈
for(int i=1;i<=n;i++){
//入站原则：保持递减
//维护单调递减栈，表示暂未找到答案的栈
while(!s.empty()&&a[s.top()]<a[i]){
ans[s.top()]=i;
s.pop();
}
s.push(i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
需要保证栈是否为空再去判断。否则会发生奇怪的问题
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N];
int main(){
deque<int>q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
//对首元素不在窗口范围，及时出对
if(!q.empty()&&q.front()<i-m+1)q.pop_front();
//入队之前，先检查单调性是否能维持
while(!q.empty()&&a[q.back()]>=a[i]){//严格递增
q.pop_back();
}
q.push_back(i);
if(i>=m)cout<<a[q.front()]<<" ";
}
return 0;
}
动物园的等待
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct Node{
int h;//高度，个数
ll c;
};
int a[N];
ll ans;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<Node>s;
for(int i=1;i<=n;i++){
//元素依次入栈
//1.a[i]大于栈顶,把栈中比a[i]低的一个个推掉，统计ans++;
Node cur={a[i],1};
while(!s.empty()&&a[i]>s.top().h){
ans+=s.top().c;
s.pop();
}
//2.a[i]递减，正常入栈,ans++(两两相邻）
//3.a[i]等于栈顶，统计跟a[i]一样高的元素个数有几个
//如果存在a[i]前面第一个比它高的，如果存在ans++;
//栈是否为空
if(!s.empty()){
if(s.top().h==a[i]){
ans+=s.top().c;
cur.c=s.top().c+1;
s.pop();
if(!s.empty())ans++;
}else{
//相邻元素递减，只能看到彼此
ans++;
}
}
s.push(cur);
}
cout<<ans;
return 0;
}
链表？
下一个更大的元素：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int ans[N];
int main(){
memset(ans,-1,sizeof ans);
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>s1,temp,s2;
//s1还未找到第一大的元素
//s2已经找到第一大的元素
for(int i=1;i<=n;i++){
//1.用a[i]和s2比较，尝试更新s2中的元素
while(!s2.empty()&&a[s2.top()]<a[i]){
ans[s2.top()]=a[i];
s2.pop();
}
//cout<<i<<" ";
//2.用a[i]和s1比较，把找到第一大数字的元素，丢到s2
//需要先把s1弹出的元素->temp->s2
while(!s1.empty()&&a[s1.top()]<a[i]){
temp.push(s1.top());
s1.pop();
}
while(!temp.empty()){
s2.push(temp.top());
temp.pop();
}
s1.push(i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
写单调栈和单调队列的时候要注意判断栈和队列是否为空。
在写单调栈和单调队列的时候要注意判断栈和队列是否为空。
构造回文数组
前缀和不开long long 见祖宗的嗷！
前缀和：pre[r]-pre[l-1]
差分：pre[l]+x pre[r+1]-x
D2 早上开模拟赛
下午摸题解。
想要找到第n大的质数。
欧拉筛：O(n) 每一个和数 都只会被自己的最小质因数标记。
埃氏筛：O(n log lon n)
T2：可以使用暴力，也可以使用优先队列。
我觉得，做错的原因主要是我当时思路不太清晰。
做一道题，应该先想清楚思路在开始吧。
等一下。
我去找老师对了一下思路。理论上而言，我的思路应该是正确的。
不过正确了也T。
我觉得这题我没做出来的主要原因是我以前的东西忘得有点太多了。
啥都不记得了。
在想优化的时候大脑空空。
啥都不知道。
反正最后结果就是我养了优先队列。
然后我去看看欧拉筛是怎么写的。
用分块来写代码后，可以写一个快，检查一下
在做难题或者复杂的题目的时候，要先自己做一些小的样例。
然后慢慢总结规律。
摸个T4吧。
好可惜啊。
T4要是考场上再想想可能就写出来了。
但我去刷小红书了喵。（逃跑
但是没关系，让我们来美美地写一个题解吧遗憾弥补一下吧！
这道题，它主要是想问在一颗树上，如何加才能使整体数值加到它期望的样子。
我觉得此题的难点有两个：
1.它的范围不太好判断。如果初读的话，你可能会有点懵。
（不过这个也是题目的必须点，亦是突破点）
2.它的思路有点难想（虽然其实很简单，但是如果你正常做的话，你可能会觉得自己遇到了一堆难点）
就这两个，平均下来应该是绿题里面比较简单的题目吧。
然后说说具体是怎么做的吧。
想动态规划一样，有两种遍历方法：
1.自顶向下
2.自底向上
这个提出的好像有点早了，到时候再说好了。
可以从一条链开始推。
然后你就会发现一个核心点：
从最下方开始，并且最好是取每个点的最大值（这个稍微推一推就出来了）
然后就没有了。
欧拉筛：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
bool isprime[N];
int p[N];
int main(){
int n;
cin>>n;
int now=0;
for(int i=2;i<=n;i++){
if(!isprime[i])p[++now]=i;
for(int j=1;j<=now;j++){
if(i*p[j]>n)break;
isprime[i*p[j]]=1;
if(i%p[j]==0)break;//判断语句应当放在标记之后
}
}
//欧拉筛：要求 每一个合数都只会被自己的最小质因数所标记
//比如说：30只会被2所标记而不会被3所标记
//也就是说，在遍历到10的时候，是不会标记30的
//只有遍历到15，才会标记30.
//因为遍历到10的时候，10%2==0.这也就代表：后续的数不一定是被自己的最小质因数标记/。
cout<<now;
return 0;
}
然后接下来去做点好玩的 咪。
1.优先队列
神奇的优先队列介绍！
优先队列分为两种：1.小根堆 2.大根堆
再要细分的话，还有结构体优先队列 和 数字优先队列。
看看：
1.数字大根堆（默认，大的数字在前）：
priority_queue<int>pq;
2.数字小根堆
priority_queue<int,vector<int>,greater<int> >pq;
结构体大/小根堆：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y;
friend bool operator < (Node a,Node b){
return x>y;//注意这个适合sort的cmp刚好相反的
}
};
priority_queue<Node>pq;
int main(){
return 0;
}
好的，那么现在理论成立，实践开始。
优先队列的运用主要有两个（为我所知的）：
1.优化
2.反悔贪心
这里主要介绍一下优先队列用来优化。
关于如何优化，让我们用一道题目见识一下。
舞蹈演出
这道题的题意非常清晰，在此就不过多赘述了。
暴力如何打应该已经知晓：
每次二分k的最小值，设置出k个值为t的变量，然后每次找值最小的一个减一个。
如果说，想要找最小的值且用暴力的话，一次就是O(n)界别。
而1e4的n没办法支撑O(n^2logn)的时间复杂度。
只能支撑O(nlogn)或者O(n)又或是O(nloglogn)
也就是，要优化一个log。
而且是要找动态最小值。
哦豁，答案呼之欲出！
优先队列是也。喵。
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
priority_queue<int,vector<int>,greater<int> > pq;//原是大根堆，用重载运算符变成小根堆。
int n,t;
int a[N];
int ans;
bool check(int x){
for(int i=1;i<=x;i++)pq.push(a[i]);
for(int i=x+1;i<=n;i++){
int now=pq.top();
pq.pop();
now+=a[i];
pq.push(now);
}
bool can=1;
while(!pq.empty()){
int now=pq.top();
pq.pop();
if(now>t)can=0;
}
return can;
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++)cin>>a[i];
int l=1,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
关于神奇的链表！
通常，我们不是用STL里面的链表（太难用了喵），而是自己通过结构体来模拟。
现在我们一起来做一道模板题目。
模板双向链表
这道题目钟一共要求了三个关于链表的更改操作。
1.将x插入到y的左侧
2.将x插入到y的右侧
3.删除x这个节点
我们来分析一下这三个操作：
将A插入到B的左/右侧
它本质是两个操作：
1.删除
2.插入
如果A原本存在于这个数组之中，那么将其删除。
先来看看如何实现删除这个操作：
删除一个元素，意味着这个元素的左边的右边要变成它的右边。
这个元素的右边的左边要变成它的左边。
这个就是删除操作：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
bool if1[N];
struct Node{
int s,z,y;//数值，左边是谁，右边是谁
}node[N];
void shan(int x){
node[node[x].z].y=node[x].y;
node[node[x].y].z=node[x].z;
if1[x]=1;
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)node[i].s=i;
for(int i=1;i<=m;i++){
int c;//
cin>>c;
if(c==1){
}else if(c==2){
}else if(c==3){
int x;
cin>>x;
shan(x);
}
}
return 0;
}
然后思考一下插入操作怎么整。
将A插入到B的左边，也就意味着：
B左边的右边变成A，B的左边变成A的左边，A的右边变成B，B的左边变成A
也就是这样：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
bool if1[N];
struct Node{
int s,z,y;//数值，左边是谁，右边是谁
}node[N];
void shan(int x){
node[node[x].z].y=node[x].y;
node[node[x].y].z=node[x].z;
if1[x]=1;
return;
}
void cha(int x,int y){
//将x插入到y的左侧
node[node[y].z].y=x;
node[x].z=node[y].z;
node[x].y=y;
node[y].z=x;
return;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)node[i].s=i;
for(int i=1;i<=m;i++){
int c;//
cin>>c;
if(c==1){
int xx,yy;
cin>>xx>>yy;
//将xx插入到yy的左侧
//1.先删除xx
shan(xx);
//2.然后插入
cha(xx,yy);
}else if(c==2){
int xx,yy;
cin>>xx>>yy;
shan(xx);
cha(yy,xx);
}else if(c==3){
int xx;
cin>>xx;
shan(xx);
}
}
return 0;
}
最后输出一下就好了：
枚举：
枚举什么？
1.确定枚举范围
2.如何是枚举不重不漏
要把一个大问题分解成若干个小模块去解决
T4：绝对值即距离
对于距离，考虑相对位置的情况。
1.重叠，包含
2.b在a 前面
3.a在b前
重点在于维护：amin bmin amax bmax
归并排序：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
void p(int l,int m,int r){
int i=l,j=m+1,t=0;
while(i<=m&&j<=r){
if(a[i]>a[j])b[t++]=a[j++];
else b[t++]=a[i++];
}
while(i<=m)b[t++]=a[i++];
while(j<=r)b[t++]=a[j++];
for(int i=0;i<t;i++)a[i+l]=b[i];
}
void c(int x,int y){
if(x<y){
int mid=(x+y)>>1;
c(x,mid);
c(mid+1,y);
p(x,mid,y);
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
c(1,n);
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
}
分治是很重要的思想：分而治之。
这是所有庞大规模问题的基础。
下午上倍增和ST表
关于倍增：
RMQ问题：区间最值问题
额主要讲一讲如何使用吧。
一句话概括：倍增是思想，ST表是框架。
ST表的模板虽然是取区间最值，但是这并不代表它只能用来取区间最值。
相反，它的运用面是很广泛的。
拿一道题目来举例吧。
利用ST表的框架。
先考虑大致思路框架：
每走一步，需要想的是：走到了哪里->拿了几个胡萝卜
而我们已知的是：我们走了几步
如果一次一次推的话，时间复杂度大概是O(m)
太高了。
如何优化？
下午讲了选讲内容：
离散化
这里空空如也
有帮助，赞一个