头像

V_1




离线:5小时前


活动打卡代码 AcWing 340. 通信线路

V_1
1天前
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

const int N = 1010, M = 20010;
int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];

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

int bfs(int bound) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    deque<int> dq;
    dq.push_back(1);
    dist[1] = 0;

    while (dq.size()) {
        int t = dq.front();
        dq.pop_front();

        if (st[t]) continue;
        if (t == n) return dist[t];

        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i], ed = w[i] > bound ? 1 : 0;
            if (dist[j] > dist[t] + ed) {
                dist[j] = dist[t] + ed;
                if (ed) dq.push_back(j);
                else dq.push_front(j);
            }
        }
    }

    return 0x3f3f3f3f;
}

int main() {
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + (r - l >> 1);
        if (bfs(mid) <= k) r = mid;
        else l = mid + 1;
    }

    if (r == 1e6 + 1) cout << -1 << endl;
    else cout << r << endl;

    return 0;
}


活动打卡代码 AcWing 1135. 新年好

V_1
2天前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int source[6];
int h[N], e[M], ne[M], w[M], idx;
int dist[6][N];
bool st[N];

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

void dijkstra(int start, int dis[]) {
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push({0, start});
    dis[start] = 0;

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

        int v = t.second, d = t.first;
        if (st[v]) continue;

        st[v] = true;
        for (int i = h[v]; ~i; i = ne[i]) {
            int j = e[i];
            if (!st[j] && dis[j] > d + w[i]) {
                dis[j] = d + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distance) {
    if (u == 6) return distance;

    int res = INF;
    for (int i = 1; i <= 5; i++)
        if (!st[i]) {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = false;
        }

    return res;
}

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

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

    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < 6; i++) dijkstra(source[i], dist[i]);

    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 0, 0));

    return 0;
}


活动打卡代码 AcWing 181. 回转游戏

V_1
2天前
#include <iostream>
using namespace std;

const int N = 24;

int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

int oppo[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int q[N];
int path[100];

int f() {
    int cnt[4] = {0};
    for (int i = 0; i < 8; i++) cnt[q[center[i]]]++;

    int s = 0;
    for (int i = 1; i <= 3; i++) s = max(cnt[i], s);

    return 8 - s;
}

void operate(int x) {
    int t = q[op[x][0]];
    for (int i = 0; i < 6; i++) q[op[x][i]] = q[op[x][i + 1]];
    q[op[x][6]] = t;
}

bool dfs(int depth, int max_depth, int last) {
    if (depth + f() > max_depth) return false;
    if (!f()) return true;

    for (int i = 0; i < 8; i++) {
        if (last == oppo[i]) continue;
        operate(i);
        path[depth] = i;
        if (dfs(depth + 1, max_depth, i)) return true;
        operate(oppo[i]);
    }

    return false;
}

int main() {
    while (cin >> q[0], q[0]) {
        for (int i = 1; i < N; i++) cin >> q[i];

        int max_depth = 0;
        while (!dfs(0, max_depth, -1)) max_depth++;

        if (!max_depth) cout << "No moves needed" << endl;
        else {
            for (int i = 0; i < max_depth; i++) printf("%c", path[i] + 'A');
            cout << endl;
        }

        printf("%d\n", q[6]);
    }

    return 0;
}


活动打卡代码 AcWing 180. 排书

V_1
3天前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 18;
int n, a[N];
int w[5][N];

int f() {
    int cnt = 0;
    for (int i = 0; i < n - 1; i++)
        if (a[i + 1] != a[i] + 1) cnt++;

    return (cnt + 2) / 3;
}

bool dfs(int depth, int max_depth) {
    if (depth + f() > max_depth) return false;

    if (f() == 0) return true;

    for (int len = 1; len <= n; len++)
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            for (int k = r + 1; k < n; k++) {
                memcpy(w[depth], a, sizeof a);
                int y = l;
                for (int x = r + 1; x <= k; x++)
                    a[y++] = w[depth][x];
                for (int x = l; x <= r; x++)
                    a[y++] = w[depth][x];

                if (dfs(depth + 1, max_depth)) 
                    return true;

                memcpy(a, w[depth], sizeof a);
            }
        }

    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth++;

        if (depth >= 5) cout << "5 or more" << endl;
        else cout << depth << endl;
    }

    return 0;
}


活动打卡代码 AcWing 171. 送礼物

V_1
3天前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50;
int n, m, k;
int a[N];
int weights[1 <<24], cnt;
int res;

void dfs_1(int u, int s) {
    if (u == k) {
        weights[cnt++] = s;
        return;
    }   

    if ((long) s + a[u] <= m) dfs_1(u + 1, s + a[u]);
    dfs_1(u + 1, s);
}

