感谢名单

Z_LOVE_OI ， 精神小伙！

进制输出

oct 是八进制输出，

cout<<oct<<a<<endl;

dec 是十进制（效果和默认一样），

cout<<dec<<a<<endl;

hex 是十六进制输出（字母默认是小写字母）。

cout<<hex<<a<<endl;

快读快写

$ int $

#define gc getchar()
inline int read(){
	int x=0; bool sgn=0; char s=gc;
	while(!isdigit(s))sgn|=s=='-',s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
	return sgn?-x:x;
}

inline void write_n(int X){
    if(X<0) putchar('-'),X=~(X-1);
    int s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    puts("");
}

$ long $ $ long $

inline ll read_n(){
    ll X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

inline void write_n(ll X){
    if(X<0) putchar('-'),X=~(X-1);
    ll s[20],top=0;
    while(X) s[++top]=X%10,X/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    puts("");
}

$ string $

inline string read_s(){
    char c;
    string res;
    while((c=getchar())!=' ') res.push_back(c);
    return res;
}

inline void write_s(string s){
    for(string::iterator it=s.begin(),l=s.end(); it!=l; it++){
        putchar(*it);
    }
    putchar('\n');
}

求最大公因数和最小公倍数

#include<bits/stdc++.h>
using namespace std;
int gcd1(int a,int b){ //辗转相除递归解法 
if(b==0)  return a;
return gcd1(b,a%b); 
} 
int gcd2(int a,int b){ //辗转相除法求解 
while(b!=0){
    int r=a%b;
    a=b;
    b=r;
}
return a;
} 
int lcm(int a,int b){ //最小公倍数 
return a*b/gcd1(a,b);
}

$ gcd $ 核心代码

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

高精度加法

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
string s1,s2;
int a[500],b[500],c[500];
int main()
{
    cin>>s1>>s2;
    a[0]=s1.size();
    for(int i=1;i<=a[0];++i)
        a[i]=s1[a[0]-i]-'0';
    b[0]=s2.size();
    for(int i=1;i<=b[0];++i)
        b[i]=s2[b[0]-i]-'0'; 
	int n=max(a[0],b[0]);
	for(int i=1;i<=n;++i)
	    c[i]=a[i]+b[i];
	for(int i=1;i<=n;++i)
	{
		if(c[i]>=10)
		{
			c[i]%=10;
			++c[i+1];
		}
	}
	if(c[n+1]>0) n++;
	//while(c[n]==0) n--;
	for(int i=n;i>0;--i)
	    cout<<c[i];
	cout<<endl;
	return 0;
}

高精度减法

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
string s1,s2,s3;
int a[50000],b[50000];
int main()
{
    cin>>s1>>s2;
    if(s1.size()<s2.size()||s1.size()==s2.size()&&s1<s2)
    {
    	s3=s1;
    	s1=s2;
    	s2=s3;
    	cout<<"-";
	}
    a[0]=s1.size();b[0]=s2.size();
    for(int i=1;i<=a[0];++i)
        a[i]=s1[a[0]-i]-'0';
    for(int i=1;i<=b[0];++i)
        b[i]=s2[b[0]-i]-'0';
	int n=max(a[0],b[0]);
	for(int i=1;i<=n;++i)
	{
		if(a[i]<b[i])
		{
		    --a[i+1];
			a[i]+=10;
		}
		a[i]=a[i]-b[i];
	}
	while(a[n]==0&&n>1) n--;
	for(int i=n;i>0;--i)
	    cout<<a[i];
	cout<<endl;
	return 0;
}

质数判断

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int num)
{ //质数判断 
    if(num<2)  return false;
    for(int i=2;i<=sqrt(num);i++)
        if(num%i==0)  return false;
    return true;
} 

埃氏筛

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e9;
bool isPrime[MAX]; 
void eraSieve(int MAX){ //埃式筛 
//计算MAX范围内所有的质数 
memset(isPrime,true,sizeof(isPrime)); 
isPrime[0]=isPrime[1]=false;
for(int i=2;i<=MAX;i++){
    if(isPrime[i]){
        for(int j=2;j*i<=MAX;j++){
            isPrime[j*i]=false;
        }
    }
} 
}

欧拉筛

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e7;
bool isPrime[MAX];
int prime[MAX]; 
void EulerSieve(int MAX){ //欧拉筛 
memset(isPrime,true,sizeof(isPrime)); 
isPrime[0]=isPrime[1]=false;
int cnt=0; //质数个数 
for(int i=2;i<=MAX;i++){
    if(isPrime[i]){
        prime[cnt++]=i;
    }
    for(int j=0;j<cnt&&prime[j]*i<=MAX;j++){
        isPrime[prime[j]*i]=false;
        if(i%prime[j]==0)  break;
    }
} 
}

线性筛

#include<bits/stdc++.h>
using namespace std;
int v[100000010];
int n,cnt=0;
int p[6000010];
void getss(int n)//线性筛
{
	for(int i=2;i<=n;++i)
	{
		if(v[i]==0)
		{
			v[i]=i;
			p[++cnt]=i;
		}
		for(int j=1;j<=cnt;++j)
	        {
				if(p[j]>n/i||p[j]>v[i])break;
				v[i*p[j]]=p[j];
			}
	}
	
}

