头像

烤肉

暨南大学




离线:30分钟前


最近来访(63)
用户头像
来感觉了
用户头像
冰之韵
用户头像
WangJY
用户头像
123_34
用户头像
铁锅炖大鹅
用户头像
OI
用户头像
wssdl
用户头像
Van_sama
用户头像
yuanxinwang2022
用户头像
@.@_7
用户头像
SABI
用户头像
che_che
用户头像
妮可_
用户头像
Carver
用户头像
CHN右手
用户头像
先去学习了
用户头像
巾凡.
用户头像
ycq
用户头像
米龙
用户头像
大雪莱

活动打卡代码 AcWing 4222. 罐子

烤肉
5小时前
#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> PII;

string st[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

struct Node
{
    int a, b, step;
    string s;
};

int a, b, c;

void bfs()
{
    queue<Node> q;
    map<PII, int> h;

    q.push({0, 0, 0, ""});
    h[{0, 0}] = 1;

    while (!q.empty())
    {
        auto t = q.front(); q.pop();

        if (t.a == c || t.b == c)
        {
            cout << t.step << endl;
            for (int i = 0; i < t.s.size(); ++i)
                cout << st[t.s[i] - '1'] << endl;
            return;
        }

        if (h[{a, t.b}] != 1)
            h[{a, t.b}] = 1, q.push({a, t.b, t.step + 1, t.s + "1"});
        if (h[{t.a, b}] != 1)
            h[{t.a, b}] = 1, q.push({t.a, b, t.step + 1, t.s + "2"});
        if (h[{0, t.b}] != 1)
            h[{0, t.b}] = 1, q.push({0, t.b, t.step + 1, t.s + "3"});
        if (h[{t.a, 0}] != 1)
            h[{t.a, 0}] = 1, q.push({t.a, 0, t.step + 1, t.s + "4"});

        if (t.a >= b - t.b && h[{t.a - (b - t.b), b}] != 1) //a能把b装满
            h[{t.a - (b - t.b), b}] = 1, q.push({t.a - (b - t.b), b, t.step + 1, t.s + "5"});
        else if (t.a < b - t.b && h[{0, t.b + t.a}] != 1) //把a倒完也装不满
            h[{0, t.b + t.a}] = 1, q.push({0, t.b + t.a, t.step + 1, t.s + "5"});
        if (t.b >= a - t.a && h[{a, t.b - (a - t.a)}] != 1) //b能把a装满
            h[{a, t.b - (a - t.a)}] = 1, q.push({a, t.b - (a - t.a), t.step + 1, t.s + "6"});
        else if (t.b < a - t.a && h[{a + t.b, 0}] != 1) //把b倒完也装不满
            h[{t.a + t.b, 0}] = 1, q.push({t.a + t.b, 0, t.step + 1, t.s + "6"});
    }

    puts("impossible");
}

int main()
{
    cin >> a >> b >> c;

    bfs();
    return 0;
}



烤肉
17小时前
#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
string n;

int char_to_int(char x)
{
    if (x >= 'A' && x <= 'F')
        return x - 'A' + 10;
    if (x >= 'a' && x <= 'f')
        return x - 'a' + 10;
    if (x >= '0' && x <= '9')
        return x - '0';
}

char int_to_char(int x)
{
    if (x >= 10)
        return x - 10 + 'A';
    return x + '0';
}

int first(string t, int n) //第一步,任意进制转10进制
{
    int dec = 0;
    for (int i = 0; i < t.size(); ++i)
        dec = dec * n + char_to_int(t[i]);
    return dec;
}

string second(int dec, int n) //第二步,十进制转任意进制
{
    string res;
    while (dec)
        res += int_to_char(dec % n), dec /= n;
    reverse(res.begin(), res.end()); //记住是反着的
    return res;
}

int main()
{
    cin >> a >> n >> b;
    //把a进制数n转换成b进制数

    cout << second(first(n, a), b) << endl;
    return 0;
}


活动打卡代码 AcWing 3438. 数制转换

烤肉
17小时前
#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
string n;

int char_to_int(char x)
{
    if (x >= 'A' && x <= 'F')
        return x - 'A' + 10;
    if (x >= 'a' && x <= 'f')
        return x - 'a' + 10;
    if (x >= '0' && x <= '9')
        return x - '0';
}

char int_to_char(int x)
{
    if (x >= 10)
        return x - 10 + 'A';
    return x + '0';
}

int first(string t, int n) //第一步,任意进制转10进制
{
    int dec = 0;
    for (int i = 0; i < t.size(); ++i)
        dec = dec * n + char_to_int(t[i]);
    return dec;
}

string second(int dec, int n) //第二步,十进制转任意进制
{
    string res;
    while (dec)
        res += int_to_char(dec % n), dec /= n;
    reverse(res.begin(), res.end()); //记住是反着的
    return res;
}

int main()
{
    cin >> a >> n >> b;
    //把a进制数n转换成b进制数

    cout << second(first(n, a), b) << endl;
    return 0;
}



烤肉
18小时前

感觉有点写复杂了

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

using namespace std;

const int N = 110;

int n, T, u;
char s1[N], s2[N], s[2 * N], tmp[2 * N];

struct Node
{
    string s;
    int step;
};

void shuffle()
{
    for (int i = 0, j = 1; i < n; j += 2, ++i)
        tmp[j] = s1[i];
    for (int i = 0, j = 0; i < n; j += 2, ++i)
        tmp[j] = s2[i];

    for (int i = 0; i < n; ++i)
        s1[i] = tmp[i];
    for (int i = n; i < 2 * n; ++i)
        s2[i - n] = tmp[i];
}

bool check()
{
    for (int i = 0; i < 2 * n; ++i)
        if (tmp[i] != s[i])
            return false;
    return true;
}

string c2s(char c[], int n)
{
    string t;
    for (int i = 0; i < n; ++i)
        t += c[i];
    return t;
}

void bfs()
{
    queue<Node> q;
    unordered_map<string, int> h;

    q.push({c2s(tmp, n + n), 0});
    h[q.front().s] = 1;

    while (!q.empty())
    {
        auto t = q.front(); q.pop();

        if (check())
        {
            cout << u << ' ' << t.step << endl;
            return;
        }

        shuffle();
        if (h[c2s(tmp, 2 * n)] != 1)
            q.push({c2s(tmp, 2 * n), t.step + 1}), h[q.front().s] = 1;
    }

    cout << u << ' ' << -1 << endl;
}

int main()
{
    cin >> T;
    for (u = 1; u <= T; ++u)
    {
        memset(tmp, 0, sizeof tmp);
        cin >> n >> s1 >> s2 >> s;
        bfs();
    }
    return 0;
}


活动打卡代码 AcWing 4221. 洗牌

烤肉
18小时前
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cstring>

using namespace std;

const int N = 1100;

int n, T, res, u;
char s1[N], s2[N], s[2 * N], tmp[2 * N];

struct Node
{
    string s;
    int step;
};

void shuffle()
{
    for (int i = 0, j = 1; i < n; j += 2, ++i)
        tmp[j] = s1[i];
    for (int i = 0, j = 0; i < n; j += 2, ++i)
        tmp[j] = s2[i];

    for (int i = 0; i < n; ++i)
        s1[i] = tmp[i];
    for (int i = n; i < 2 * n; ++i)
        s2[i - n] = tmp[i];
}

bool check()
{
    for (int i = 0; i < 2 * n; ++i)
        if (tmp[i] != s[i])
            return false;
    return true;
}

string c2s(char c[], int n)
{
    string t;
    for (int i = 0; i < n; ++i)
        t += c[i];
    return t;
}

void bfs()
{
    queue<Node> q;
    unordered_map<string, int> h;
    res = -1;

    q.push({c2s(tmp, n + n), 0});
    h[q.front().s] = 1;

    while (!q.empty())
    {
        auto t = q.front(); q.pop();

        if (check())
        {
            cout << u << ' ' << t.step << endl;
            return;
        }
        shuffle();
        if (h[c2s(tmp, 2 * n)] != 1)
            q.push({c2s(tmp, 2 * n), t.step + 1}), h[q.front().s] = 1;
    }

    cout << u << ' ' << -1 << endl;
}

int main()
{
    cin >> T;
    for (u = 1; u <= T; ++u)
    {
        memset(tmp, 0, sizeof tmp);
        cin >> n >> s1 >> s2 >> s;
        bfs();
    }
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

烤肉
19小时前
#include <iostream>

using namespace std;

const int N = 30010;

int n, m, T;
int p[N], s[N], d[N];

int find(int x)
{
    if (x == p[x])
        return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = root;
}

int main()
{
    for (int i = 1; i < N; ++i)
        p[i] = i, s[i] = 1;

    scanf("%d", &m);
    while (m--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M')
        {
            int pa = find(a), pb = find(b);
            if (pa != pb)
            {
                d[pa] = s[pb];
                s[pb] += s[pa];
                p[pa] = pb;
            }
        }
        else
        {
            int pa = find(a), pb = find(b);
            if (pa != pb)
                puts("-1");
            else
                printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }

    return 0;
}



烤肉
1天前
#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q;

//结论:WPL等于哈弗曼树上所有非叶结点权值之和

int main()
{
    cin >> n;
    while (n--)
    {
        int x; 
        cin >> x;
        q.push(x);
    }

    int res = 0;
    while (q.size() > 1)
    {
        auto a = q.top(); q.pop();
        auto b = q.top(); q.pop();
        res += a + b;
        q.push(a + b);
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 3531. 哈夫曼树

烤肉
1天前
#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q;

//结论:WPL等于哈弗曼树上所有非叶结点权值之和

int main()
{
    cin >> n;
    while (n--)
    {
        int x; 
        cin >> x;
        q.push(x);
    }

    int res = 0;
    while (q.size() > 1)
    {
        auto a = q.top(); q.pop();
        auto b = q.top(); q.pop();
        res += a + b;
        q.push(a + b);
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

烤肉
1天前
#include <iostream>
#include <unordered_map>

using namespace std;

//最多有1e5对关系,因此涉及2e5结点
const int N = 2e5 + 10;

struct Query
{
    int x, y, e;
};

int n, m, T;
int p[N];
unordered_map<int, int> h;
Query query[N];

int get(int x)
{
    if (!h.count(x))
        h[x] = ++n;
    return h[x];
}

int find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        n = 0;
        h.clear();
        scanf("%d", &m);
        for (int i = 0; i < m; ++i)
        {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            query[i] = {get(x), get(y), e};
        }

        for (int i = 1; i <= n; ++i)
            p[i] = i;

        for (int i = 0; i < m; ++i)
            if (query[i].e)
                p[find(query[i].x)] = find(query[i].y);

        bool has_conflict = false;
        for (int i = 0; i < m; ++i)
            if (!query[i].e)
            {
                int px = find(query[i].x), py = find(query[i].y);
                if (px == py)
                {
                    has_conflict = true;
                    break;
                }
            }

        if (has_conflict)
            puts("NO");
        else
            puts("YES");
    }

    return 0;
}



活动打卡代码 AcWing 1252. 搭配购买

烤肉
1天前
#include <iostream>
using namespace std;

const int N = 10010;

int n, m, vol;
int v[N], w[N];
int f[N], p[N];

int find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}

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

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        --a, --b;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            v[pa] += v[pb];
            w[pa] += w[pb];
            p[pb] = pa;
        }
    }

    for (int i = 0; i < n; ++i)
        if (p[i] == i)
            for (int j = vol; j >= v[i]; --j)
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[vol] << endl;
    return 0;
}