memset - 对数组中每一个元素赋相同的值 - 用于初始化 / 重置
memset(数组名,值,sizeof(数组名));
一般初始化 0 或者 -1 ，因为memset使用的是按字节赋值，这样int类型的4个字节都会被赋成相同的值。
若要对数组赋为其他数字 - 使用STL中的fill函数
string.h头文件函数
strlen(字符数组);
\0前的字符个数strcmp(字符数组1,字符数组2);
<返回负整数 =返回0 >返回正整数strcpy(字符数组1,字符数组2)；
2复制给字符数组1 - 包括结束符\0strcat(字符数组1,字符数组2)
2拼接到字符数组1后sscanf & sprintf
string+ scanf / printf数组名作为函数参数，相当于指针传入，引用调用
+* (a+i) == a[i]
q-p == &a[i] - &a[j] 相差距离指针引用 - 引用别名
结构体内部可以定义自身的指针
结构体构造函数 - 初始化序列
结构体定义后直接申明的变量都是调用默认构造函数 - 跟C++构造函数一样的注意点
cin / cout 只有在string输出时才调用，一般多使用printf / scanf， 因为在输出大量数据时很容易超时
浮点数精度
const double eps = 1e-8;
const double Pi = acos(-1.0);
# define Equ(a,b) ((fabs((a)-(b)))<(eps)) // ==
# define More(a,b) (((a)-(b))>(eps)) // >
# define Less(a,b) (((a)-(b))<(-eps)) // <
# define More(a,b) (((a)-(b))>(-eps)) // >=
# define More(a,b) (((a)-(b))<(eps)) // <=
while(scanf("%d %d",&a,&b) != EOF)
while(scanf("%s",str) != EOF)
while(gets(str) != NULL)
n趟枚举选出依次最小元素void selectSort(){
for(int i = 1;i <= n; i++){ //进行n趟操作
int k = i;
for (int j =i; j <= n; j++){ //选出[i,n]中最小元素，下标为k
if(A[j] < A[k])
k = j;
}
int temp = A[i];
A[i] = A[k];
A[k] = temp;
}
}n-1趟int A[maxn], n; //n为元素个数，数组下标为1-n
void insertSort(){
for(int i = 2; i <= n; i++){ //进行n-1趟排序
int temp = A[i], j = i; //temp临时存放A[i]，j从i开始往前枚举
while(j > 1 && temp < A[j-1]){ //只要temp小于前一个元素A[j-1]
A[j] = A[j-1]; //则把A[j-1]后移一位
j--;
}
A[j] = temp;
}
}C++的sort函数即可
C中的qsort涉及许多复杂指针操作
规避了经典快排极端情况会出现O(n<sup>2</sup>)
sort(首元素地址，尾元素地址的后一个地址 [，cmp比较函数] )
#include<algorithm>
using namespace std;
sort函数会原地修改传入序列
int a[6] = {5,6,4,1,3,2}
sort(a,a+4) //将a[0]~a[3]进行排序
sort(a,a+6) //将a[0]~a[5]进行排序
STL标准容器里vector，string，deque是可用sort的，而set，map本身有序（由红黑树实现不需排序）
不填cmp参数，则默认对可比较类型进行从小到大排序
bool cmp(int a, int b){ // 实现int类型从大到小排序
return a>b; // 返回结果为True时，a在b前排序；否则b在a前排序
}
struct node {
int x,y;
}ssd[10];
bool cmp(node a, node b){ //实现对结构体的排序
return a.x > b.x // True则ab，false则ba - 一级排序
}
bool cmp(node a, node b){ // 二级排序
if(a.x != b.x) return a.x > b.x; //x不等时按x从大到小排序
else return a.y < b.y; //x相等时按y从小到大排序
}
按string字典序大小排序：使用strcmp(s1,s2) - 返回值>0或<0
直接设置一个变量记录或定义结构体时将排名项加入结构体中；
之后先排序，后修改结构体内的排名值：a[0]=1，遍历剩余元素，若分数等于上个元素分数，则排名值相同，否则等于下标+1
// strcmp(s1,s2)应用
bool cmp(student a, student b){
if(a.score != b.score) return a.score > b.score;
else return strcmp(a.name, b.name) < 0; //名字字典序小的在前
}
// 并列排名问题 1 - 需要存储
stu[0] = 1; //有序数组
for(int i = 1; i<n; i++){
if(stu[i].score == stu[i-1].score)
stu[i].rank = stu[i-1].rank;
else stu[i].rank = i + 1;
}
// 并列排名问题 2 - 直接输出
r = 1;
for(int i = 0;i < n;i++){
if(i>0 && stu[i].score != stu[i-1].score )
r = i+1;
// 输出信息 or stu[i].rank = r;
}
常见散列函数：直接定址法（恒等变换&线性变换） 平方取中法 除留余数法（mod常为素数）
哈希冲突：开放定址法（线性探查&平方探查） 拉链法
map（C++11中unordered_map）
字符串由A~Z构成 - 将其看成26进制，转换成十进制整数映射：26len-1 最大表示整数
若有A~Za~z构成 - 则将其看成52进制，处理方法与上一致
① 与上一样，化为62进制
② 若是只出现在特定位置，比如最后一位，则可以用拼接的方式：将前面的字母映射为十进制，拼接上后续数字
// A~Z
int hashFunc(char S[], int len){
int id = 0;
for(int i = 0; i < len; i++){
id = id * 26 + (S[i]-'A')
}
return id;
}
// A~Za~z
int hashFunc(char S[], int len){
int id = 0;
for(int i = 0; i < len; i++){
if(S[i]<='Z' && S[i]>='A') // Z~a之间在ascll上不是相连的
id = id * 52 + (S[i]-'A');
else if(S[i]<='z' && S[i]>='a')
id = id * 52 + (S[i]-'a') + 26;
}
return id;
}
// 假设A~Z且最后一位是数字
// A~Z
int hashFunc(char S[], int len){
int id = 0;
for(int i = 0; i < len; i++){
id = id * 26 + (S[i]-'A');
}
id = id*10 + (S[i]-'0');
return id;
}
分治 & 递归
递归式 & 递归边界
简单贪心：当前局部最优来获得全局最优 - 贪心的证明思路一般使用反证+数学归纳法，证明比想到更难，若是想到时自己暂时也无法举出反例，则一般来说是正确的
区间不相交问题：给出N个开区间，选择尽可能多的开区间，使得两两之间没有重合。 - 贪心策略：先按左端点大小排序（右端点大小），总是选择最大左端点（最小右端点）
区间最小点：给出N个开区间，选择最少的点，使得各区间都有点分布 - 与上述贪心策略相反，就是区间相交问题
贪心解决最优化问题 - 思想希望由局部最优求解全局最优 - 适用问题需具有最优子结构性（即一个问题最优解能由其子结构最优解求得） - 贪心解决问题范围有局限性
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 110;
struck Inteval {
int x,y; // 开区间左右端点
} I[maxn];
bool cmp(Inteval a, Inteval b){
if(a.x != b.x) return a.x > b.x;
else return a.y < b.y;
}
int main(){
int n;
while(scanf("%d", &n), n != 0){
for(int i = 0; i<n; i++)
scanf("%d%d",&I[i].x, &I[i].y);
sort(I, I+n ,cmp); //区间端点排序
//ans记录不相交区间个数，lastX几里路上一个被选中区间的左端点
int ans = 1, lastX = I[0].x;
for(int i =1; i<n; i++){
if(I[i].y <= lastX){ //如果该区间右端点在lastX左边，表示没有重合
lastX = I[i].x; //以I[i]作为新选中区间
ans++; //不相交区间个数+1
}
}
printf("%d\n",ans);
}
return 0;
}基于有序序列查找算法，查找第一满足条件的位置，时间复杂度O(logn)
mid = left+(right-left)/2（避免int越界），[left,mid-1]，[mid+1,right]；
临界条件：1、查找到 2、left>right
二分条件：1、循环left，相等时就是需要的值直接返回即可 2、二分初始区间为[0,n]
①：序列中是否存在满足条件的元素 ②：寻找有序序列第一个满足某条件元素位置
// 序列中是否存在满足条件的元素
int binarySearch(int A[], int left, int right, int x){
int mid; // mid为left和right中点
while(left <= right){
mid = left+ (right - left) / 2;
if(A[mid] == x) return mid;
else if(A[mid] > x)
right = mid - 1;
else left = mid + 1;
}
return -1;
}
// 寻找有序序列第一个满足某条件元素位置
int solve(int left, int right){ //左闭右闭写法
int mid;
while(left < right){ // 若左开右闭，则 left+1<right
mid = left + (right - left)/2;
if( 条件成立 ){
right = mid;
} else left = mid +1; // 若左开右闭，则 left=mid
}
return left; // 左开右闭，return right
}
① 二分法 - 罗尔定理求方程根 eg.f(x)=x2-2=0 求在[left,right]范围方程根
eg. 给N根木棒，切割希望得到至少K段长度相等的木棒，请问切割最长长度是多少。（切分长度越长，得到的段数越少 - 线性有序）
相当于问：一个有序序列中，满足k>=K的最后一个元素位置 - 满足k<K的第一个元素位置(递减序列)，利用上述模板即可解决
求幂朴素做法 O(n)：an=a * a * a..... 一共进行n次乘法
if n = 奇数：an = a * aan-1
if n = 偶数：an = an/2 * an/2
为了加快运算，奇偶判断使用位运算：if(n&1)
i位上有数，化为a2i-1
eg. a11 = a23 * a21 * a20
步骤①：n&1判断二进制末尾是否=1，ans是则乘以a
步骤②：a=a2，n>>=1，只要n大于0，则继续步骤①；结果ans返回
// 快速幂递归写法
typedef long long LL;
LL binaryPow(LL a, LL b){
if(b == 0) return 1;
if(b & 1) return a * binaryPow(a,b-1);
else{
LL mul = binaryPow(a,b/2) // 不能同时调用两个binaryPow，时间复杂度指数倍
return mul * mul;
}
}
// 快速幂迭代写法
LL binaryPow(LL a, LL b){
LL ans = 1;
while(b > 0){
if(b & 1)
ans = ans * a;
a = a* a;
b >>= 1;
}
return ans;
}原文：https://www.cnblogs.com/ymjun/p/12171132.html