算法

栈:
1.手写 #include<iostream>

using namespace std;

int n,z[233],v;

int main()
{
cin >> n >> v;
for (int a=1;a<=n;a++)
cin >> z[a];

int l=1,r=n+1;
while (l+1!=r)
{
int m=(l+r)/2;
if (v>=z[m]) l=m;
else r=m;
}
cout << l << endl;

return 0;
}
2.函数#include<cstdio>
#include<stack>

using namespace std;

stack<int> sta;

int main()
{
sta.push(233);
sta.push(2444);
sta.pop();
cout << sta.top() << endl;
cout << sta.size() << endl;

return 0;
}
队列
1.手写#include<cstdio>

using namespace std;

struct queue
{
int head=1,size=0;
int z[233];
void push(int x)
{
z[head+size] = x;
size++;
}
void pop()
{
size--;
head++;
}
int front()
{
return z[head];
}
};

int main()
{
return 0;
}
2.函数 #include<cstdio>
#include<queue>

using namespace std;

queue<int> que;

int main()
{
que.push(233);
que.push(2444);
que.pop();
cout << que.front() << endl;
cout << que.size() << endl;

return 0;
}
堆
1.优先队列:#include<cstdio>
#include<queue>

using namespace std;

priority_queue<int> heap;

int main()
{
heap.push(23);
heap.push(233);
heap.push(2333);
heap.pop();
cout << heap.top() << endl;
cout << heap.size() << endl;
}
Map:
#include<iostream>
#include<map>
#include<string>
#include<cstdio>

using namespace std;

map<int,int> m;
map<long long,int> m2;
map<string,int> m3;

map<int, map<int,int> > mm;

int main()
{
printf("%.20lf ",1.0/3);

m[2147483647] = 233;
m[-500] = 666;
m[-2147483648] = 9;
m2[23333333333333333333333ll] = 2333333333;

m3["hello world"] = 0;
mm[23][23]=23;
return 0;
}
较精确的判断两个实数是否相等:(c++中,求一个实数的值位数多了不是很精确如1.0/3)
#include<cstdio>

using namespace std;
const double eps=1e-8;

int main()
{
double a,b;
if (fabs(a-b)<=eps) printf("deng");
}
Pair
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
pair<int,int> p = make_pair(23,3);
cout << p.first << p.second << endl;
}
归并排序/分治
#include<iostream>

using namespace std;
int z[233],y[233];

void merge_sort(int l,int r)
{
if (l==r) return;
int m=(l+r)/2;
merge_sort(l,m);
merge_sort(m+1,r);

int p1=l,p2=m+1;
for (int a=l;a<=r;a++)
{
if (p1 <=m && p2<=r){
if (z[p1] < z[p2])
{y[a] = z[p1];p1++;}
else
{y[a] = z[p2];p2++;}
}
else{
if (p1<=m)
{y[a]=z[p1];p1++;}
else
{y[a]=z[p2];p2++;}
}
}
for (int a=l;a<=r;a++)
z[a]=y[a];
}

int main()
{
int n;
cin >> n;
for (int a=1;a<=n;a++)
cin >> z[a];
merge_sort(1,n);
}
前缀和
#include<iostream>

using namespace std;

int n,m;
int z[2333],s[2333];

int main()
{
cin >> n;
for (int a=1;a<=n;a++)
cin >> z[a];
for (int a=1;a<=n;a++)
s[a] = s[a-1] + z[a];
cin >> m;
for (int a=1;a<=m;a++)
{
int l,r;
cin>>l>>r;
cout << s[r] - s[l-1] << endl;
}
}
二分
1.#include<iostream>

2.using namespace std;

int n,z[233],v;

int main()
{
cin >> n >> v;
for (int a=1;a<=n;a++)
cin >> z[a];

int l=0,r=n;
while (l+1!=r)
{
int m=(l+r)/2;
if (v>z[m]) l=m;
else r=m;
}
if (z[r] == v) cout << "yes" << endl;
else cout << "no" << endl;

return 0;
}
1.a*b*c%p=(a*b%p)*c%p.
求 a^b%p.

快速幂:

st表
相当于f[i][j],表示从a[i]开始的2^j个数中的最大值,放进f[i][j].中

贪心
对于所有贪心题,只要你推导出来了n=2的时候如何判断a在前面还是b在前面的函数的时候,直接把这个函数放到sort里面,就是最优解.

上面是简化前,下面是简化后.

矩阵:
两个矩阵能做乘法的前提是一个矩阵的列数等于另一个矩阵的行数.并且 n*m的矩阵×m*k的矩阵的结果为n*k的矩阵.
加const 使得既取了地址又避免了改变数值.
矩阵乘法没有交换律