2022.01.30刷题

2023-10-02 13:53:28

2022.01.30刷题

DFS

排列数字

注意下用state表示时候的运算顺序.

取第 i 位 state >> i & 1 和 state | (1 << i);

int path[10];
int n;
void dfs(int cnt, int state) {
    if (cnt == n) {
        rep(i, 0, n) O(path[i]);
        puts("");
        return;
    }
    rep(i, 0, n) {
        if ((state >> i & 1) == 0) { // 注意这里一定要括起来才行..
            path[cnt] = i + 1;
            dfs(cnt + 1, state | (1 << i));
        }
    }
}
int main() {
    n = read();
    dfs(0, 0);
    return 0;
}
n-皇后问题

x+y 和 x-y+n 两个表示斜线

int n;
bool dx[30], dy[30], sy[30]; //简单的三个状态表示就行了.
char g[20][20];
void dfs(int x) {
    if (x == n) {
        rep(i, 0, n) {
            rep(j, 0, n) printf("%c", g[i][j]);
            puts("");
        }
        puts("");
        return;
    }
    rep(y, 0, n) {
        if (!dx[x + y] && !dy[y - x + n] && !sy[y]) {
            dx[x + y] = dy[y - x + n] = sy[y] = true; 
            g[x][y] = 'Q';
            dfs(x + 1);
            dx[x + y] = dy[y - x + n] = sy[y] = false;
            g[x][y] = '.';
        }
    }
}
int main() {
    n = read();
    rep(i, 0, n) rep(j, 0, n) g[i][j] = '.';
    dfs(0);
    return 0;
}
树的重心

DFS好处, 遍历过程中, 可以求出来子树的点的个数的.

复杂度是 \(O(n+m)\)的.

int h[N5], e[N5 * 2], ne[N5 * 2], idx, ans = N5, n;
bool st[N5]; // h是邻接表, e和ne是边.

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;// 加上一条边.
}

int dfs(int u) {
    st[u] = true;
    int size = 0, sum = 0;
    for (int i = h[u];i != -1;i = ne[i]) {
        int j = e[i];
        if (st[j]) continue;
        int s = dfs(j);
        size = max(size, s);
        sum += s;
    }
    size = max(size, n - sum - 1);
    ans = min(ans, size);
    return sum + 1;
}
int main() {
    n = read();
    memset(h, -1, sizeof h); //树初始时候 变成 -1;
    rep(i, 0, n - 1) {
        int a = read(), b = read();
        add(a, b), add(b, a);
    }
    dfs(1);
    O(ans);
    return 0;
}

BFS

走迷宫

雪菜额外维护了一个 d[N2][N2] 来判断起点到每个点的距离.

char g[N2][N2];
int  dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,-1,1 };

int main() {
    queue<PII> q;
    int n = read(), m = read();
    rep(i, 0, n)rep(j, 0, m) g[i][j] = read();
    q.push({ 0,0 });
    g[0][0] = 1;
    int res = 0;
    while (q.size()) {
        res++;
        int cnt = q.size();
        while (cnt--) {
            auto t = q.front();
            rep(i, 0, 4) {
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x == n - 1 && y == m - 1) {
                    O(res); return 0;
                }
                if (x >= 0 && x < n && y >= 0 && y < m && !g[x][y])
                    q.push({ x,y }), g[x][y] = 1;
            }
            q.pop();
        }
    }
    return 0;
}
八树码

注意是 unordered_set 不是 set ... 要不然会 TLE;

int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
int main() {
    queue<string> qs;
    string state;
    char c[2];
    rep(i, 0, 9) cin >> c, state += c[0];
    int res = 0;
    unordered_set<string> sets;
    qs.push(state), sets.insert(state);
    while (!qs.empty()) {
        int _cnt = qs.size();
        while (_cnt--) {
            string s = qs.front();
            if (s == "12345678x") { O(res);return 0; }
            int x = 0, y = 0, k = s.find('x');
            x = k / 3, y = k % 3;
            rep(i, 0, 4) {
                int xx = x + dx[i], yy = y + dy[i];
                if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) {
                    swap(s[xx * 3 + yy], s[x * 3 + y]);
                    if (!sets.count(s)) {
                        sets.insert(s);
                        qs.push(s);
                    }
                    swap(s[xx * 3 + yy], s[x * 3 + y]);
                }
            }
            qs.pop();
        }
        res++;
    }
    O(-1);
    return 0;
}
图中点的层次
int n, m, e[N5], h[N5], ne[N5], idx, st[N5];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;// 加上一条边.
}

int main() {
    n = read(), m = read();
    memset(h, -1, sizeof h); //树初始时候 变成 -1;
    rep(i, 0, m) {
        int a = read(), b = read();
        add(a, b);
    }
    queue<int> qu;
    qu.push(1);
    int res = 0;
    while (!qu.empty()) {
        int cnt = qu.size();
        while (cnt--) {
            int t = qu.front();
            if (t == n) { O(res);return 0; }
            for (int i = h[t];i != -1;i = ne[i]) {
                int j = e[i]; // 记住这样才能把边取出来
                if (!st[j]) {
                    st[j] = true;
                    qu.push(j);
                }
            }
            qu.pop();
        }
        res++;
    }
    O(-1);
    return 0;
}

