霍夫曼树

#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

struct Node
{
    char c; int w; Node* l, * r;
    Node(char chr = 0, int weight = 0, Node* left = nullptr, Node* right = nullptr)
    {
        c = chr; w = weight; l = left; r = right;
    }
};

const int inf = ~(1 << 31);

Node* create(vector<vector<int>> dts)
{
    int n = dts.size();
    Node* F[n], * root;
    for (int i = 0; i < n; i ++)
    {
        F[i] = new Node{char(dts[i][0]), dts[i][1], nullptr, nullptr};
    }

    // 执行 n - 1 次
    for (int k = 1; k < n; k ++)
    {
        int m1, m2; m1 = m2 = inf; // m1 是最小值的下标，m2 是次最小值的下标

        // 先找到两个非空节点的下标
        for (int i = 0; i < n; i ++)
        {
            if (F[i] && m1 == inf)
            {
                m1 = i; continue;
            }
            else if (F[i]) 
            {
                m2 = i; break;
            }
        }

        // 确定两个最小值
        for (int i = m2; i < n; i ++)
        {
            if (F[i])
            {
                if (F[i]->w <= F[m1]->w)
                {
                    m2 = m1; m1 = i;
                }
                else if (F[i]->w < F[m2]->w)
                    m2 = i;
            }
        }

        root = new Node{0, F[m1]->w + F[m2]->w, F[m1], F[m2]};
        F[m1] = root; F[m2] = nullptr;
    }

    return root;
}

int get_wpl(Node* a, int h = 0)
{
    if (!a) return 0;
    if (!a->l && !a->r) return a->w * h;
    return get_wpl(a->l, h + 1) + get_wpl(a->r, h + 1);
}

const int N = int (1e7 + 10);
char s[N]; int cnt[26];
string hff[26];

void haff(Node* a, string path = string())
{
    if (!a) return;
    if (!a->l && !a->r)
    {
        hff[a->c - 'a'] = path; return;
    }
    haff(a->l, path + '0');
    haff(a->r, path + '1');
}

