头像

disheng

河北科技师范学院




在线 


最近来访(14)
用户头像
SoumaSumire
用户头像
狐闹
用户头像
要挥剑了
用户头像
哦呼_2
用户头像
回归线
用户头像
小陈同学.
用户头像
ZJ.cao
用户头像
zombotany
用户头像
domyslavy

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

disheng
17小时前

n皇后问题

思路和数字全排列一样的
这里有两个技巧
就是对于对角线和反对角线上是否已经存在皇后的判断:
对角线满足y = x + b 反对角线满足 y = -x + b
所以b = y - x 和b = y + x 每一个(x,y)都可以映射一个其对角线b1和反对角线b2
所以开一个对角线和反对角线bool数组来记录这条斜线上是否已经存在皇后

方法1:

dfs遍历的顺序为每一行看看某一列是否符合条件,是否可放置皇后

# include<iostream>

using namespace std ;

const int N = 10 ;

int n ;
char chess[N][N] ;
bool col[N],diagonal[2 * N],udiagonal[2 * N]; // 列,行,对角线、反对角线四个数组记录该线是否已经存在皇后了 

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                cout << chess[i][j] ;
            }
            cout << endl ;
        }
        cout << endl ;
    }
    for(int i = 0 ; i < n ; i ++)
    {
        if(!col[i] && !diagonal[u + i] && !udiagonal[u - i + n])
        {
            chess[u][i] = 'Q' ;
            col[i] = true ;
            diagonal[u + i] = true ;
            udiagonal[u - i + n] = true ;
            dfs(u + 1) ;
            chess[u][i] = '.' ;
            col[i] = false ;
            diagonal[u + i] = false ;
            udiagonal[u - i + n] = false ;
        }
    }
}

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

    return 0 ;
}

方法2

枚举每一个格子

# include<iostream>

using namespace std ;

const int N = 10 ;

int n ,u ;
char gess[N][N] ;
bool col[N] ,row[N] ,dg[2 * N] , udg[2 * N] ;

void dfs(int x, int y ,int u)
{
    if(y == n) y = 0 , x ++ ; // 注意y最大为n - 1 当y==n的时候y已经越界,我们每次判断一下y是否越界,越界就让他拐下来    
    if(x == n) 
    {
        if(u == n)
        {
            for(int i = 0 ; i < n ; i ++) puts(gess[i]) ;
            cout << endl ;
        }
        return ;
    }

    // 如果放皇后
    if(!col[y] && !row[x] && !dg[x + y] && !udg[x - y + n]) // x 对应的是行, y对应的是列
    {
        col[y] = row[x] = dg[x + y] = udg[x - y + n] = true ;
        gess[x][y] = 'Q' ;
        dfs(x,y + 1,u + 1) ;
        col[y] = row[x] = dg[x + y] = udg[x - y + n] = false ;
        gess[x][y] = '.' ;
    }

    // 如果不放就直接dfs下一个格子
    dfs(x,y + 1,u) ;


}

int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i ++)
    {
        for(int j = 0 ; j < n ; j ++) gess[i][j] = '.' ;
    }
    // 枚举每一个格子
    dfs(0,0,0) ; // 从(0,0)开始,皇后摆放数量一开始是0

    return 0 ;
}



disheng
1天前

解法1:dfs

每次需要知道该枚举哪一位,需要知道可以枚举谁
所以开两个数组,bool st[10] 来记录哪些数还可以枚举使用,int u来记录枚举到了哪一位

# include<iostream>

using namespace std ;

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

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n ; i ++) cout << path[i] << " " ;
        cout << endl ;
    }
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!st[i])
        {
            st[i] = true ;
            path[u] = i ;
            dfs(u + 1) ;
            st[i] = false ;
        }
    }
}

int main()
{
    cin >> n ;
    dfs(0) ;

    return 0 ; 
}

解法2:stlnb

# include<iostream>
# include<vector>
# include<algorithm>

using namespace std ;

void print(vector<int> res)
{
    for(auto i : res) cout << i << " " ;
    cout << endl ;
}

int main()
{
    int n ;
    cin >> n ;
    vector<int> res ;
    for(int i = 1 ; i <= n ; i ++) res.push_back(i) ;
    do print(res) ; while(next_permutation(res.begin(),res.end())) ;

    return 0 ;
}


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

disheng
1天前
# include<iostream>

