?基础数学

进制转换?

对于P进制的数，转换为Q进制：先将P进制转换为10进制，然后由10进制转换为Q进制。

P进制x转10进制y：

    int P,x;
    cin>>x>>P;
    int y=0,product=1;
    while(x!=0){
        y+=(x%10)*product;
        x/=10;
        product*=P;
    }

10进制y转Q进制z：（数组z中从高位到低位即为答案）

    int z[40],num=0,Q;
    cin>>Q;
    do{
        z[num++]=y%Q;
        y/=Q;
    }while(y!=0);

快速幂?

typedef long long LL;
LL binaryPow(LL a,LL b,LL m){
    if(b==0) return 1;
    if(b&1) return a*binaryPow(a,b-1,m)%m;
    else{
        LL mul=binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}

最大公约数(gcd)与最小公倍数(lcm)?

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}

关于gcd(a,b)，算法文件中有个函数__gcd(a,b)，可直接使用

int lcm(int a,int b){
    int d=gcd(a,b);
    return a/d*b;//防溢出
}

分数的运算?

初始：

struct Fraction{
    long long up,down;
}

化简：

Fraction reduction(Fraction result){
    if(result.down<0){
        result.up=-result.up;
        result.down=-result.down;
    }
    if(result.up==0){
        result.down=1;
    }else{
        int d=gcd(abs(result.up),abs(result.down));
        result.up/=d;
        result.down/=d;
    }
    return result;
}

加法：

Fraction add(Fraction f1,Fraction f2){
    Fraction result;
    result.up=f1.up*f2.down+f2.up*f1.down;
    result.down=f1.down*f2.down;
    return reduction(result);
}

减法：

Fraction minu(Fraction f1,Fraction f2){
    Fraction result;
    result.up=f1.up*f2.down-f2.up*f1.down;
    result.down=f1.down*f2.down;
    return reduction(result);
}

乘法：

Fraction multi(Fraction f1,Fraction f2){
    Fraction result;
    result.up=f1.up*f2.up;
    result.down=f1.down*f2.down;
    return reduction(result);
}

除法：

Fraction divide(Fraction f1,Fraction f2){
    Fraction result;
    result.up=f1.up*f2.down;
    result.down=f2.up*f1.down;
    return reduction(result);
}

输出：

void showFraction(Fraction f){
    f=reduction(f);
    if(f.down==1) printf("%lld",f.up);
    else if(abs(f.up)>f.down){
        printf("%d %d/%d",f.up/f.down,abs(f.up)%f.down,f.down);
    }
}

素数?

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

质因子分解?

对于int大小的数，fac数组只需要开到10.

struct factor{
    int x,cnt;//x为质因子，cnt为个数
}fac[10];

大整数运算?

初始：

struct bign{
    int d[1000];
    int len;
    bign(){
        memset(d,0,sizeof(d));
        len=0;
    }
};

字符串转bign：

bign change(char str[]){
    bign a;
    a.len=strlen(str);
    for(int i=0;i<a.len;++i){
        a.d[i]=str[a.len-i-1]-'0';
    }
    return a;
}

比较大小：

int compare(bign a,bign b){
    if(a.len>b.len) return 1;
    else if(a.len<b.len) return -1;
    for(int i=a.len-1;i>=0;--i){
        if(a.d[i]>b.d[i]) return 1;
        else if(a.d[i]<b.d[i]) return -1;
    }
    return 0;
}

加法：

