问题标题: 模板(会更新）

1.质数判断

bool f(int n){
	if(n==1){
		return 0; 
	}
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

2.最大公约数

while(a%b!=0){
	r=a%b;
	a=b;
	b=r;
}
cout<<b;

3.最小公倍数

//dsf(x,y)表示为求x和y的最大公约数的函数
cout<<a*b/dsf(x,y)

4..最大公约数(递归写法)

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

5二进制转十进制

 cin>>x;
    while(x){
    	a+=x%10*cnt;
    	cnt*=2;
    	x/=10;
	}
	cout<<a;

6.k进制转十进制(1<=k<=16)

int f(string x){
	int cnt=1,ans=0;
	for(int i=x.size()-1;i>=0;i--){
		if(x[i]>='0'&&x[i]<='9'){
			ans+=(x[i]-'0')*cnt;
		}else{
			ans+=(x[i]-'A'+10)*cnt;
		}
		cnt*=k;
	}
	return ans;
} 

7.十进制转二进制

string f(int x){
	string ans="";
	while(x){
		ans=(char)(x%2+'0')+ans;
		x/=2;
	}
	return ans;
}

8.十进制数转化为k进制(1<=k<=16)

string f(int x){
	string ans="";
	while(x){
		ans=(char)(x%2+'0')+ans;
		x/=2;
	}
	return ans;
}

9.二分(第一座表)

for(int i=1,x;i<=m;i++){
		cin>>x;
		int l=1,r=n;
		while(l<r){
			int mid=l+r>>1;
			if(a[mid]<x){
				l=mid+1;
			}else{
				r=mid;
			}
		}
	}

9.二分(最后坐标)

for(int i=1,x;i<=m;i++){
		cin>>x;
		int l=1,r=n;
		while(l<r){
			int mid=l+r+1>>1;
			if(a[mid]>x){
				r=mid-1;
			}else{
				l=mid;
			}
		}
	}

余思淼在2025-05-17 19:51:41追加了内容

第8条搞错了，是

string f(int x){
	string ans="";
	while(x){
		if(x%k<10){
			ans=(char)(x%k+'0')+ans;
		}else{
			ans=(char)(x%k-10+'A')+ans;
		}
		x/=k;
	}
	return ans;
}

 

余思淼在2025-05-18 09:47:06追加了内容

10.判断回文字符串(指针)

bool f(string s){
	int l=0,r=s.size()-1;
	while(l<r){
		if(s[l]!=s[r]){
			return 0;
		}
		l++;
		r--;
	}
	return true;
}

11.判断回文数字

bool hw(int x){
	int y=0,a=x;
	while(x){
		y=y*10+x%10;
		x/=10;
	}
	return y==a;
}

12.去重排序

for(int i=1;i<=(题目中a[i]最大值);i++){
		if(b[i]!=0){
			cout<<i<<" ";
		}
	}

13. 不去重排序

for(int i=1;i<=1000;i++){//遍历桶数组(排序) 
		//i是数值 b[i]是i出现的次数 
		for(int j=1;j<=b[i];j++){//i输出b[i]次 
			cout<<i<<' '; 
		}
	}

14.去重不排序

for(int i=1;i<=n;i++){//遍历原数组 去重不排序 
		if(b[a[i]]==0){//当前元素a[i]  a[i]没有统计过 
			cout<<a[i]<<' ';
		}
		b[a[i]]++;
	}

15.冒泡排序

for(int i=1;i<=n-1;i++){
		for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
			}
		}
	}

16.汉诺塔移动过程

//把前n层汉诺塔从st杆移动到ed杆，借助fz杆  a=st    b=ed   c=fz
void h(int n,char st,char ed,char fz){
    //边界
    if(n==0){
        return ;
    }
    //1.把前n-1层汉诺塔从st杆移动到fz杆,借助ed
    h(n-1,st,fz,ed);
    //2.把第n个盘从st杆移动到ed杆
    cout<<st<<"->"<<n<<"->"<<ed<<endl;
    //3.把前n-1层汉诺塔从fz杆移动到ed杆,借助st
    h(n-1,fz,ed,st);
}

