头像

4444486




离线:2小时前


最近来访(34)
用户头像
辣鸡号航母
用户头像
三三得玖
用户头像
键盘敲烂
用户头像
JcWing
用户头像
笑脸人
用户头像
AcWing2AK
用户头像
菜狗一枚
用户头像
星尘流天
用户头像
Gnomeshgh
用户头像
Luminous_0
用户头像
北海没有WA
用户头像
茉窈my
用户头像
acsRe
用户头像
hgg6666
用户头像
whale77
用户头像
yxc
用户头像
acwing_7777
用户头像
头发乱了0
用户头像
不拿NOI金牌不改名
用户头像
飞劫


4444486
2小时前
/*
    spfa就是单点能够进行多次松弛操作的堆优化dijkstra
    dijkstra不能够解决负权边的原因就是一个点只能松弛一次
    因为从优先队列出队说明dist最小 后面更大的dist经过正权边不可能再比对头元素的dist小
    而如果存在负权边的话 后面更大的dist点就有可能经过负权边比对头元素的dist小
    而一个点在出队之后dist更新的话 就需要重新拿它进行松弛操作(更新邻点的最短距离)

    虽然不需要记录点是否进行过松弛操作 但还是需要bool数组
    它的含义与dijkstra不同 它用来记录某个点是否已经入队
    因为节点在出队的时候就会进行一遍松弛操作
    而spfa只需要在节点的dist更新的时候才需要进行松弛(入队)
    所以如果重复入队而不是dist更新了再入队的话 重复松弛的点一定在做无用功

    spfa也算是bellman-ford的优化 只有dist[b]被更新了 才需要用它进行松弛操作
    因此不需要优先级队列 只有等待进行松弛操作的节点
    另一个角度:使用优先级队列也没有意义,dijkstra使用优先队列目的就是为了节点第一次出队时能够得到最短距离
    而有负权边就算使用了优先队列也不能确保得到最短距离
*/
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;
int h[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];
int n, m;

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

int spfa () {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> heap;
    heap.push(1);

    while (heap.size()) {
        int t = heap.front(); heap.pop();

        st[t] = false; //出队了之后重新置为false

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                //防止做无用功 所以不能重复入队
                if (!st[j]) {
                    heap.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

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

    memset(h, -1, sizeof h);
    while ( m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();
    if (t == 0x3f3f3f3f) puts("impossible");
    else cout << t << endl;

    return 0;
}


活动打卡代码 AcWing 166. 数独

4444486
5小时前
/*
    优先搜索决策数量较少的点 => 行 & 列 & 九宫格  找到1的数量最小的点

    找到数量最少的点之后需要知道还剩下哪些数字
    因此可以每次使用lowbit取出最小的1  然后预处理所有的低位1 将数映射到该位的下标

    因为要快速找到二进制数中1的个数 所以可以预处理 将所有二进制中1的个数保存起来
*/

#include <iostream>

using namespace std;

const int N = 9;
int row[N], col[N], cell[3][3];
int map[1 << N], ones[1 << N];
char str[100];

void init () {
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

int lowbit (int x) {
    return x & -x;
}

int get (int x, int y) {
    return row[x] & col[y] & cell[x / 3][y / 3];
}

void draw (int x, int y, int t, bool is_set) {
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

bool dfs (int cnt) {
    if (!cnt) return true;

    //找到1数量最少的点
    int minv = 10;
    int x, y;
    for (int i = 0; i < N; ++ i)
        for (int j = 0; j < N; ++ j)
            if (str[i * N + j] == '.') {
                int t = ones[get(i, j)];
                if (t < minv) {
                    minv = t;
                    x = i;
                    y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i)) {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1))  return true;
        draw(x, y, t, false);
    }

    return false;
}

int main () {
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e') {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }

    return 0;
}



活动打卡代码 LeetCode 1282. 用户分组

4444486
9小时前
class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        map<int, vector<int>> hash;
        vector<vector<int>> res;

        for (int i = 0; i < groupSizes.size(); ++ i) {
            hash[groupSizes[i]].push_back(i);
            if (hash[groupSizes[i]].size() == groupSizes[i]) {
                res.push_back(hash[groupSizes[i]]);
                hash[groupSizes[i]].clear();
            }
        }

        return res;
    }
};


活动打卡代码 AcWing 178. 第K短路

4444486
22小时前
/*
    一般A*的heap只需要存储到终点的估价函数 
    但是这道题目需要返回的是起点到终点的距离(由于heap排序需要估价函数 而答案有需要dist)
    因此需要创建一个三元组来存放 f 和 dist 并且按照f进行排序

    由于估价函数要小于等于真实值 所以反向进行一遍dijkstra就能得到每一个点到终点的最短距离

    细节问题:1.需要清楚为什么估价函数的值必须小于等于真实值(出队是最短路径)
    2.为什么路径上的每个点也是最多经过K次
    3.A*的优先队列中需要存储哪些信息
    4.如何得到f估价函数
    5.当估价函数都为0时 就是dijkstra算法
*/

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

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

#define x first
#define y second

const int N = 1010, M = 20010;
//由于需要反向做一遍dijkstra 因此保存所有反向边
int h[N], rh[N], ne[M], e[M], w[M], idx;
int dist[N];  //保存dijkstra的最短路径
bool st[N];
int n, m, S, E, k;
int cnt[N];

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

void dijkstra () {
    memset(dist, 0x3f, sizeof dist);
    dist[E] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, E});

    while (heap.size()) {
        auto [dis, ver] = heap.top(); heap.pop();

        if (st[ver]) continue;
        st[ver] = true;

        //遍历相邻的边
        for (int i = rh[ver]; i != -1; i = ne[i]) {
            int j = e[i];

            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int Astar () {
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S], {0, S}});

    while (heap.size()) {
        auto t = heap.top(); heap.pop();

        int ver = t.y.y, dis = t.y.x;

        //出队的时候判断
        ++ cnt[ver];
        if (cnt[E] == k) return dis;  //返回到起点的距离

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];

            //将能够放入的点都放入队列
            if (cnt[j] < k) heap.push({dis + w[i] + dist[j], {dis + w[i], j}});
        }
    }

    return -1;
}

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

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for (int i = 0; i < m; ++ i) {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);
        add(rh, b, a, c);
    }

    cin >> S >> E >> k;
    if (S == E) ++ k;

    dijkstra();

    cout << Astar() << endl;

    return 0;
}



