头像

苍茫得胖帅




离线:6小时前


最近来访(4)
用户头像
抒怀
用户头像
Yujuchang
用户头像
喵喵酱
用户头像
int_main

活动打卡代码 AcWing 847. 图中点的层次

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef pair<int, int> PII;//存坐标
const int N = 105;
int n, m;
int g[N][N], d[N][N];//存图以及,距离
queue<PII> q;

int bfs(){
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//(x, y)上下左右四个点偏移量
        for(int i = 0; i < 4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];//偏移后的坐标
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &g[i][j]);
        }
    }
    cout << bfs() << endl;
}


活动打卡代码 AcWing 846. 树的重心

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10, M = 2 * N;//题目指示边为n-1,无向边数存两边
int h[N], e[M], ne[M], idx;//连接表存储边
bool st[N];//存节点是否遍历过了
int ans = N;
int n;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int u){
    //返回该节点子树的节点数目和
    //u代表的是树种的节点编号,不是idx
    st[u] = true;
    //对每个自己点进行递归dfs
    int sum = 1, res = 0;//sum算上根节点,res代表子树的最大节点数目
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int t = dfs(j);
            res = max(res, t);
            sum += t;
        }
    }
    res = max(res, n - sum);//n - sum代表除了该树,其他节点数和,由于是树其它节点保证连通
    ans = min(ans, res);
    return sum;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans;
    return 0;
}



时间复杂度

所有DFS\BFS时间复杂度都和,节点数目(N)以及边数(M)正相关
O(N + M)

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10, M = 2 * N;//题目指示边为n-1,无向边数存两边
int h[N], e[M], ne[M], idx;//连接表存储边
bool st[N];//存节点是否遍历过了
int ans = N;
int n;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int u){
    //返回该节点子树的节点数目和
    //u代表的是树种的节点编号,不是idx
    st[u] = true;
    //对每个自己点进行递归dfs
    int sum = 1, res = 0;//sum算上根节点,res代表子树的最大节点数目
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int t = dfs(j);
            res = max(res, t);
            sum += t;
        }
    }
    res = max(res, n - sum);//n - sum代表除了该树,其他节点数和,由于是树其它节点保证连通
    ans = min(ans, res);
    return sum;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n;
    int a, b;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 845. 八数码

#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;
string str;
unordered_map<string, int> ump; //存距离
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//偏移

int bfs(){
    string end = "12345678x";
    queue<string> q;
    q.push(str);
    ump[str] = 0;
    while(!q.empty()){
        string t = q.front();
        q.pop();
        int d = ump[t];//方便算下一层的距离
        //if(t == end)return d;
        int k = t.find('x');
        int a = k / 3, b = k % 3;
        for(int i = 0; i < 4; i++){
            int x = a + dx[i], y = b + dy[i];//
            if(x >= 0 && x < 3 && y >= 0 && y < 3){
                swap(t[k], t[3 * x + y]);
                if(!ump.count(t)){//没走过
                    ump[t] = d + 1;
                    q.push(t);
                }
                if(t == end)return ump[t];
                swap(t[k], t[3 * x + y]);//换回来
            }
        }
    }
    return -1;
}
int main(){
    for(int i = 0; i < 9; i++){
        char c;
        cin >> c;
        str += c;
    }
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 844. 走迷宫

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef pair<int, int> PII;//存坐标
const int N = 105;
int n, m;
int g[N][N], d[N][N];//存图以及,距离
queue<PII> q;

int bfs(){
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//(x, y)上下左右四个点偏移量
        for(int i = 0; i < 4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];//偏移后的坐标
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &g[i][j]);
        }
    }
    cout << bfs() << endl;
}


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

#include<iostream>
using namespace std;

const int N = 20;//注意斜对角线数组的长度最大可达19(2*9 + 1)
char g[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++)puts(g[i]);
        puts("");
        return;
    }
    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;
}


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

#include <iostream>
using namespace std;

const int N = 10;
int path[N];
bool j[N];
int n;
void dfs(int u){
    if(u == n){
        //遍历到最后一个位置应当输出
        for(int i = 0; i < n; i++)printf("%d ", path[i]);
        puts("");
    }
    else {
        //按顺序遍历每个未使用的数
        for(int i = 1; i <= n; i++){
            if(!j[i]){//如果未使用
                path[u] = i;
                j[i] = true;
                dfs(u + 1);
                j[i] = false;//恢复    
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

#include <iostream>
using namespace std;

typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131;
ULL h[N], p[N];//h[i]表示前i个字符哈希
char str[N];

ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    int n, m;
    scanf("%d%d%s", &n, &m, str + 1);//从1开始存
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }
    int l1, l2, r1, r2;
    while(m--){
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2))puts("Yes");
        else puts("No");
    }
    return 0;
}



C++ 代码

#include<iostream>

typedef unsigned long long ULL;//相当于对2e64取模
const int N = 1e5 + 10, P = 131;
ULL h[N], p[N];
int n, m;
char str[N];

ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main(){

    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];//大小写字母的ASCII码最大为122,不会超过131
    }
    int l1, l2, r1, r2;

    while(m--){
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2))puts("Yes");
        else puts("No");
    }
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx;

void insert(int x){
    int p = (x % N + N) % N;
    ne[idx] = h[p];
    h[p] = idx;
    e[idx++] = x;
}

bool find(int x){
    int p = (x % N + N) % N;
    for(int i = h[p]; i != -1; i = ne[i]){
        if(e[i] == x)return true;
    }
    return false;
}

int main(){
    char op[2];
    int x, n;
    cin >> n;
    memset(h, -1, sizeof(h));
    while(n--){
       scanf("%s%d", op, &x);
       if(op[0] == 'I')insert(x);
       else{
           if(find(x))puts("Yes");
           else puts("No");
       }
    }
    return 0;
}