整数快速幂
#include <bits/stdc++.h>
using namespace std;
int quickpow(int x,int n){
int res=x,ans=1;
while(n){
if(n&1){
ans*=res;
}
res*=res;
n>>=1;
}
return ans;
}
int main()
{
int x,n;
scanf("%d%d",&x,&n);
printf("%d
",quickpow(x,n));
//cout << "Hello world!" << endl;
return 0;
}
快速幂取模
typedef long long ll;
using namespace std;
ll qp(ll x,ll n,ll mod){
ll res=1;
while(n){
if(n&ll(1)) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
矩阵快速幂
#include <bits/stdc++.h>
using namespace std;
struct matrix{
int m[N][N];
}ans,res;
matrix mul(matrix a,matrix b,int n){
matrix tmp;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
tmp.m[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
tmp.m[i][j]+=a.m[i][k]*b.m[k][j];
return tmp;
}
void quickpower(int m,int n){
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) ans.m[i][i]=1; else ans.m[i][j]=0;
while(m){
if(m&1){
ans=mul(ans,res);
}
res=mul(res,res);
m>>=1;
}
}
int main()
{
int m;
quickpower(m,n);
//cout << "Hello world!" << endl;
return 0;
}
//最长不下降子序列
#include <bits/stdc++.h>
const int N=1000;
using namespace std;
int b[N],a[N];
int k=0;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>=b[k]){
b[++k]=a[i];
continue;
}
for(int j=k;j>=1;j--){
if(a[i]>b[j]){
b[j+1]=a[i];
break;
}
}
}
printf("%d
",k);
return 0;
}
二叉树的遍历
#include <iostream>
const int N=100;
using namespace std;
int tr[N];
int n;
void xxbl(int node){
cout<<tr[node]<<" ";
if(node<<1<=n) xxbl(node<<1);
if((node<<1)+1<=n) xxbl((node<<1)+1);
}
void zxbl(int node){
if(node<<1<=n) zxbl(node<<1);
cout<<tr[node]<<" ";
if((node<<1)+1<=n) zxbl((node<<1)+1);
}
void hxbl(int node){
if(node<<1<=n) hxbl(node<<1);
if((node<<1)+1<=n) hxbl((node<<1)+1);
cout<<tr[node]<<" ";
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>tr[i];
//xxbl(1);
//zxbl(1);
hxbl(1);
//cout << "Hello world!" << endl;
return 0;
}
已知先序遍历和中序遍历,求层序遍历
#include <iostream>
const int N=100;
using namespace std;
int tr[N];
int a[N],b[N];
int n;
int cnt=0;
void build(int node,int l,int r,int l1,int r1){
tr[node]=a[l];
int k;
for(int i=l1;i<=r1;i++) if(b[i]==node){ k=i;break;}
if(node<<1<=n) build(node<<1,l+1,l+k-l1,l1,k-1);
if((node<<1)+1<=n) build((node<<1)+1,l+k-l1+1,r,k+1,r1);
}
void hxbl(int node){
if(node<<1<=n) hxbl(node<<1);
if((node<<1)+1<=n) hxbl((node<<1)+1);
tr[node]=a[++cnt];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
//cout << "Hello world!" << endl;
build(1,1,n,1,n);
for(int i=1;i<=n;i++) cout<<tr[i]<<" "<<endl;
return 0;
}
回溯算法例子,输出n的全排列
#include <iostream>
const int N=100;
using namespace std;
int a[N];
int s[N];
int cnt;
void p(int n){
for(int i=1;i<=n;i++){
printf("%d ",s[i]);
}
puts("");
}
void dfs(int n,int level){
if(level>n){
p(n);
return;
}
for(int i=1;i<=n;i++)
if(a[i]==0) s[++cnt]=i,a[i]=1,dfs(n,level+1),a[i]=0,cnt--;
}
int main()
{
//cout << "Hello world!" << endl;
int n;
while(cin>>n&&n!=0){
cnt=0;
dfs(n,1);
}
return 0;
}
n皇后问题(递归)
#include <bits/stdc++.h>
const int N=20;
using namespace std;
//int mp[N][N];
int mp[N];//使用一维数组
int ans;
int n;
/*
void op(){
for(int i=1;i<=n;i++) printf("%d ",mp[i]); puts("");
}*/
bool ck(int x,int y){
for(int i=1;i<=x-1;i++) if(x-i==abs(mp[i]-y)) return false;
return true;
}
bool isempty(int m){
for(int i=1;i<=n;i++) if(mp[i]==m) return false;
return true;
}
void dfs(int now,int end){
for(int i=1;i<=end;i++){
if(ck(now,i)&&isempty(i)){
if(now==end) ans++;
else mp[now]=i,dfs(now+1,end),mp[now]=0;
}
}
}
int Nqueue(int n){
memset(mp,0,sizeof(mp));
ans=0;
dfs(1,n);
return ans;
}
int main()
{
while(cin>>n&&n!=0){
cout<<Nqueue(n)<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}