Chaos Slover 补档计划 - 哈夫曼树

2015.11.27 19:44 Fri| 4 visits oi_2016| ChaosSlover补档计划| Text

POJ1521&HDU1053 Entropy

裸题,用优先队列每次找两个出现次数最小的计入答案(合并果子)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int len, cnt[28], ans;
char str[200];
priority_queue<int> q;

int main()
{
    while (scanf("%s", str), strcmp(str, "END"))
    {
        memset(cnt, 0, sizeof cnt); ans = 0;
        while (!q.empty()) q.pop();
        cout << (len = strlen(str)) * 8 << ' ';
        for (int i = 0; i < len; ++i)
            if (str[i] == '_') ++cnt[0];
            else ++cnt[str[i] - 'A' + 1];
        for (int i = 0; i <= 26; ++i)
            if (cnt[i]) q.push(-cnt[i]);
        if (q.size() == 1) ans = len;
        while (q.size() >= 2)
        {
            int x = q.top(); q.pop();
            x += q.top(); q.pop(); q.push(x); ans -= x;
        }
        cout << ans << ' ';
        cout << fixed << setprecision(1) << (1.0 * len * 8 / ans) << endl;
    }
    return 0;
}

POJ1862 Stripies

从大到小合并……

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int n;
priority_queue<double> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        q.push(read());
    while (q.size() >= 2)
    {
        double x = q.top(); q.pop();
        x = 2 * sqrt(x * q.top()); q.pop(); q.push(x);
    }
    cout << fixed << setprecision(3) << q.top() << endl;
    return 0;
}

HDU2527 Safe Or Unsafe

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int test, cnt[30], ans;
char str[200];
priority_queue<int> q;

int main()
{
    cin >> test;
    while (test--)
    {
        memset(cnt, 0, sizeof cnt);
        while (!q.empty()) q.pop();
        cin >> ans;
        scanf("%s", str);
        for (int i = 0; str[i]; ++i)
            ++cnt[str[i] - 'a'];
        for (int i = 0; i < 26; ++i)
            if (cnt[i]) q.push(-cnt[i]);
        if (q.size() == 1) ans += q.top();
        while (q.size() >= 2)
        {
            int x = q.top(); q.pop();
            x += q.top(); q.pop(); q.push(x); ans += x;
        }
        if (ans < 0) puts("no");
        else puts("yes");
    }
    return 0;
}

POJ3253 Fence Repair

果然都是裸题,不想刷了……

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

int n;
long long ans;
priority_queue<long long> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        q.push(-read());
    if (q.size() == 1) ans += q.top();
    while (q.size() >= 2)
    {
        long long x = q.top(); q.pop();
        x += q.top(); q.pop(); q.push(x); ans -= x;
    }
    cout << ans << endl;
    return 0;
}

UVALive6533&UVA12676 Inverting Huffman

给出哈夫曼树上每一个叶子结点的深度,求构造出这棵哈夫曼树的字符串最小长度是多少。

首先最深的叶子上的权值一定要设为 1,然后深度为 i 的叶子结点的权值不能小于深度大于 i 的结点的权值。贪心搞一搞。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int n;
priority_queue<pair<long long, long long> > q;

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n)
    {
        for (int i = 1; i <= n; ++i)
            q.push(make_pair(read(), 0));
        long long maxval = -1;
        while (q.size() >= 2)
        {
            long long d = q.top().first - 1, t1 = q.top().second; q.pop();
            long long t2 = q.top().second; q.pop();
            if (t1 == 0) t1 = maxval;
            if (t2 == 0) t2 = maxval;
            maxval = min(maxval, min(t1, t2));
            q.push(make_pair(d, t1 + t2));
        }
        cout << -q.top().second << endl; q.pop();
    }
    return 0;
}

UVA10954 Add All

多组数据的合并果子……

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int n;
long long ans;
priority_queue<long long> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    while (cin >> n)
    {
        ans = 0;
        for (int i = 1; i <= n; ++i)
            q.push(-read());
        if (q.size() == 1) ans += q.top();
        while (q.size() >= 2)
        {
            long long x = q.top(); q.pop();
            x += q.top(); q.pop(); q.push(x); ans -= x;
        }
        cout << ans << endl; q.pop();
    }
    return 0;
}

HDU5350 MZL's munhaff function

还是合并果子。

这里可以看到原题解:http://blog.csdn.net/nike0good/article/details/47909809

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int test, n;
long long ans;
priority_queue<long long> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> test;
    while (test--)
    {
        ans = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            q.push(-read());
        while (q.size() >= 2)
        {
            long long x = q.top(); q.pop();
            x += q.top(); q.pop(); q.push(x); ans -= x;
        }
        cout << ans << endl; q.pop();
    }
    return 0;
}

BZOJ4198 [Noi2015]荷马史诗

国赛题。裸的多叉哈夫曼树(其实就是贪心啊)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

long long n, k, ans;
priority_queue<pair<long long, long long> > q;

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> k;
    for (long long i = 1; i <= n; ++i)
        q.push(make_pair(-read(), 1));
    while ((n - 1) % (k - 1))
        q.push(make_pair(0, 1)), ++n;
    while (q.size() >= 2)
    {
        pair<long long, long long> p;
        for (long long i = 1; i <= k; ++i)
            p.first += q.top().first,
            p.second = min(p.second, q.top().second), q.pop();
        ans -= p.first; --p.second; q.push(p);
    }
    cout << ans << '\n' << -q.top().second << endl;
    return 0;
}