5.24 基础题目

 

快速幂

#include<bits/stdc++.h>
using namespace std;
//126348976 982638476 938420413
int main(){
    int a,b,p;
    cin>>a>>b>>p;
    long long res = 1,ci=1;
    int flag=0;
    if(b==0){
            res%=p;
        }
    else{
        while(b){
    	if (flag==0)ci=a%p;
    	else
          ci=(ci%p)*(ci%p)%p;
        
		if (b&1)res=(res*(ci%p))%p;
        b>>=1;
        flag++;
        //cout<<ci<<"  "<<res<<endl;
    }
    }
    cout<<res<<endl;
    return 0;
}

64位整数乘法

#include<bits/stdc++.h>
/*
a*b=a+a+a+...+a
a*1=a
a*2=2a
a*4=4a;
...
a*(2^k)=2^k*a;
*/
using namespace std;
typedef long long LL;
int main(){
    LL a,b,p;
    cin>>a>>b>>p;
    LL res=0;
    while(b){
        if(b&1)res=(res+a)%p;
        b>>=1;
        a=a*2%p;
    }
    cout<<res<<endl;
    return 0;
}

最短Hamilton路径

1s约计算1亿次；

 f[state][j]=

f[state_k][j]+weight[k][j];

state_k是state除去j之后的集合，state_k要包含k，k是state_k二进制表示中为1的下标，枚举出k

state_k=state-2^j;

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

        if ((state_k>>j )& 1 == 0)

          {    

                state=state_k+2^j;

                f[state][j]=f[state_k][j]+weight[k][j];

          }

}

 

#include <bits/stdc++.h>
 
using namespace std;
const int N=20,M=1<<20; 
int n;
int f[M][N],weight[N][N];
int main(){
	cin>>n;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++){
			cin>>weight[i][j];
		}
		
	memset(f,0x3f,sizeof(f));
	f[1][0]=0;
	for(int i = 0;i < 1<<n;i++)//枚举所有的状态 
		for(int j = 0;j < n;j++){//枚举状态i二进制表示中所有的1的位置 
			if(i>>j & 1)
				for(int k = 0;k < n;k++)//枚举状态i去掉第j位后的剩余的1的位置 
					if(i-(1<<j) >> k & 1)//第k位是1 
						f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[k][j]);
		}
	cout<<f[(1<<n)-1][n-1]<<endl;
	return 0;
}

汉诺塔问题（三塔）

#include <bits/stdc++.h>
using namespace std;
//f(x)=2^x-1
int hnt(int st,int mid,int dst,int n){
	if(n==1){
		//cout<<"from "<<char(st)<<" through "<<char(mid)<<" to "<<char(dst)<<" with "<<n<<endl;
		return 1;
	}
	else {
		int sum=0;
		cout<<"from "<<char(st)<<" through "<<char(dst)<<" to "<<char(mid)<<" with "<<n-1<<endl;
		sum+=hnt(st,dst,mid,n-1);
		cout<<"from "<<char(st)<<" through "<<char(mid)<<" to "<<char(dst)<<" with "<<1<<endl;
		sum+=hnt(st,mid,dst,1);
		cout<<"from "<<char(mid)<<" through "<<char(st)<<" to "<<char(dst)<<" with "<<n-1<<endl;
		sum+=hnt(mid,st,dst,n-1);
		return sum;
	}
}
int main(){
	int st,mid,dst,n;
	st=int('A'),mid=int('B'),dst=int('C');
	n=12;
	int ans = hnt(st,mid,dst,n);
	cout<<ans;
	return 0;
} 
 
 
 

四塔汉诺塔问题

// 凡是用到min的都需要，赋较大值。
    // memset以字节形式重置(int: 0x3f3f3f3f)
    //又0x3f的2倍为最大整数,所以还可以满足加法不越界

#include<bits/stdc++.h>
 
using namespace std;
const int N=15;
int d[N],f[N];
int main(){
    d[1]=1;
    for(int i = 2;i <=12;i++ )
    d[i]=d[i-1]+1+d[i-1];
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    f[1]=1;
    //先让i个盘到B塔或者C塔，剩下的n-i盘在3塔情况下移到D
//再将i盘在4塔(因为D塔都是更重的盘)情况下移动到D。因为对于i我们不知道哪个最优，因此
//因此推导为 f[n] = min(f[n],2*f[i]+d[n-i])(for i in [1..n-1])
	for(int i =2;i <= 12;i++)
		for(int j = 1;j < i;j++)
			f[i]=min(f[i],f[j]+d[i-j]+f[j]);
	for(int i =1;i <= 12;i++)
		cout<<f[i]<<endl;
    
    
    return 0;
}