判断回文

#include<bits/stdc++.h>
using namespace std;
char st[101];
int main()
{
	cin>>st;
	int len=strlen(st)-1,i=0;
	int j=len;
	while(i<=j)
	{
		if(st[i]!=st[j])
		{
			cout<<"no"<<endl;
			return 0;
		}
		    i++;
		    j--;	
	}//是回文就输出yes，否则输出no
	cout<<"yes"<<endl;
	return 0;
}

前缀和

一维

for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		s[i]=s[i-1]+a[i];
	}    
	int L,N;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&L,&N);
		printf("%d\n",s[N]-s[L-1]);
	}

二维

void gouzao(int x,int y)
{
    s[x][y]=s[x-1][y]+s[x][y-1]-s[x-1][y-1]+a[x][y];
}
int qiuhe(int x1,int y1,int x2,int y2)
{
    return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}

差分

一维

void chafen(int l,int r,int k)
{
    ca[l]+=k;
    ca[r+1]-=k;
}

二维

void chafen(int x1,int y1,int x2,int y2,int k)
{
    ca[x1][y1]+=k;
    ca[x1][y2+1]-=k;
    ca[x2+1][y1]-=k;
    ca[x2+1][y2+1]+=k;
}

迪杰斯特拉模板

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int W[51][51];
int d[51];
int pre[51];
bool b[51];
int n,m;
void print(int i)
{
	if(pre[i]) print(pre[i]);
	printf("%d",i);
}
int main()
{
	int i,j,k,w,minn,oo=0x3f3f3f3f,s=1;
	cin>>n>>m;
	memset(W,127/3,sizeof(W));
	for(k=1;k<=m;++k)
	{
	    cin>>i>>j>>w;
	    W[i][j]=W[j][i]=w;
	}
	for(i=1;i<=n;++i)
	{
		d[i]=oo;
		pre[i]=0;
	}
	for(i=1;i<=n;++i)
	{
		minn=oo,k=0;
		for(j=1;i<=n;++j)
		if(!b[j]&&d[j]<minn)
		{
			minn=d[j];
			k=i;
		}
		b[k]=true;
		for(j=1;j<=n;++j)
		if(d[k]+W[k][j]<d[j])
		{
			d[j]=d[k]+W[k][j];
			pre[j]=k;
		}
	}
	print(n);
	return 0;
}

弗洛伊德模板

#include<iostream>
using namespace std; 
void Floyd(){ //Floyd核心代码 
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
  for(int j=1; j<=n; j++)
    if(e[i][j]>e[i][k]+e[k][j])
      e[i][j]=e[i][k]+e[k][j];
}

全排列问题

#include<iostream>
#include<iomanip>
#include<cstdio>
using namespace std;
int num=0,a[10005]={0},n,r;
bool b[10005]={0};
int print()
{
	num++;
	for(int i=1;i<=r;++i)
	    cout<<setw(3)<<a[i];
	cout<<endl;
}
int search(int k)
{
	int i;
	for(int i=1;i<=n;++i)
	    if(!b[i])
	    {
	    	a[k]=i;
	    	b[i]=1;
	    	if(k==r) print();
	    	else     search(k+1);
	    	b[i]=0;
	    }
}
int main()
{
	cout<<"input n,r:";
	cin>>n>>r;
	search(1);
	cout<<"number="<<num<<endl;
} 

走迷宫

#include<cstdio>
#include<iostream>
using namespace std;
char Map[9][9];//地图 
int n,m;//迷宫行列数 
int startx,starty;//入口坐标 
int endx,endy;//出口坐标 
int pathx[81],pathy[81];//保存路径 
bool visit[9][9];//走过标记 
int dx[4]={-1,0,1,0},//x坐标增量 
    dy[4]={0,1,0,-1};//y坐标增量
void print(int step)
{
	for(int i=1;i<=step;++i)
	    printf("%d,%d ",pathx[i],pathy[i]);
	printf("\n");
}
void dfs(int x,int y,int step)
{
	printf("%d,%d step=%d\n",x,y,step);
	pathx[step]=x;
	pathy[step]=y;//保存路径 
	visit[x][y]=true;//保存走过 
	if(x==endx&&y==endy)
	    print(step);//输出路径 
	for(int i=1;i<=4;++i)
	{
		int tx=x+dx[i];
	    int ty=y+dy[i];	
	    if(tx>=1&&tx<=n&&ty>=1&&ty<=m
		&&Map[tx][ty]=='.'&&!visit[tx][ty])
		{
			dfs(tx,ty,step+1);//搜索下一步 
			visit[tx][ty]=false;//回溯一步
		}
	}
}
int main()
{
	cin>>n>>m;
	cin>>startx>>starty>>endx>>endy;
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=m;++j)   
	        cin>>Map[i][j];
	dfs(startx,starty,1);
	return 0;
}