void solve(void)
{
    scanf ("%s", s);
    vector<vector<int>> dts;
    for (int i = 0; s[i]; i ++) cnt[s[i] - 'a'] ++;
    for (int i = 0; i < 26; i ++) dts.push_back({i + 'a', cnt[i]});
    Node* a = create(dts);
    haff(a);
    for (int i = 0; i < 26; i ++)
        cout << char(i + 'a') << " : " << hff[i] << endl;
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;
#define endl '\n'
#define pique priority_queue
#define oier \
            ios_base::sync_with_stdio(false);\
            cin.tie(nullptr); cout.tie(nullptr);

#define cf int t; cin >> t; while (t --)

#define upfor(i, l, r) for (i = (l); i <= (r); i ++)
#define downfor(i, l, r) for (i = (r); i >= (l); i --)

// #define int long long
typedef long long LL;
typedef long double LD;
//typedef __int128_t int128;

const int inf = ~(1 << 31);  // 正无穷
const int ninf = (1 << 31);  // 负无穷

const LL infll = ~(1ll << 63); // 正无穷
const LL ninfll = (1ll << 63); // 负无穷

inline LL rll() { oier LL x; cin >> x; return x; }
inline int rint() { oier int x; cin >> x; return x; }

/*
    0b00111111 = 0x3f
    0b01111111 = 0x7f
    0b11111111 = -1
*/

int gdb = 0;

const int N = int (1e7 + 10);

// 由于情报不足，只能透过「试行错误」来获取。

/* =============================代码区============================= */

int sums[N];

struct Tree
{
    char a; int b; Tree * l, * r;
};

struct Node
{
    Tree* t;
    Node(Tree* a = nullptr) { t = a; }
    bool operator<(const Node& a) const { return t->b > a.t->b; }
};

typedef priority_queue<Node> pq;

struct Qnode
{
    char a; string s;
    bool operator<(const Qnode& t) const { return a > t.a; }
};

typedef priority_queue<Qnode> sq;

void solve()
{   oier
    /* =========================== */

    string s; cin >> s; for (auto x : s) sums[x - 'a'] ++;

    pq q; 
    for (int i = 0; i < 26; i ++)
    {
        if (sums[i]) q.push(Node(new Tree{i + 'a', sums[i], nullptr, nullptr}));
    }

    while (q.size() > 1)
    {
        Node a = q.top(); q.pop();
        Node b = q.top(); q.pop();
        Node c = Node(new Tree{0, a.t->b + b.t->b, a.t, b.t});
        q.push(c);
    }

    stack<pair<Tree*, string>> st;
    st.push({q.top().t, string()});

    sq res;
    while (st.size())
    {
        auto [x, y] = st.top(); st.pop();
        if (!x->l && !x->r) 
        { 
            // cout << x->a << " : " << x->b << " : " << y << endl;
            // cout << x->a << " : " << y << endl; 
            res.push({x->a, y});
            continue; 
        }
        st.push({x->l, y + '0'});
        st.push({x->r, y + '1'});
    }

    while (res.size())
    {
        auto t = res.top(); res.pop();
        cout << t.a << " : " << t.s << endl;
    }

    /* =========================== */
}

/* =============================代码区============================= */

/**
*                             _ooOoo_
*                            o8888888o
*                            88" . "88
*                            (| -_- |)
*                            O\  =  /O
*                         ____/`---'\____
*                       .'  \\|     |//  `.
*                      /  \\|||  :  |||//  \
*                     /  _||||| -:- |||||-  \
*                     |   | \\\  -  /// |   |
*                     | \_|  ''\---/''  |   |
*                     \  .-\__  `-`  ___/-. /
*                   ___`. .'  /--.--\  `. . __
*                ."" '<  `.___\_<|>_/___.'  >'"".
*               | | :  `- \`.;`\ _ /`;.`/ - ` : | |
*               \  \ `-.   \_ __\ /__ _/   .-` /  /
*          ======`-.____`-.___\_____/___.-`____.-'======
*                             `=---='
*          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*                     佛祖保佑        永无BUG
*            佛曰:
*                   写字楼里写字间，写字间里程序员；
*                   程序人员写程序，又拿程序换酒钱。
*                   酒醒只在网上坐，酒醉还来网下眠；
*                   酒醉酒醒日复日，网上网下年复年。
*                   但愿老死电脑间，不愿鞠躬老板前；
*                   奔驰宝马贵者趣，公交自行程序员。
*                   别人笑我忒疯癫，我笑自己命太贱；
*                   不见满街漂亮妹，哪个归得程序员？
**/

/* ========================佛祖保佑, 永无bug======================== */

int main()
{
    // oier cf solve(); return 0;
    oier solve(); return 0;
}

struct Node
{
    int w; Node* l, * r;
    Node(int weight = 0, Node* left = nullptr, Node* right = nullptr)
    {
        w = weight; l = left; r = right;
    }
};

const int inf = ~(1 << 31);

Node* init(const vector<int>& nums)
{
    int n = nums.size();
    Node* F[nums.size() + 1];
    for (int i = 1; i <= nums.size(); i ++)
        F[i] = new Node(nums[i - 1]);

    Node* root;
    // 两两合并，要合并 n - 1 次
    for (int a = 1; a < n; a ++)
    {
        // min1 是最小值的下标，min2 是次最小值的下标
        int min1, min2; min1 = min2 = inf;

        // 先找到不为 「空」 的两个节点
        for (int i = 1; i <= n; i ++)
        {
            if (F[i] && min1 == inf)
            {
                min1 = i; continue;
            }
            else if (F[i])
            {
                min2 = i; break;
            }
        }

        // 寻找最小值，寻找最大值
        for (int i = min2; i <= n; i ++)
        {
            if (F[i])
            {
                if (F[i]->w <= F[min1]->w) 
                {
                    min2 = min1; min1 = i;
                }
                else if (F[i]->w <= F[min2]->w)
                    min2 = i;
            }
        }

        // 建立新树
        root = new Node(F[min1]->w + F[min2]->w, F[min1], F[min2]);
        F[min1] = root;
        F[min2] = nullptr;
    }

    return root;
}

int get_wpl(Node* a, int h = 0)
{
    if (a == nullptr) return 0;
    if (!a->l && !a->r) return a->w * h;
    return get_wpl(a->l, h + 1) + get_wpl(a->r, h + 1);
}