拓扑排序

有向图拓扑排序

使用自定义的队列, 可以存下来 拓扑排序的顺序, 妙啊;

const int N = N5;
int n, m, h[N], e[N], ne[N], q[N], d[N], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool bfs() {
    int hh = 0, tt = -1;
    rep(i, 1, n + 1) {
        if (!d[i]) q[++tt] = i;
    }
    while (hh <= tt) {
        int t = q[hh++];
        // cout << t << endl;
        for (int i = h[t]; i != -1;i = ne[i]) {
            int j = e[i];
            // cout << "   " << j << endl;
            if (--d[j] == 0) q[++tt] = j;
        }
    }
    return hh == n; // 注意这里 hh是n 而 tt是 n-1;
}
int main() {
    n = read(), m = read();
    memset(h, -1, sizeof h);
    rep(i, 0, m) {
        int a = read(), b = read();
        add(a, b);
        d[b]++;
    }
    if (bfs()) { rep(i, 0, n)O(q[i]); }
    else { O(-1); }
    return 0;
}

最短路

dijkstra 最短路

遍历过的边 S 和其他的边 T之间, 每次从T最小 dis 的 放到 S中, 然后更新T中其他边的距离, a,b,w 有 dis[a] + w < dis[b] 就更新一下.

边权一定得是正数.
dijkstra 最短路2:

用堆来维护接下来需要遍历的边.

Bellman-ford 最短路

多少条边 遍历多少次. 直接用结构体存就可以.

然后可以判断负环, 如果存在, n次遍历以后还在更新, 那么就说明有一条大于n长度的最短路径, 也就是说有负环.

O(nm)的算法.

最多k条边的最短路径, 只能用bellman-ford

每次备份一下 当前的dis数组, 才能保证在 k 的限制之内. memcpy
spfa

由 dis[b] = min(dis[b], dis[a]+w) 如果 dis[a] 不变的话, dis[b] 也不会变.

BFS进行, 如果变小, 就加入队列, 反复迭代.
spfa求负环

路径上一定存在一个环.

初始时候每个边都放到queue中, 然后求得时候用cnt[N]如果大于了 n 就说明有负环了.
Floyd最短路

d[k,i,j] = d[k-1, i, k] + d[k-1, k, j]

动态规划.

不能有负权回路, 负无穷的最短路径.

生成树.

2022.01.30刷题

prim 最小生成树
  1. 所有 dist[i] 初始化成正无穷
  2. rep(i,0,n)
    1. t \(\leftarrow\) 集合外距离最近的点. (第一步随便挑)
    2. 用t来更新其他点到集合的距离
    3. st[t] = true 加入到集合中.
      1. 只有集合这里和dijkstra不同.

//todo 堆优化.
kruskal
  1. 将所有边按照权重从大到小排序.
    1. O(m logm) 常数非常小
  2. 枚举每条边, a,b,w 如果a, b 不连通, 将w加到集合中.
    1. 并查集. O(m)

二分图

染色法.

一个图是二分图, 当且仅当图中不含奇数环.

int n, m, idx, h[N5], ne[N5 * 2], e[N5 * 2], st[N5];
int a, b;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool ok = true;

void dfs(int a, int c) {
    st[a] = c;
    for (int i = h[a]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j])dfs(j, 3 - c);
        else if (st[j] == c) ok = false;
    }
}


int main() {
    n = read(), m = read();
    memset(h, -1, sizeof h);
    rep(i, 0, m) {
        a = read(), b = read();
        add(a, b);add(b, a);
    }

    rep(i, 1, n + 1) {
        if (!st[i] && ok) dfs(i, 1);
    }
    puts(ok ? "Yes" : "No");
}
匈牙利算法 二分图匹配

返回图中匹配成功的数量最大值.

如果想要去匹配的人已经有人了, 那就尝试换一个.

O(n * m)

这个回溯怎么写的还是没懂..

int h[510], ne[N5], e[N5];
int match[510];
bool st[510];
int n1, n2, m, idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (match[j] == 0 || find(match[j])) {
                match[j] = x; //这是个回溯么?
                return true;
            }
        }
    }
    return false;
}

int main() {
    n1 = read(), n2 = read(), m = read();
    memset(h, -1, sizeof h);
    while (m--) {
        add(read(), read());
    }
    int res = 0;
    rep(i, 1, n1 + 1) {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }
    O(res);
    return 0;
}
上一篇：【2022/01/30】thinkphp源码无差别阅读（三十二）


下一篇：[LeetCode] 407. Trapping Rain Water II 收集雨水之二