头像

Birdy




离线:1天前


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

Birdy
1天前

方法1

//时间复杂度O(n!)
#include<iostream>
using namespace std;

const int N=20;   //10*2 因为对角线需要2n-1个空间

char res[N][N];              //存储选择的结果
bool col[N],dg[N],udg[N];   //分别表示列、对角线、反对角线 有没有皇后
int n;

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<res[i]<<endl;
        }    
        cout<<endl;
        return ;
    }

    for(int i=0;i<n;i++){     //遍历第u列
        if(!col[i]&&!dg[i+u]&&!udg[i-u+n]){
            res[u][i]='Q';
            col[i]=dg[i+u]=udg[i-u+n]=true;
            dfs(u+1);
            col[i]=dg[i+u]=udg[i-u+n]=false;
            res[u][i]='.';                       //恢复现场  必须有
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            res[i][j]='.';
    dfs(0);
    return 0;
}

方法2

//时间复杂度(2^(n^2))
#include<iostream>

using namespace std;

const int N=20;

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

void dfs(int x,int y,int s){    //  x是数组的横着的方向   //整个遍历顺序是从左到右、从上到下
    if(x==n){                     
        y++;
        x=0;
    }
    if(y==n){             //已经n行选完了
        if(s==n){
            for(int i=0;i<n;i++)
                cout<<res[i]<<endl;
            cout<<endl;
           // return ;             //return 不能写在这 有一些可能是没有摆满n个皇后
        }
        return ;
    }

    //不选皇后
    dfs(x+1,y,s);

    //选皇后
    if(!row[y]&&!col[x]&&!dg[x+y]&&!udg[n-x+y]){
        res[x][y]='Q';
        row[y]=col[x]=dg[x+y]=udg[n-x+y]=true;
        dfs(x+1,y,s+1);
        row[y]=col[x]=dg[x+y]=udg[n-x+y]=false;
        res[x][y]='.';
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            res[i][j]='.';
    dfs(0,0,0);
    return 0;
}


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

Birdy
2天前
#include<iostream>

using namespace std;

const int N=10;

bool visited[N];    //true 表示该数字i(下标)已经用过
int path[N];
int n;

void dfs(int u){   //u表示第u个位置
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return ;
    }

    for(int i=1;i<=n;i++){
        if(!visited[i]){
            path[u]=i;        
            visited[i]=true;
            dfs(u+1);
            visited[i]=false;    //恢复现场 
            //path[u]=0;         //会被覆盖,所以可以不加
        }
    }

}

int main(){
    cin>>n;
    dfs(0);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Birdy
10天前
#include<iostream>
#include<vector>
using namespace std;

const int N=16;

int st[N];     //st[N] 1表示不选 2表示选 0表示没确定
int n,cnt;
vector<vector<int>> ways;

/*
void dfs(int u)
{
    if (u>n)
    {
        for(int i=1;i<=n;i++){
            if(st[i]==1)
                printf("%d ",i);
        }            
        printf("\n");
        return;
    }

    st[u] = 1;
    dfs(u + 1);     // 第一个分支:选
    st[u] = 0;

    st[u] = 2;
    dfs(u + 1);     // 第二个分支:不选
    st[u] = 0;  // 恢复现场

}*/
void dfs(int u){

    if(u>n){

        vector<int> way;
        for(int i=1;i<=n;i++){
            if(st[i]==1)
                way.push_back(i);
        }
        ways.push_back(way);
        return;
    }

    st[u]=1;
    dfs(u+1);
    st[u]=0;

    st[u]=2;
    dfs(u+1);
    st[u]=0;

}
/*
int main(){
    cin>>n;

    dfs(1);

    return 0;
}*/

int main(){
    cin>>n;
    dfs(1);
    for(int i=0;i<ways.size();i++){
        for(int j=0;j<ways[i].size();j++)   {
            cout<<ways[i][j]<<' ';
        }    
        cout<<endl;    
    }
    return 0;
}





问题 蓝桥

Birdy
11天前

AcWing《蓝桥杯C++ AB组辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/19/group_buy/2655/




Birdy
12天前

题目链接 https://www.acwing.com/problem/content/2/

01背包的递归怎么写?并且需要记录选择物品的下标;
递推的01背包怎么写可以记录物品下标?
哪位大佬帮忙解答一下,谢谢



活动打卡代码 AcWing 2. 01背包问题

Birdy
12天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1010;

int f[N][N];
int v[N],w[N];

int main(){
    int n,m;

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }

    cout<<f[n][m]<<endl;

    return 0;
}

//优化为一维
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int f[N];
int v[N],w[N];

int main(){
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

    }
    cout<<f[m]<<endl;

    return 0;
}
//寻找路径
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;

int f[N][N];
int w[N],v[N];
bool choose[N];

int main()
{
    int m,n;
    cin>>m>>n;

    for(int i=1; i<=m;i++)
        cin>>w[i]>>v[i];
    int i,j;
    for(i=1;i<=m;i++)
        for(j=0;j<=n;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=w[i])
                f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
        }
    cout<<"MAX:"<<f[m][n]<<endl;

    //寻找路径 
    for(i--,j--;i>=1;i--)
        if(f[i][j]==f[i-1][j-w[i]]+v[i] && f[i][j]!=f[i-1][j])
        {
            choose[i]=true;
            j-=w[i];
        }       
    for(i=1;i<=m;i++)
        if(choose[i])
            cout<<i<<" ";


    return 0;
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~