bign add(bign a,bign b){
    bign c;
    int carry=0;
    for(int i=0;i<a.len||i<b.len;++i){
        int temp=a.d[i]+b.d[i]+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    if(carry!=0){
        c.d[c.len++]=carry;
    }
    return c;
}

减法：

bign sub(bign a,bign b){
    bign c;
    for(int i=0;i<a.len||i<b.len;++i){
        if(a.d[i]<b.d[i]){
            a.d[i+1]--;
            a.d[i]+=10;
        }
        c.d[c.len++]=a.d[i]-b.d[i];
    }
    while(c.len-1>=1&&c.d[c.len-1]==0){C++
        c.len--;
    }
    return c;
}

乘法：

bign multi(bign a,int b){
    bign c;
    int carry=0;
    for(int i=0;i<a.len;++i){
        int temp=a.d[i]*b+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    while(carry!=0){
        c.d[c.len++]=carry%10;
        carry/=10;
    }
    return c;
}

除法：

bign divide(bign a,int b,int&r){
    bign c;
    c.len=a.len;
    for(int i=a.len-1;i>=0;--i){
        r=r*10+a.d[i];
        if(r<b) c.d[i]=0;
        else{
            c.d[i]=r/b;
            r%=b;
        }
    }
    while(c.len-1>=1&&c.d[c.len-1]==0){
        c.len--;
    }
    return c;
}

扩展的欧几里得算法?

ax+by=gcd(a,b)

int exGcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int g=exGcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return g;
}

组合数?

long long res[67][67]={0};
long long C(long long n,long long m){
    if(m==0||m==n) return 1;
    if(res[n][m]!=0) return res[n][m];
    return res[n][m]=C(n-1,m)+C(n-1,m-1);
}

?排序

选择排序

每次选出一个最小的进行排序（基本不考）

插入排序?

每次指针向后移一位新加入一个data，对新加入的这个data前重新进行排序。（A1089和A1098有考，写代码的时候可以凑巧使用sort函数）

归并排序?

一般是二路归并排序：两两分组，排序后再次两两分组，最后只剩下一个组

const int maxn=100;
void merge(int a[],int l1,int r1,int l2,int r2){
    int i=l1,j=l2;
    int temp[maxn],index=0;
    while(i<=r1&&j<=r2){
        if(a[i]<=a[j]){
            temp[index++]=a[i++];
        }else{
            temp[index++]=a[j++];
        }
    }
    while(i<=r1) temp[index++]=a[i++];
    while(j<=r2) temp[index++]=a[j++];
    for(i=0;i<index;++i){
        a[l1+i]=temp[i];
    }
}
void mergeSort(int a[],int left,int right){
    if(left<right){
        int mid=(left+right)/2;
        mergeSort(a,left,mid);
        mergeSort(a,mid+1,right);
        merge(a,left,mid,mid+1,right);
    }
}

快速排序?

int partition(int a[],int left,int right){
    int temp=a[left];
    while(left<right){
        while(left<right&&a[right]>temp) --right;
        a[left]=a[right];
        while(left<right&&a[left]<=temp) ++left;
        a[right]=a[left];
    }
    a[left]=temp;
    return left;
}
void quickSort(int a[],int left,int right){
    if(left<right){
        int pos=partition(a,left,right);
        quickSort(a,left,pos-1);
        quickSort(a,pos+1,right);
    }
}

堆排序?

二分查找?

对一个有序数组，每次查找时，取中间的位置。

注意：这个数组的数据有可能是有重复的，具体需要注意题目的要求。

下面是二分查找的有重数组的第一个x：

int lower_bound(int a[],int left,int right,int x){
    int mid;
    while(left<right){
        mid=(right-left)/2+left;
        if(a[mid]>=x) right=mid;
        else left=mid+1;
    }
    return left;
}

?散列

普通散列法

比如名字或者一个字符串，将其中每个字母分别对应于一个数字，然后相加，成为对应的hash值。

除留余数法（Division by remainder）

hash(key)=key%mod

这个没考过。。。

线性探查法（Linear Probing）

如果对应的hash(key)已经被占用，那么就选择hash(key)+1，依次进行判断，直到第一个未被占用

平方探查法（Quadratic probing）?

当has(key)被占用时，探查hash(key)+1^2，hash(key)-1^2，hash(key)+2^2，hash(key)-2^2……

如果超出了表TSize的范围，那么就取模TSize

这个方法是个重点。

链地址法（拉链法）