目录
1、暴力、枚举
2、日期问题
①判断闰年
②判断日期是否合理
③借助excel计算
3、数的处理
①素筛
1、简单素筛：
2、埃氏筛
②最大公约数（欧几里得）
1、单个数：
2、多个数：
③最小公倍数
1、单个数：
2、多个数：
④二分
4、dp——01背包
5、搜索
①dfs
6、C++里常用函数
①排序函数sort函数
②初始化函数memset
③数学函数
7、string
1、暴力、枚举
一般是多重循环、注意边界和出口
2、日期问题
①判断闰年
int check(int x){ if(x%400==0||(x%4==0&&x%100!=0) return 1; return 0;}②判断日期是否合理
int check(int year,int month,int day){ int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; if(year%4==0&&year%100!=0||year%400==0)//闰年判断 a[2]+=1; if(month<1||month>12)//判断月份是否出界 return 0; int t=a[month]; if(day<1||day>t) return 0; return 1;}③借助excel计算
3、数的处理
①素筛
1、简单素筛：
int prime(int n){ if(n==1) return 0; for(int i=2;i*i<n;i++) { if(n%i==0)return 0; } return 1;}2、埃氏筛
思想：从2开始，将每个质数的倍数都标记成合数
int a[MAXN];void prime(){ memset(a,1,sizeof(a); //初始化为都是素数 a[0]=a[1]=0;//0和1不是素数 for(int i=2;i<=MAXN;i++) { if(a[i]) { for(int j=i*i;j<MAXN;j=j+i) a[j]=0;//i的倍数都不是素数 } }}②最大公约数（欧几里得）
因为a / b = k(余r)所以 a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b假设d是a,b的一个公约数，则 a%d == 0, b%d == 0而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此r%d==0而r=a mod b,因此d也是b,a mod b的公约数假设d是b,a mod b的公约数,则b%d == 0,(a-k*b)%d == 0(a − k ∗ b a-k*ba−k∗b)%d = a%d-k∗ *∗b%d == 0 ,k是一个整数。进而a%d == 0.因此d也是a,b的公约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等1、单个数：
int gcd(int a,int b){ return b?gcd(b,a%b):a;}2、多个数：
int gcds(int a[],int n){ int g=a[0]; for(int i=1;i<n;i++) { g=gcd(g,a[i]); } return g;}③最小公倍数
两个数的最小公倍数等于他俩乘积除以最大公约数（a*b/gcd(a,b)）
1、单个数：
int lcm(int a,int b){ return a*b/gcd(a,b);}2、多个数：
int lcms(int a[],int n){ int l=a[0]; for(int i=1;i<n;i++) { l=lcm(a[i],l); } return l;}④二分
int i=0,j=100001;//所给范围 while(i<=j){ int mid=(i+j)/2;//二分法将mid看作边长 if(check(mid))//假如已经符合就继续往上查找 i=mid+1;//找到符合题意的最大边长 else j=mid-1;//往下查找 }4、dp——01背包
已知条件
①有N个物品，有一个背包。背包的容量是V。
②对于每个物品有:体积，价值
③每个物品只能使用一次
需要满足两个条件
①选择的这i个物品总体积不超过V
②这些物品的价值加起来最大
③对于某一个物品:使用/不使用
分析：
如果不拿就有j空间分给i-1个物品
如果拿了就只要j-c[i]的空间分给i-1个物品，c[i]的空间分给第i个物品
给i-1个物品分配j-c[i]空间和分配j空间带来的总价值是不一样的
#include<bits/stdc++.h>//万能头文件#define ll long longusing namespace std;const ll maxn=100;ll n,v,f[maxn][maxn];ll c[maxn];//每个物品占用空间ll w[maxn];//每个物品的价值int main(){ cin>>n>>v; for(ll i=1;i<=n;i++) scanf("%lld",&c[i]); for(ll i=1;i<=n;i++) scanf("%lld",&w[i]); for(ll i=1;i<=n;i++)//第i个物品 for(ll j=v;j>=0;j--)//剩余空间j { if(j >= c[i])//如果装得下 f[i][j]=max( f[i-1][j-c[i]]+w[i],f[i-1][j]); else//如果装不下 f[i][j]=f[i-1][j]; } cout<<f[n][v]<<endl;//输出答案 }5、搜索
①dfs
void dfs(int x,int y){ if(x==fx&&y==fy)//出口 { sum++;return ; } for(int i=0;i<4;i++) { int nx=x+s[i][0]; int ny=y+s[i][1]; if(nx<1||nx>n||ny<1||ny>m||mp[nx][xy]==1||vis[nx][ny]==1) continue;//边界条件以及是否有障碍或已走过 vis[nx][ny]=1;//标记走过 dfs(nx,ny);//递归 vis[nx][ny]=0//回溯 }} 6、C++里常用函数
①排序函数sort函数
sort(a,a+num)
②初始化函数memset
memset(a,0,sizeof (a));
③数学函数
1.、abs——求整数的绝对值
2、 pow——求x的次幂
3、sqrt——计算平方根
7、string
string类的常用方法_turbo夏日漱石的博客-CSDN博客