小知识
指针常量和常量指针
基础算法
排序
排序的时间复杂度
快速排序
快速排序
思想：分治
流程：
1.确定分界点：q [ l ] q[l]q[l]、q [ ( l + r ) / 2 ] q[(l+r)/2]q[(l+r)/2]、q[r] q[r]q[r]、随机点，记值为 x
2.调整区间为，分界点左边的数都 <= x，分界点右边的数都 >= x
3.递归处理左右两段
···心得：建议背一个模板
http://t.csdn.cn/hkoVU（具体的画图分析快速排序）
模板：
void quick_sort(int q[], int l, int r)
{
if (l >= r)return;
int x = q[l+r>>1], i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j)
{
swap(q[i], q[j]);
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
归并排序
归并排序
思想：分治![IMG_20230306_191601]
流程：
1.确定分界点：m i d = ( l + r )/2
2.递归排序 left, right 部分
3.归并：合二为一
void merge_sort(int q[], int l, int r)
{
int temp[N];
if (l >= r)return;//递归边界，如果长度为零直接返回
int k = 0, mid = (l + r) >> 1;//取分界点
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);//递归左半部分，右半部分进行排序
int i = l, j = mid + 1;
while (i <= mid && j <=r)//左半部分和右半部分最小值进行比较
{
if (q[i] <= q[j])temp[k++] = q[i++];
else temp[k++] = q[j++];
}
while (i <= mid)temp[k++] = q[i++];
while (j <= r)temp[k++] = q[j++];
for (int i = l, j = 0; i <=r; i++, j++)q[i] = temp[j];
}
高精度
加法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
vector<int> add(vector<int>& A, vector<int>& B)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size() ; i++)
{
if (i < A.size()) t += A[i];
if (i < B.size())t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(1);
return C;
}
int main()
{
string a, b;
vector<int> A, B;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
auto C = add(A, B);
for (int i =C.size() - 1 ; i >=0 ; i--)
{
cout << C[i];
}
}
前缀和
差分
#incude<iostream>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],b[N];//a是原数组及前缀和，b是差分数组。差分数组和原数组互为逆运算。
//在初始化时，我们可以理解为在0数组上，依次插入一个c = A[i]
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) insert(i,i,a[i]);//第一次insert求的是a的差分数组，可以写写看看。
//比如b是1，2，3，4，5，6
//那么a是1，3，6，10，15，21；
//a是b的前缀和数组，b是a的差分数组
//这里的insert求的是a的差分数组,刚开始b数组的初始化全为0，a数组的数据题目已经给出；
//例如第一次插入 b[1]=1，b[2]=0-1=-1;那么继续循环第二次插入，b[2]=-1+3=2,b[3]=0-3=-3;
//继续循环b[3]=-3+6=3。如此循环可以看出，a的差分数组慢慢求出
while(m--)//这里没什么好说的就是m个询问
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);//这里的插入才是为了解答题目
}
for(int i=1;i<=n;i++) a[i]=a[i-1]+b[i];//这里y总为了省事，直接用的差分数组存储，我修改了下。
//a[i]表示b数组前i个数的和，那么就是b数组前i-1个数的和加上第i个数。所以a[i]=a[i-1]+b[i];
//注意此时求出的前缀和数组是加上数之后的前缀和数组。最后输出a[i]
for(int i=1;i<=n;i++) printf("%d ",a[i]);
//这里提醒一点，前缀和和差分数组下标都是从1开始，为了方便。
return 0;
}
//y总模板
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=100010;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--)
{
int l, r ,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
//最后两次循环y总的模板
for(int i=1;i<=n;i++)b[i]+=b[i-1];//这里求的是b数组的前缀和，相当于a数组
for(int i=1;i<=n;i++)cout<<b[i];//经过上面一次循环，b数组已经相当于a数组了，此时只需要输出b数组即可
return 0;
}
差分矩阵
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int N=1010;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
insert(i,j,i,j,a[i][j]);
}
}
while(q--)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",a[i][j]);
}
puts(" ");
}
}
#include<iostream>
using namespace std;
const int N =1010;
int n, m, q, a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c; //整个矩阵
b[x2 + 1][y1] -= c; // x2之后(长x2+1...右端，宽y1的长方形)【高】[红色区域]
b[x1][y2+ 1] -= c; //y2之后 (长x1..右端, 宽y2 + 1..的长方形) 【短粗胖】[绿色区域]
b[x2 + 1][y2 + 1] += c; // 右下角小矩阵，从x2+1, y2+ 1往右下的矩形
// 原本O(N) 现在就4*O(1)= O(1). 不用操作矩阵里每个数，只用改这四个。
}
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
insert(i, j, i, j, a[i][j]); //同理，根据上述矩阵分析，a[i][j]+c <=> b(i,j) 的那些操作。如果矩阵塌缩为点，即在b(i,j)插入了a(i,j)的值
// 想象a(i,j) + c的运算a(i,j)设为0，c=(a(i,j))即通过insert函数b(i,j)表达了0到a(i,j)的信息转换。这次insert后b(i,j)的前缀和=a(i,j)
while(q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //bij前缀和定义 = aij;
// 即x方向(横着看)+ (i-1,j)和之前的,
// y方向(竖着看)+ (i, j - 1)和之上的。由于多加了一倍重合的(i-1, j-1)往前往上的部分，所以减回来。总运算即为(2D二维前缀和)
//对于矩阵坐标不熟的可以背一下
for (int i = 1;i <= n; i++){
for (int j = 1; j <= m; j++)
printf("%d ", b[i][j]); //以上操作过后b(i,j)变成了前缀和,即为a(i,j)
puts("");
}
}
作者：yxc
链接：https://www.acwing.com/video/244/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
二分算法
整数二分
int l=0,r=n-1;
int x;//定义分界点
cin>>x;
while(l<r)
{
int mid=l+r+1>>1;
if(q[mid]<=x)l=mid;
else r=mid-1;
}
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=x)r=mid;
else l=mid+1;
}
#include<bits/stdc++.h>
using namespace std;
#define N 100000
int q[N],m,n;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>q[i];
while(m--)
{
int x;
cin>>x;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=x)r=mid;
else l=mid+1;
}
if(q[l]!=x)cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
int l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(q[mid]<=x)l=mid;
else r=mid-1;
}
cout<<r<<endl;
}
}
}
浮点二分
双指针算法
模板
for(int i=0nj=0;i<n;i++)
{
while(j<i&&check(i,j))j++;
//每道题的题目逻辑
}
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
int res = 0;
for (int i = 0, j = 0; i < n; i ++ )
{
s[q[i]] ++ ;
while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/40066/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
所需要学的例题都在本文件夹里的双指针算法pdf中
位运算
位运算的笔记
https://www.runoob.com/w3cnote/bit-operation.html
#include<iostream>
#include <bitset>
using namespace std;
int main()
{
int n=5;
int m = -5;
cout << bitset<32>(n) << endl;
cout << bitset<32>(n >> 1) << endl;
cout << bitset<32>(n << 1) << endl;
cout << bitset<32>(m) << endl;
cout << bitset<32>(m >> 1) << endl;
cout << bitset<32>(n << 1) << endl;
}
公式一：看n的二进制表示第k'位的数
- n>>k&1;
//查看某个数的二进制表示
int main()
{
int n=10;
for(int k=3;k>=0;k--)
{
cout<<(n>>k&1);
}
return 0;
}
数据结构
单链表
头插
//head 表示头结点的下标
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针
//idx 存储当前已经用到了那个点
int head, e[N], ne[N], idx;
//初始化
void init()
{
head = -1;
idx = 0;
}//头插
void add_head(int n)
{
e[idx] = n;
ne[idx] = head;
head = idx;
idx++;
}
任意位置的后面插入
//将x插入下标是k的后面
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
删除k后面一点的位置
//删除k点后面的点
void remove(int k)
{
ne[k] = ne[ne[k]];
}
双链表
初始化
//初始化
void init()
{
//0表示左端点，1表示右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
插入
//将x插入下标是k的后面（右边）
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
}
//左边
add（l[k],x）;
删除
//删除k点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
栈和队列
#include<iostream>
using namespace std;
const int N = 10010;
//tt 栈顶下标
int stk[N], tt;
//插入一个
skt[++ tt] = x;
//弹出
tt--;
//判断栈是否为空
if (tt > 0) //不空
else //空
//栈顶
skt[tt]
**********************************
//队列
//在队尾插入元素，在队头弹出元素（先进先出）
int q[N], hh, tt=-1;//hh 队头，tt 队尾
//插入
q[++tt] = x;
//弹出
hh++;
if(hh<=tt) //不空
else//空
//取出队头元素
q[hh]
//取出队尾元素
q[tt]
模拟栈
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =100010;
int skt[N],tt;
int main()
{
int m;
cin>>m;
while(m--)
{
string op;
int x;
cin>>op;
if(op=="push")
{
cin>>x;
skt[++tt]=x;
}
else if(op=="pop")
{
tt--;
}
else if(op=="empty")
{
if(tt>0)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
else
{
cout<<skt[tt]<<endl;
}
}
}
模拟队列
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =100010;
int skt[N],tt;
int main()
{
int m;
cin>>m;
while(m--)
{
string op;
int x;
cin>>op;
if(op=="push")
{
cin>>x;
skt[++tt]=x;
}
else if(op=="pop")
{
tt--;
}
else if(op=="empty")
{
if(tt>0)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
else
{
cout<<skt[tt]<<endl;
}
}
}
单调栈
#include<iostream>
using namespace std;
const int N = 10010;
int skt[N],tt;
int n;
int main()
{
cin >> n;
while (n--)
{
int x;
cin >> x;
while (tt && skt[tt] >= x)tt--;
if (tt) cout << skt[tt] << " ";
else cout << "-1 ";
skt[++tt] = x;
}
}
单调队列（https://www.bilibili.com/video/BV1H5411j7o6?spm_id_from=333.337.search-card.all.click）//B站链接
KMP
暴力算法
朴素算法
s[N],p[M]//s是总的字符串，p是小的模板连
for (int i = 1; i <= n; i ++ )
{
bool flag = true;
for (int j = 1; j <= m; j ++ )
{
if (s[i + j - 1] != p[j])
{
flag=false;
break;
}
}
}
Tire
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
char str[N];
int son[N][26], cnt[N], idx;
/*insert()函数：对输入的字符串进行遍历，逐个字符插入到字典树中。如果当前节点没有对应的子节点，则创建一个新的节点，并更新节点计数。最后，将指针指向下一个节点。*/
void insert(char *str) // 插入字符串
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
/*query()函数：对输入的字符串进行遍历，逐个字符在字典树中查询。如果当前字符没有对应的子节点，则说明该字符串不存在于字典树中，返回0。否则，将指针指向下一个节点，直到字符串遍历完成。返回最后一个节点的计数值。*/
int query(char *str)
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
while (n -- )
{
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I')insert(str);
else printf("%d\n",query(str));
}
return 0;
}