17.汉诺塔移动次数

int h(int n){
    if(n==0){
        return 0;
    }
    return h(n-1)*2+1;
}
//可能用long long,看题目

18.（必经中间柱）汉诺塔移动次数

int h(int n){
    //把n层汉诺塔经过中间从左(右)边移动到右(左)边
    if(n==0)return 0;
    return h(n-1)*3+2;
}

19.高精度加法

string pu(string s1,string s2){
    a[0]=s1.size();
    b[0]=s2.size();
    c[0]=max(a[0],b[0]);
    int jw=0;
    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';
    }
    for(int i=1;i<=c[0];i++){
        c[i]=a[i]+b[i]+jw;
        jw=c[i]/10;
        c[i]%=10;
    }
    if(jw) c[++c[0]]++;
    string ans="";
    for(int i=1;i<=c[0];i++){
        ans=(char)(c[i]+'0')+ans;
    }
    return ans;
}

20.高精度减法 

string MU(string x,string y){
    memset(a,0,sizeof(a));
    memset(a,0,sizeof(b));
    memset(a,0,sizeof(c));
    a[0]=x.size();
    b[0]=y.size();
    for(int i=1;i<=a[0];i++){
        a[i]=x[x.size()-i]-'0';
    }
    for(int i=1;i<=b[0];i++){
        b[i]=y[y.size()-i]-'0';
    }
    c[0]=max(a[0],b[0]);
    for(int i=1;i<=c[0];i++){
        if(a[i]<b[i]){
            c[i]=a[i]+10-b[i];
            a[i+1]--;
        }else{
            c[i]=a[i]-b[i];
        }
    }
    while(c[0]>1&&c[c[0]]==0){
        c[0]--;
    }
    string ans="";
    for(int i=c[0];i>=1;i--){
        ans+=char(c[i]+'0');
    }
    return ans;
}

21. 高精度乘法

string cf(string s1,string s2){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    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';
    }
    c[0]=a[0]+b[0];
    for(int i=1;i<=a[0];i++){
        for(int j=1;j<=b[0];j++){
            c[i+j-1]+=a[i]*b[j];
        }
    }
    int jw=0;
    for(int i=1;i<=c[0];i++){
        c[i]+=jw;
        jw=c[i]/10;
        c[i]%=10;
    }
    while(c[c[0]]==0&&c[0]>1){
        c[0]--;
    }
    string ans="";
    for(int i=1;i<=c[0];i++){
        ans=char(c[i]+'0')+ans;
    }
    return ans;
}

## 20、21、18 都有三个数组 a[位数] b[位数] c[位数]

 

余思淼在2025-05-18 09:52:15追加了内容

22.埃氏筛

for(int i=2;i<=sqrt(n);i++){
        if(p[i]==0){
            for(int j=i*i;j<=n;j+=i){
                p[j]=1;
            }
        }
    }
//p[j]为0是质数

余思淼在2025-05-20 13:08:25追加了内容

Dijkstra

 

for(int k=1;k<=n;k++){

 

for(int i=1;i<=n;i++){

 

for(int j=1;j<=n;j++){

 

f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

 

}

 

}

 

}

Floyd

 

while(true){

 

int pos=-1;

 

for(int i=1;i<=n;i++){

 

if(!vis[i]&&(pos==-1||f[i]<f[pos])){

 

pos=i;

 

}

 

}

 

if(pos==-1) break;

 

vis[pos]=true;

 

mst+=f[pos];

 

for(int i=0;i<a[pos].size();i++){

 

int t1=a[pos][i].to;

 

int t2=a[pos][i].w;

 

f[t1]=min(f[t1],t2);

 

}

 

}

Prim

 

for(int i=1;i<=n;i++){

 

if(inged[i]==0){

 

q.push(i);

 

f[i]=t[i];

 

}

 

}

 