4444486
1天前

1098:城堡问题

为什么这道题使用dfs求连通块的数目会错误

错误的代码:

#include <iostream>

using namespace std;

const int N = 55;
int n, m;
int g[N][N];
bool st[N][N];
int ans = 1;

int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};

void dfs (int x, int y) {
    cout << x << ' ' << y << endl;
    st[x][y] = true;

    for (int i = 0; i < 4; ++ i) {
        int a = dx[i] + x, b = dy[i] + y;
        if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
        if (g[x][y] >> i & 1) continue;
        dfs(a, b);
    }
}

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

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> g[i][j];

    int ans = 0;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            if (!st[i][j]) {
                dfs(i, j);
                ++ ans;
            }

    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 170. 加成序列

4444486
1天前
/*
    普通的dfs遍历会遍历大约100层的深度
    但是可以发现二进制倍增的话 它答案序列的长度一定很短
    因此设置depth表示答案序列的长度 不断++depth
*/
#include <iostream>

using namespace std;

const int N = 110;
int path[N];
int n;

bool dfs (int u, int depth) {
    if (u == depth) {
        if (path[u - 1] == n) return true;
        return false;
    }

    //每一个位置枚举的数要求不同即可(用于回溯判重)
    bool st[N] = {0};

    //从大到小枚举(优化搜索顺序)
    for (int i = u - 1; i >= 0; -- i)
        for (int j = i; j >= 0; -- j) {
            int s = path[i] + path[j];
            if (s < path[u - 1] || s > n || st[s]) continue;
            st[s] = true;
            path[u] = s;
            if (dfs(u + 1, depth)) return true;
        }

    return false;
}

int main () {
    while (cin >> n, n) {
        path[0] = 1;
        int depth = 1;
        while (!dfs(1, depth)) ++ depth;

        for (int i = 0; i < depth; ++ i) cout << path[i] << ' ';
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 168. 生日蛋糕

4444486
1天前
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;
int n, m;
int mins[N], minv[N];
int R[N], H[N];
int ans = INF;

void dfs (int u, int v, int s) {
    if (v + minv[u] > n) return;
    if (s + mins[u] >= ans) return;
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;

    if (!u) {
        if (v == n) ans = s;
        return;
    }

    for (int r = min((int)sqrt(n - v), R[u + 1] - 1); r >= u; -- r)
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; -- h) {
            int t = 0;
            if (u == m) t = r * r;
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}

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

    for (int i = 1; i <= m; ++ i) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);

    if (ans == INF) ans = 0;
    cout << ans << endl;

    return 0;
}



活动打卡代码 AcWing 167. 木棒

4444486
1天前
/*
    搜索顺序:大棍选择小棍 而不是小棍选择大棍

    1.优化搜索顺序:拼接每一根大棍是都从大到小枚举
    2.排除等效冗余:2.1拼接一根大棍123 和 321是相同的 因此每一根大棍内部按照组合数枚举
    2.2在拼接一根大棍的时候不能在一个for循环中选择长度相同的小棍
    2.3如果在拼接大棍时 放入第一根小棍失败了(也就是回溯回来了 那么直接return回溯)
       因为如果回溯到该大棍的第一根小棍的话 说明后面所有摆放的方法均尝试过且失败了
       如果不直接回溯的话 该小棍放在后面的任意位置都不可能成功
*/

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