void dfs_2 (int u, int s) {
    if (u == n) {
        int l = 0, r = cnt - 1;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if ((long) weights[mid] + s <= m) l = mid;
            else r = mid - 1;
        }

        if ((long) weights[l] + s <= m) res = max(res, weights[l] + s);
        return;
    }

    if ((long) s + a[u] <= m) dfs_2(u + 1, s + a[u]);
    dfs_2(u + 1, s);
}

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

    sort(a, a + n, greater<int>());

    k = n / 2 + 2;
    dfs_1(0, 0);

    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights;

    dfs_2(k, 0);

    cout << res << endl;

    return 0;
}


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

V_1
3天前
#include <iostream>
using namespace std;

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

bool dfs(int depth, int max_depth) {
    if (depth > max_depth) return false;

    if (a[depth - 1] == n) return true;

    bool st[N] = {0};
    for (int i = depth - 1; i >= 0; i--) 
        for (int j = i; j >= 0; j--) {
            int s = a[i] + a[j];
            if (s > n || s <= a[depth - 1] || st[s]) continue;

            st[s] = true;
            a[depth] = s;
            if (dfs(depth + 1, max_depth)) return true;
        }

    return false;
}

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

        for (int i = 0; i < max_depth; i++) 
            cout << a[i] << ' ';

        cout << endl;
    }

    return 0;
}


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

V_1
4天前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 10010, M = 22;
int n, m;
int minv[M], mins[M];
int R[M], H[N];
int res = 0x3f3f3f3f;

void dfs(int u, int v, int s) {
    if (v + minv[u] > n) return;
    if (s + mins[u] >= res) return;

    if (s + 2 * (n - v) / R[u + 1] >= res) return;

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

    for (int r = min(R[u + 1] - 1, (int) sqrt(n - v)); 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] = res;

    dfs(m, 0, 0);

    printf("%d\n", res == 0x3f3f3f3f ? 0 : res);

    return 0;
}


活动打卡代码 AcWing 167. 木棒

V_1
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;
int n;
int a[N], len, sum;
bool st[N];

bool dfs(int u, int l, int start) {
    if (u * len == sum) return true;
    if (l == len) return dfs(u + 1, 0, 0);

    for (int i = start; i < n; i++) {
        if (st[i]) continue;
        if (l + a[i] > len) continue;
        if (i > start && !st[i - 1] && a[i] == a[i - 1]) continue;

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

        if (!l || l + a[i] == len) return false;
    }

    return false;
}

int main() {
    while (cin >> n, n) {
        sum = len = 0;
        memset(st, 0, sizeof st);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }

        sort(a, a + n, greater<int>());
        len = a[0];
        while (len <= sum) {
            if (sum % len == 0 && dfs(0, 0, 0)) {
                printf("%d\n", len);
                break;
            }

            len++;
        }
    }

    return 0;
}


活动打卡代码 AcWing 3302. 表达式求值

V_1
8天前
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

unordered_map<char, int> mp;
string s;

void cal(stack<int>& stk, stack<char>& ops) {
    int y = stk.top(); stk.pop();
    int x = stk.top(); stk.pop();
    char op = ops.top(); ops.pop();
    switch (op) {
        case '+': stk.push(x + y); break;
        case '-': stk.push(x - y); break;
        case '*': stk.push(x * y); break;
        case '/': stk.push(x / y); break;
    }        
}

int main() {
    cin >> s;

    mp['('] = 0;
    mp['+'] = mp['-'] = 1;
    mp['*'] = mp['/'] = 2;

    stack<int> stk;
    stack<char> ops;

    for (int i = 0; i < s.size(); i++) {
        char ch = s[i];
        if (isdigit(ch)) {
            int j = i;
            while (j < s.size() && isdigit(s[j])) j++;
            int x = stoi(s.substr(i, j - i));
            stk.push(x);
            i = j - 1;
        } else if (ch == '(') ops.push(ch);
        else if (ch == ')') {
            while (ops.top() != '(') 
                cal(stk, ops);
            ops.pop();
        } else {
            while (ops.size() && mp[ops.top()] >= mp[ch])
                cal(stk, ops);
            ops.push(ch);
        }
    }

    while (ops.size())
        cal(stk, ops);

    cout << stk.top() << endl;

    return 0;
}


活动打卡代码 AcWing 166. 数独

V_1
8天前
#include <iostream>
using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

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

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

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;
}

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

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

    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 state = get(i, j);
                if (ones[state] < minv) {
                    minv = ones[state];
                    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 < M; i++) {
        int t = i;
        while (t) {
            ones[i]++;
            t -= lowbit(t);
        }
    }

    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);
        cout << str << endl;
    }

    return 0;
}