using namespace std ;

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

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ; i < n ; i ++) cout << path[i] << " " ;
        cout << endl ;
    }
    for(int i = 1 ; i <= n ; i ++)
    {
        if(!st[i])
        {
            st[i] = true ;
            path[u] = i ;
            dfs(u + 1) ;
            st[i] = false ;
        }
    }
}

int main()
{
    cin >> n ;
    dfs(0) ;

    return 0 ; 
}



disheng
2天前
# include<iostream>
# include<cstdio>
# include<algorithm>

using namespace std ;

const int N = 100010 ;

struct Rec
{
    int x ;
    double y ;
    string z ;
    // 重载小于号 记住模板 
    bool operator < (const Rec &t)const
    {
        return x < t.x ;
    }
}a[N] ;

int main()
{
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> a[i].x >> a[i].y >> a[i].z ;
    }
    sort(a,a+n) ; // 这里不能是a[0]和a[n]! 必须是a,a+n!!
    for(int i = 0 ; i < n ; i ++)
    {
        printf("%d %.2lf %s\n",a[i].x,a[i].y,a[i].z.c_str()) ; // printf输出string得加一个.c_str()!!
    }

    return 0 ;
}


活动打卡代码 AcWing 862. 三元组排序

disheng
2天前
# include<iostream>
# include<cstdio>
# include<algorithm>

using namespace std ;

const int N = 100010 ;

struct Rec
{
    int x ;
    double y ;
    string z ;
    // 重载小于号 记住模板 
    bool operator < (const Rec &t)const
    {
        return x < t.x ;
    }
}a[N] ;

int main()
{
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> a[i].x >> a[i].y >> a[i].z ;
    }
    sort(a,a+n) ; // 这里不能是a[0]和a[n]! 必须是a,a+n!!
    for(int i = 0 ; i < n ; i ++)
    {
        printf("%d %.2lf %s\n",a[i].x,a[i].y,a[i].z.c_str()) ; // printf输出string得加一个.c_str()!!
    }

    return 0 ;
}



disheng
2天前

写法1

一个int是32位,就循环32次,每次查看第i位是否为1 (n >> i & 1)如果n的第i位为1就返回1否则就是0

class Solution {
public:
    int NumberOf1(int n) {
        int cnt = 0 ;
        for(int i = 1 ; i <= 32 ; i ++)
        {
            if(n >> i & 1) cnt ++ ;
        }
        return cnt ;
    }
};

写法2

使用lowbit(k)这个函数能返回k的二进制形式的最后一个1

lowbit(k) = k & -k

class Solution {
public:
    int NumberOf1(int n) {
        int cnt = 0 ;
        while(n & -n) 
        {
            n-= n & -n ;
            cnt ++ ;
        }
        return cnt ;
    }
};



disheng
2天前

写法1

一个int是32位,就循环32次,每次查看第i位是否为1 (n >> i & 1)如果n的第i位为1就返回1否则就是0

class Solution {
public:
    int NumberOf1(int n) {
        int cnt = 0 ;
        for(int i = 1 ; i <= 32 ; i ++)
        {
            if(n >> i & 1) cnt ++ ;
        }
        return cnt ;
    }
};

写法2

使用lowbit(k)这个函数能返回k的二进制形式的最后一个1

lowbit(k) = k & -k

class Solution {
public:
    int NumberOf1(int n) {
        int cnt = 0 ;
        while(n & -n) 
        {
            n-= n & -n ;
            cnt ++ ;
        }
        return cnt ;
    }
};


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

disheng
2天前
class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
        vector<vector<int>> res ;
        sort(nums.begin(),nums.end()) ;
        do res.push_back(nums) ; while(next_permutation(nums.begin(),nums.end())) ;
        return res ;
    }
};



disheng
2天前
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> htable ;
        for(auto i : nums)
        {
            if(!htable.count(target - i))
            {
                htable.insert(i) ;
            }
            else
            {
                return {i,target - i} ;
            }
        }
    }
};


活动打卡代码 AcWing 53. 最小的k个数

disheng
2天前
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int,vector<int>,greater<int>> q ;
        for(auto i : input) q.push(i) ;
        vector<int> res ;
        int i = 1 ;
        while(i <= k)
        {
            res.push_back(q.top()) ;
            q.pop() ;
            i ++ ;
        }
        return res ;
    }
};