目录

基础

基本数据类型

scanf格式符

printf格式符

最大公约数

int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

最小公倍数

//先求最大公约数d
a*b/d;  //最小公倍数=a*b/最大公约数
a/d*b;  //怕溢出就写成

素数

素数的判断

bool isprime(int n){
    if(n<=1)return false;
    for(int i=2;i*i<=n;i++){
        if(!n%i)return flase;
    }
    return true;
}

筛选法获取素数

用上面素数的判断来求素的方法，当n<10^5时是可以承受的，但如果需要求更大范围的数则可以用下面的算法：筛选法

int num[100],l=0;//num存素数
bool p[100]={0};
for(int i=2;i<100;i++){
    if(p[i]==false){
        num[l++]=i; i是素数就存起来
        for(int j=i+i;j<100;j+=i){
            p[j]=true;  //把i的倍数全部筛选掉
        }
    }
}

sscanf与sprintf

sscanf与sprintf分别可以理解为sscanf = string + scanf 与 sprintf = string + printf

string str="123abc";
char ch[50];
int a;
sscanf(str.c_str(),"%d",&a);    //sscanf是把字符串str以"%d"的格式写到a中
sprintf(ch,"%d",a);    //sprintf是把a以"%d"的格式写到ch字符数组中
//string类要使用sscanf时需要写成 str.c_str() 但用在sprintf会报错，不知道什么原因，就先使用字符数组ch存吧
str=ch;     //可以用字符数组存，然后再赋值给string

cout<<a<<" "<<ch<<endl; //打印结果为 123 123

常用math函数

fabs(double x)  //取绝对值

floor(double x) //向下取整
ceil(double x)  //向上取整
round(double x) //四舍五入

pow(double r,double p)  //返回r^p

sqrt(double x)  //算术平方根

log(double x)   //返回以e为底的对数

浮点数的比较

由于浮点数在计算机总的存储并不总是精确的,且在C/C++中的“==”操作是完全相同才能判True,所以需要引入一个极小数来对这种误差进行修正。

const double eps = 1e-8 //取误差的范围
//a等于b
#define Equ(a,b) ( ( fabs((a)-(b)) ) < eps )    //定义宏 当a、b的误差比eps小时，可以认为a=b

//a大于b
#define More(a,b) ( ( (a)-(b) ) > (eps) )   //当a-b大于eps，可以认为a>b

//a小于b
 #define Less(a,b) ( ( (a)-(b) ) < (-eps) ) //当a-b小于-eps，可以认为a<b

//a大于等于b
 #define MoreEqu(a,b) ( ( (a)-(b) ) > (-eps) ) //当a-b大于-eps，可以认为a>=b

 //a小于等于b
 #define LessEqu(a,b) ( ( (a)-(b) ) < (eps) ) //当a-b小于eps，可以认为a<=b

字符函数库 ctype.h

字符函数库中函数用于对单个字符的操作。

isalnum()   //判断字符是否为字母或数字函数
isalpha()   //判断字符是否为英文字母函数

islower()   //判断字符是否为英文小写字母函数
isupper()   //判断字符是否为英文大写字母函数
//是则返回true，否则返回false


toupper()   //将字符转换为大写字母函数
tolower()   //将字符转换为小写字母函数
//返回转换后的字符

二分查找

二分查找是基于有序序列的查找算法，该算法一开始另[left,right]为整个序列的下标区间，然后每次测试当前[left,right]的中间位置mid=(left+right)/2，判断a[mid]与欲查询的元素X的大小。
以下为实现的代码。

int binary_search(int a[],int l,int r,int num){
    int mid;
    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]==num) return mid;
        else if (a[mid]>num) r=mid-1;
        else l=mid+1;
    }
    return -1;
}

PTA刷题模板

考试的时候敲一遍，复制几份。

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin); //文件输入
    #endif  


    return 0;
}

//偷懒可以用万能头文件😄

#include<bits/stdc++.h>//万能头文件
using namespace std;
int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("1.txt","r",stdin); //文件输入 
    #endif

    return 0;
}

数据结构

STL

STL

链表

链表

树

树的知识点

图

图

考试总结

2019冬季乙级考试总结