while(!q.empty()){

 

int h=q.front();

 

q.pop();

 

for(int i=0;i<a[h].size();i++){

 

int to=a[h][i];

 

inged[to]--;

 

f[to]=max(f[to],f[h]+t[to]);

 

if(inged[to]==0){

 

q.push(to);

 

}

 

}

 

}

拓扑排序

 

for(int i=1;i<=n;i++){

 

for(int j=a;j>=v[i];j--){

 

f[j]=max(f[j],f[j-v[i]]+w[i]);

 

}

 

}

01

 

for(int i=1;i<=n;i++){

 

for(int j=v[i];j<=a;j++){

 

f[j]=max(f[j],f[j-v[i]]+w[i]);

 

}

 

}

完全

 

for(int i=1;i<=n;i++){

 

for(int j=0;j<=m;j++){

 

for(int t=0;t<=c[i]&&v[i]*t<=j;t++){

 

f[i][j]=max(f[i][j],f[i-1][j-v[i]*t]+w[i]*t);

 

}

 

}

 

}

多重

 

for(int i=1;i<=pos;i++){

 

for(int j=a[i];j<=200;j++){

 

f[j]=f[j]+f[j-a[i]];

 

}

 

}

恰填方案数

 

for(int i=1;i<=n;i++){

 

for(int j=m;j>=v[i];j--){

 

f[j]=min(f[j],f[j-v[i]]+1);

 

}

 

}

填满最小物品数

 

for(int i=1;i<=mx;i++){

 

for(int j=m;j>=0;j--){

 

for(int t=0;t<=len[i];t++){

 

if(j>=v[i][t]) f[j]=max(f[j],f[j-v[i][t]]+w[i][t]);

 

}

 

}

 

}

分组1

 

for(int i=1;i<=k;i++){

 

for(int t=1;t<=len[i];t++){

 

for(int j=m;j>=v[i][t];j--){

 

if(f[i-1][j-v[i][t]]!=-1) f[i][j]=max(f[i][j],f[i-1][j-v[i][t]]+w[i][t]);

 

if(f[i][j-v[i][t]]!=-1) f[i][j]=max(f[i][j],f[i][j-v[i][t]]+w[i][t]);

 

}

 

}

 

}

分组2

 

for(int i=1;i<=m;i++){

 

for(int j=0;j<=n;j++){

 

f[i][j]=f[i-1][j];

 

if(j>=v[i][0]) f[i][j]=max(f[i][j],f[i-1][j-v[i][0]]+w[i][0]);

 

if(j>=v[i][0]+v[i][1]) f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]]+w[i][0]+w[i][1]);

 

if(j>=v[i][0]+v[i][2]) f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][2]]+w[i][0]+w[i][2]);

 

if(j>=v[i][0]+v[i][1]+v[i][2]) f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+w[i][0]+w[i][1]+w[i][2]);

 

}

 

}

依赖

 

for(int i=1;i<=n;i++){

 

for(int j=_;j>=v[i];j--){

 

for(int k=__;k>=v2[i];k--){

 

f[j][k]=max(f[j][k],f[j-v[i]][k-v2[i]]+w[i]);

 

}

 

}

 

}

二维费用

 

for(int l=1;l<n;l++){

 

for(int i=1;i<=n;i++){

 

int j=i+l;

 

if(j>n){

 

break;

 

}

 

for(int k=i;k<j;k++){

 

f[i][j] = min(f[i][j] , f[i][k] + f[k+1][j] + sum[j]-sum[i-1]);

 

}

 

}

 

}

余思淼在2025-05-30 21:41:17追加了内容

迷宫(上下左右移动、方案数、从{sx,sy}到{fx,fy}）

void dfs(int x,int y){
    if(x==fx&&y==fy){
        cnt++;
        return ;
    }
    vis[x][y]=1;
    for(int i=1;i<=4;i++){
        int dx=x+dir[i][0];
        int dy=y+dir[i][1];
        if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!a[dx][dy]&&!vis[dx][dy]){
            dfs(dx,dy);
        }
    }
    vis[x][y]=0;
    return ;
}