头像

一念花开


访客:109

在线 


活动打卡代码 AcWing 843. n-皇后问题

一念花开
16小时前

第一种方式

include [HTML_REMOVED]

using namespace std;
const int N=20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) puts(g[i]);
puts(“”);
return;
}else{

for(int i=0;i<n;i++){
  if(!col[i] && !dg[u+i] && !udg[n-u+i]){
     g[u][i]='Q';
     col[i]=dg[u+i]=udg[n-u+i]=true;
     dfs(u+1);
     col[i]=dg[u+i]=udg[n-u+i]=false;
     g[u][i]='.';   
  }
}

}

}

int main(){
scanf(“%d”,&n);
for(int i=0;i<n;i){
for(int j=0;j<n;j
){
g[i][j]=’.’;
}
}
dfs(0);
return 0;
}

第二种方式

include [HTML_REMOVED]

using namespace std;
const int N=20;

int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];

void dfs(int x,int y,int s){

if(y==n)y=0,x++;

if(x==n){
if(s==n){
for(int i=0;i<n;i++) puts(g[i]);
puts(“”);
}
return;
}

dfs(x,y+1,s);

if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]){
g[x][y]=’Q’;
row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
dfs(x,y+1,s+1);
row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
g[x][y]=’.’;
}

}

int main(){
scanf(“%d”,&n);
for(int i=0;i<n;i){
for(int j=0;j<n;j
){
g[i][j]=’.’;
}
}
dfs(0,0,0);
return 0;
}



活动打卡代码 AcWing 842. 排列数字

一念花开
18小时前

include [HTML_REMOVED]

using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;

void dfs(int u){
if(n==u){
for(int i=0;i<n;i++){
printf(“%d “,path[i]);

}
puts(“”);
return;
}else{
for(int i=1;i<=n;i++){
if(!st[i]){
st[i]=true;
path[u]=i;
dfs(u+1);
st[i]=false;
path[u]=0;
}
}
}
}

int main(){

scanf(“%d”,&n);
dfs(0);
return 0;
}



活动打卡代码 AcWing 785. 快速排序

一念花开
21小时前

include [HTML_REMOVED]

using namespace std;
const int N=1000010;
int q[N];

void quick_sort(int q[],int l,int r){
if (l >= r) return;
int i=l-1,j=r+1,x=q[l+r>>1];
while(i[HTML_REMOVED]x);
if(i<j) swap(q[i],q[j]);
}

quick_sort(q,l,j);
quick_sort(q,j+1,r);

}

int main(){
int n;
scanf(“%d”,&n);

for(int i=0;i<n;i) scanf(“%d”,&q[i]);
quick_sort(q,0,n-1);
for(int i=0;i<n;i
) printf(“%d “,q[i]);
return 0;
}




各位大佬大家好,最近一直在看动态规划。分析出动态规划状态转移方程,这个有啥诀窍吗?没有找到分析的方法,就是一步一步的把状态转移方程推导出来