2n皇后问题其实也挺简单的
一开始囿于8皇后的思想 觉得只需要一个之前的数组 结果要开的数组都是double的
以行为递归参数 然后准放数组在放了之后直接置0，其他数组置1 回溯准放数组在放了之后恢复1，其他数组恢复0
只需要一次嵌套递归就ok
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } #define y1 hhhh ll T; const int N=30; int n; bool f[N][N],vis[N][N],line1[N],line2[N],x1[N],y1[N],x2[N],y2[N]; int ans=0; void dfs(int x){ if(x==n){ ans++; return; } for(int y=0;y<n;y++){ if(!f[x][y]&&vis[x][y]&&!line1[y]&&!x1[x-y+7]&&!y1[x+y]){ f[x][y]=1;vis[x][y]=0;line1[y]=1;x1[x-y+7]=1;y1[x+y]=1; for(int yy=0;yy<n;yy++){ if(!f[x][yy]&&vis[x][yy]&&!line2[yy]&&!x2[x-yy+7]&&!y2[x+yy]){ f[x][yy]=1;vis[x][yy]=0;line2[yy]=1;x2[x-yy+7]=1;y2[x+yy]=1; dfs(x+1); f[x][yy]=0;vis[x][yy]=1;line2[yy]=0;x2[x-yy+7]=0;y2[x+yy]=0; } } f[x][y]=0;vis[x][y]=1;line1[y]=0;x1[x-y+7]=0;y1[x+y]=0; } } } void solve(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>vis[i][j]; } } dfs(0); cout<<ans; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } // cout<<ans; return 0; }递归实现指数型枚举 传送门
意思是在1~n中选择任意多的数 每行以升序顺序输出
一开始的想法是dfs 然后一想这其实是状态压缩 从0~1<<n可以表示所有状态
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } #define y1 hhhh ll T; const int N=30; int n; bool f[N][N],vis[N][N],line1[N],line2[N],x1[N],y1[N],x2[N],y2[N]; int ans=0; void dfs(int x){ if(x==n){ ans++; return; } for(int y=0;y<n;y++){ if(!f[x][y]&&vis[x][y]&&!line1[y]&&!x1[x-y+7]&&!y1[x+y]){ f[x][y]=1;vis[x][y]=0;line1[y]=1;x1[x-y+7]=1;y1[x+y]=1; for(int yy=0;yy<n;yy++){ if(!f[x][yy]&&vis[x][yy]&&!line2[yy]&&!x2[x-yy+7]&&!y2[x+yy]){ f[x][yy]=1;vis[x][yy]=0;line2[yy]=1;x2[x-yy+7]=1;y2[x+yy]=1; dfs(x+1); f[x][yy]=0;vis[x][yy]=1;line2[yy]=0;x2[x-yy+7]=0;y2[x+yy]=0; } } f[x][y]=0;vis[x][y]=1;line1[y]=0;x1[x-y+7]=0;y1[x+y]=0; } } } void solve(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>vis[i][j]; } } dfs(0); cout<<ans; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } // cout<<ans; return 0; }递归实现排列型枚举
输出1~n的所有排列组合
这其实可以用next_permutation做 记住这个函数如果遇到的是最后一个排列的话是返回0的
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } ll T,N; int a[100]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ a[i]=i; } do{ for(int i=1;i<=n;i++)cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a+1,a+n+1)!=0); } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }dfs写法
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } ll T,N; bool vis[100]; vector<int>ans; int n; void dfs(int x){ if(x==n+1){ for(auto item:ans)cout<<item<<" "; cout<<endl; return ; } for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=1; ans.push_back(i); dfs(x+1); ans.pop_back(); vis[i]=0; } } } void solve(){ cin>>n; dfs(1); } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }比较起来的话 还是stl快一点
简单斐波那契 简单斐波那契，，， 直接longlong不讲道理
#include<vector> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<map> #include<queue> #include<algorithm> #include<ctime> #include<cmath> #include<cstdlib> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; #define rg register typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } inline int read() { int X=0,w=1; char c=getchar(); while(c<'0'||c>'9') { if (c=='-') { w=-1; } c=getchar(); } while(c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar(); } return X*w; } //inline void w(int x) { if(x>9) w(x/10); putchar(x+'0'); } ll T,N; ll a[100]; void solve(){ int n; cin>>n; a[1]=0; a[2]=1; for(int i=3;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } for(int i=1;i<=n;i++)cout<<a[i]<<" "; } int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); T=1; //cin>>T; while(T--){ solve(); } return 0; }