using namespace std;

const int N = 70;
int w[N];
bool st[N]; //虽然是组合 但由于是多根木棍共用一个数组
int length, n, sum;

//当前是第几根木棍 当前木棍的和 当前节点只能从哪个元素开始枚举
bool dfs (int u, int s, int start) {
    //到达叶子节点的条件(大木棍的总长度等于sum)
    if (u * length == sum) return true;

    //如果该大棍刚好达到了length长度就拼下一根木棍
    if (s == length) return dfs(u + 1, 0, 0);

    for (int i = start; i < n; ++ i) {
        if (st[i] || s + w[i] > length) continue;

        st[i] = true;
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false;

        //如果是最后一根小木棍拼接失败的话也是直接return
        //如果是第一根小木棍拼接失败的话直接return
        if (s == 0 || s + w[i] == length) return false;

        //后面的木棍不能选择前面长度相同的
        int j = i + 1;
        while (j < n && w[j] == w[i]) ++ j;
        i = j - 1;
    }

    return false;
}

int main () {
    while (cin >> n, n) {
        memset(st, 0, sizeof st);
        sum = 0;
        for (int i = 0; i < n; ++ i) {
            cin >> w[i];
            sum += w[i];
        }

        sort(w, w + n, [](int a, int b){
            return a > b;            
        });

        length = 1;
        while (true) {
            if(sum % length == 0 && dfs(0, 0, 0)) {
                cout << length << endl;
                break;
            }
            ++ length;
        }
    }

    return 0;
}



活动打卡代码 AcWing 165. 小猫爬山

4444486
2天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int w[N];
int sum[N];
int n, m;
int ans = N;

void dfs (int g, int u) {
    //最优性剪枝(提前预测当前树不可能找到答案)
    if (g >= ans) return;

    if (u == n) {
        ans = g;
        return;
    }

    //遍历每个组 尝试将其放入
    for (int i = 0; i < g; ++ i) {
        if (sum[i] + w[u] <= m) {  //可行性剪枝(只有满足条件才递归)
            sum[i] += w[u];
            dfs(g, u + 1);
            sum[i] -= w[u];
        }
    }

    //新开一个组
    sum[g] = w[u];
    dfs(g + 1, u + 1);
    sum[g] = 0;
}

int main () {
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) cin >> w[i];

    //优化搜索顺序(先搜索重的猫)
    sort(w, w + n, [](int a, int b){
        return a > b;
    });

    //当前组的个数 当前选择到的猫的编号
    dfs(0, 0);

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1118. 分成互质组

4444486
3天前

相当于坑位选数 => 每一个组就是一个坑位 然后每一个组都是共用一个质数数组的 因此还有另外一种坑位(所有的组共用)选数

#include <iostream>

using namespace std;

const int N = 10;
int group[N][N];
int p[N];
bool st[N];
int n;
int ans = N;

int gcd (int a, int b) {
    return b ? gcd(b, a % b) : a;
}

bool check (int group[], int g_nums, int i) {
    for (int j = 0; j < g_nums; ++ j)
        if (gcd(p[group[j]], p[i]) > 1) return false;
    return true;
}

void dfs (int g, int start, int g_nums, int u) {
    if (g >= ans) return;

    //到达叶节点 => 遍历到最后一个坑位
    if (u == n) ans = g; //组号就是所有的组数

    bool flag = true; //用来判断该组中是否选了数 如果没有就需要新建一个组
    for (int i = start; i < n; ++ i) {
        if (!st[i] && check(group[g], g_nums, i)) {
            st[i] = true;
            group[g][g_nums] = i;
            dfs(g, i + 1, g_nums + 1, u + 1);
            st[i] = false;

            flag = false;
        }
    }

    if (flag) dfs(g + 1, 0, 0, u);
}

int main () {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> p[i];

    //1.如果当前数能够与最后一组所有的数互质就放入
    //2.如果不能互质的话就新建一个组
    //因此dfs需要传入组号 来分辨是哪一个组 
    //由于求的是组合问题 所以需要传入一个start(该节点能够从哪一个数开始遍历)
    //同时还需要判断一个数与组中所有的数是否都互质 因此需要传入该组中当前元素个数
    //最后还需要传入一个dfs问题都需要传入的参数 => 当前已经选择到第几个数
                                                 //(用来判断是否到达叶节点)

    //1号组 从第0个数开始选  组中元素个数为0  当前选择到第0个坑位
    dfs(1, 0, 0, 0);

    cout << ans << endl;

    return 0;
}