ACM——常用函数总结

常用函数总结：

一.全排列：next_permutation
二.读写优化
三.返回容器内最大最小值
四.复制函数
五.容器删除函数
六.容器填充函数
七.查找函数
八.字符串转换整数
九.欧拉筛
十.快速幂
十一.快速乘
十二.截取部分字符串函数

慢慢把常用的函数总结下来

一.全排列：next_permutation

next_permutation
包含在头文件<algorithm>中

int a[];
do
{

}
while(next_permutation(a,a+n));

例题：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
int n,a[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)a[i]=i;
    do{
        for(int i=1;i<=n;i++)printf("%5d",a[i]);
        cout<<endl;
    }while(next_permutation(a+1,a+1+n));
    return 0;
}

P1088 火星人
输入输出样例
输入
5
3
1 2 3 4 5
输出
1 2 4 5 3

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;
int n,a[maxn],m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--)//全排列m次就是题意中的第m大的数
        next_permutation(a+1,a+1+n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);//输出即可
    cout<<endl;
    return 0;
}

二.读写优化

inline int read()//快读
{
    int x=0,f=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?-x:x;
}

ios::sync_with_stdio(false);//cin加速

读出优化

inline void write(int x)
{
    char f[200];
    int cnt=0,tmp=x>0?x:-x;
    if(x<0)putchar('-');
    while(tmp>0)f[cnt++]=tmp%10+'0',tmp/=10;
    while(cnt>0)putchar(f[--cnt]);
}

推荐数据较多时使用

三.返回容器内最大最小值

1.min_element(first,last)寻找范围内最小值，返回迭代器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> v;
    vector<int> ::iterator pos;
    v.push_back(1);
    v.push_back(3);
    v.push_back(-8);
    v.push_back(8);
    pos=min_element(v.begin(),v.end());
    cout<<*pos<<endl;
    return 0;
}

输出：-8

2.max_element(first,last)寻找范围内最大值，返回迭代器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> v;
    vector<int> ::iterator pos;
    v.push_back(1);
    v.push_back(3);
    v.push_back(-8);
    v.push_back(8);
    pos=max_element(v.begin(),v.end());
    cout<<*pos<<endl;
    return 0;
}

输出：8

四.复制函数

1.copy(first,last,result)将first到last区间的元素复制到result中：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int myints[]= {10,20,30,40,50,60,70};
    vector<int> myvector;
    vector<int>::iterator it;
    myvector.resize(7);
    copy ( myints, myints+7, myvector.begin() );
    for(int i=0; i<myvector.size(); i++)
        cout<<myvector[i]<<" ";
    cout<<endl;
    return 0;
}

2.亦可用于字符串中

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    char s[24]="123456789";
    char s1[24]="";
    copy(s,s+5,s1);
    cout<<s1<<endl;
    return 0;
}

五.容器删除函数

remove(first,last,value)将区间first到last区间中值为value的元素删除

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int num[]= {1,2,3,4,5,1,0};
    int *pbegin=num;
    int *pend=num+sizeof(num)/sizeof(int);
    pend=remove(pbegin,pend,1);
    for(int *p=pbegin; p!=pend; p++)
        cout<<*p<<" ";
    cout<<endl;
    return 0;
}

六.容器填充函数

fill(first,last,value)将区间first到last区间全部初始为value

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> v(8);
    fill(v.begin(),v.end(),1);
    for(int i=0; i<v.size(); i++)
        cout<<v[i]<<" ";
    cout<<endl;
    return 0;
}

七.查找函数

find(first,last,value)查找first到last区间第一个值为value元素的位置，返回一个迭代器

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int num[]= {1,2,3,4,5};
    int *p;
    p=find(num,num+5,3);
    if(p==num+5)
        cout<<"Not found!"<<endl;
    else
        cout<<*p<<endl;
    return 0;
}

八.字符串转换整数

atoi(char);把字符串（字符char）转换成整型数的一个函数

#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int data;
    data=atoi("123");
    printf("%d\n",data);
    return 0;
}

stoi;把字符串（string）转换成整数

typedef unsigned long long ll;
ll stoi(char *ss,ll l,ll r)//自己写一个字符串转整数。想知道为什么cstring里包含的stoi()用不了
{
    ll res=0;
    if(l>r)return 0;
    for (ll i=l;i<=r;i++)
    {
        res*=10;
        res+=ss[i]-'0';
    }
    return res;
}

九.欧拉筛

void init()
{
    memset(vis,false,sizeof(vis));
    vis[1]=vis[0]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=0;j<=cnt&&i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}

十.快速幂

typedef long long ll;
//ll mod=1e15;
ll qpow(ll a,ll n)//快速幂
{
    ll re=1;//贼快
    while(n)
    {
        if(n&1)
            re=(re*a)%mod;//必须膜不然就wa
        n>>=1;//注意是有“=”号的！
        a=(a*a)%mod;
    }
    return re;
}

十一.快速乘


inline ll qmul(ll x,ll y,ll p)
{
    ll z=(long double)x/p*y;
    ll res=(unsigned long long)x*y-(unsigned long long)z*p;
    return (res+p)%p;
}

下面这种更快，接近 $O (1)$ 但是范围一大（大概爆int吧）就会WA

inline ll qmul(ll x, ll y, ll P){
    ll L=x*(y>>25)%P*(1<<25)%P;
    ll R=x*(y&((1<<25)-1))%P;
    return (L+R)%P;
}

十二.截取部分字符串函数

c++中超好用的截取部分字符串的函数substr();
头文件为#include