Hey
注意数据范围是否需要开longlong每日一算法备战蓝桥杯。
1. 二分
如果这个事物具有二段性（单调性），可以使用二分更快的找到满足性质的点（优于枚举查找）。
时间复杂度： O(logn)
2024-03-05
//模板一
ll l=1,r=2e9+10;
while(l<r)
{
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
//模板二
int l=0,r=m;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid)) l=mid;//mid满足条件，答案在右区间（包含端点）
else r=mid-1;//mid不满足条件，答案在左区间（不包含端点）
}
需要计算左右端点的极值（l和r的枚举空间）
- 枚举最后一个能满足条件的，有可能左边第一个也不能满足条件，l从0开始二分。AcWing-503.借教室
- 枚举空间int为10 ^9^ 注意开longlong。AcWing-5407.管道
模板的选择可以根据check函数进行选择
- check返回true之后选择左区间用模板一
- check返回true之后选择右区间用模板二
2. 前缀和
得到某块区间的总和。
时间复杂度： O(1)
2024-03-06
//一维前缀和
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];
s[i] = s[i - 1] + w[i];
}
//二维前缀和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1];
}
判断区间是否为k的倍数，s[i]%k==s[j]%k 那么(s[j]-s[i])%k==0 AcWIng-1230.k倍空间
优化枚举二维的子矩阵：i和j枚举上下界（行），l和r使用双指针枚举左右界（列）AcWing-4405.统计子矩阵
3. 差分
快速进行区间操作
当对一个区间进行增减某个值的时候，可将差分数组对应的区间左端点的值同步变化，右端点的后一个值则相反地变化完成
时间复杂度： O(1)
2024-03-07
//一维数组操作
//m次操作，将l到r区间加c
while (m -- )
{
int l,r,c;
cin>>l>>r>>c;
b[l]+=c;
b[r+1]-=c;
}
//第i个数就会加b[i]的前缀和
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++) cout<<w[i]+b[i]<<" ";
//二维数组操作
for(int i=0;i<q;i++)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
d[x1][y1]+=c;
d[x1][y2+1]-=c;
d[x2+1][y1]-=c;
d[x2+1][y2+1]+=c;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
4. 双指针
双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算
指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
时间复杂度： O(n)
2024-03-08
//对撞指针
while (left <= right)
{
left++;
// 一些条件判断 和处理
... ...
right--;
}
//快慢指针
利用快慢指针满足有效时间范围，i-j如果超过了时间范围，j++，AcWing-1238.日志统计
5. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
时间复杂度： O(nlog n)
2024-03-10
//对于q数组，l到r区间进行排序
void merge_sort(int q[],int l,int r){
int mid=(l+r)/2;
if(l==r)return;
merge_sort(q,l,mid);merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j])tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid)tmp[k++]=q[i++];
while(j<=r)tmp[k++]=q[j++];
for(int i=0,j=l;j<=r;i++,j++){
q[j]=tmp[i];
}
}
利用分治的思想，可以在排序的过程中进行一些判断求出一些值，比如求逆序对的数量AcWing-788.逆序对的数量、小朋友排队问题AcWing-1215.小朋友排队
6. 多路归并
我们要对很多数据进行升序排序，难以将所有数据一次性读入，再使用快速、归并等排序算法对这么大规模的整数进行排序。 可以将数据分成多份，每份最小值中的最小值为当前最小。
多路归并算法的基本思想如下：1) 首先建立一个小顶堆；
2) 将每一路的最小元素（即第1列元素）都加入小顶堆中，此时堆顶就是k路中全局的最小值；
3) 将堆顶元素弹出，并将堆顶元素所在数组的下一个元素加入堆中。
4) 重复第2)和第3)步，直至每一路数据都读取结束。
时间复杂度： O(mlog n)
m次加法，n路（n个数据），n个归并排序
2024-03-12
//多路归并
void merge()
{
//pair记录值和次序
priority_queue<PII,vector<PII>,greater<PII>> heap;
//小根堆, 堆顶就是最小值
//多路归并
//n个b和n个a组合，有n路，每次分别取最小值（n个）
for(int i=0;i<n;i++) heap.push({b[i]+a[0],0});
for(int i=0;i<n;i++)
{
auto p=heap.top();
heap.pop();
c[i]=p.x;//记录最小的n种组合
//取当前路中下一个最小值
heap.push({p.x-a[p.y]+a[p.y+1],p.y+1});
}
//更新最小n种组合的值
memcpy(a,c,sizeof a);
}
有可能m会过大，归并排序的思路可以转换为二分枚举满足大于等于m个的值（具有二段性）AcWing-4656.技能升级
采用多路归并的思想求第n小的数，一个质因子是一路AcWing-1378.谦虚数字
7. 贡献法
计算每个元素对最终答案的贡献是多少，在枚举的过程中加起来。（在枚举之前通常会使用单调栈找到左右第一个比当前元素更大或更小的元素所在的位置） 这类题目的关键是想到如何在枚举的过程中计算各个元素的贡献。
一般会换个角度看问题，从结果出发
时间复杂度： O(n)
2024-03-13
//孤独的牛贡献法代码
int l[N],r[N];//左右贡献度
//算左边的贡献度
for(int i=0,sh=0,sg=0;i<n;i++)
if(s[i]=='G') l[i]=sh,sg++,sh=0;
else l[i]=sg,sh++,sg=0;
//算右边的贡献度
for(int i=n-1,sh=0,sg=0;i>=0;i--)
if(s[i]=='G') r[i]=sh,sg++,sh=0;
else r[i]=sg,sh++,sg=0;
字符串子串，子串中出现字母只出现一次才有贡献，记录左边和右边出现的位置即可用O(n)算出总共的贡献度AcWIng-2868.子串分值
8. 日期问题
2024-03-14
//定义每个月的天数，闰年二月为29天
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//判断是否为闰年
int is_leap(int year)
{
if (year % 4 == 0 && year % 100 || year % 400 == 0)
return 1;
return 0;
}
//获取当月的天数
int get_days(int y, int m)
{
if (m == 2) return 28 + is_leap(y);
return months[m];
}
//判断回文日期
bool check1(string s)
{
int len = s.size();
for(int i = 0, j = len - 1; i < j ; i++,j--) //双指针
{
if(s[i] != s[j]) return false;
}
return true;
}
//枚举日期
for (int date = 19600101; date <= 20591231; date ++ )
{
int year = date / 10000, month = date % 10000 / 100, day = date % 100;
.......
}
可以将年月日转换为8位数字进行处理
9. 区间合并
区间合并就是把多个区间有交集的部分，快速进行合并。
2024-03-15
//算出合并之后一共有几个区间
for(int i=0;i<n;i++) cin>>w[i].x>>w[i].y;
sort(w,w+n);
int l=w[0].x,r=w[0].y;
int res=1;
for(int i=1;i<n;i++)
if(r>=w[i].x) r=max(r,w[i].y);
else
{
res++;
l=w[i].x,r=w[i].y;
}
10. 递归
把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。 递归有三大要素
第一要素：明确你这个函数想要干什么
第二要素：寻找递归结束条件
第三要素：找出函数的等价关系式
2024-03-15
