知新_RL

这个屌丝很懒，什么也没留下！

热门标签

BUCTOJ - 2023上半年ACM&蓝桥杯每周训练题-1-A~K题C++Python双语版_神秘电报密码-哈夫曼编码1 6 a 0.05 b 0.32 c 0.18 d 0.07 e 0.25

作者：知新_RL | 2024-05-23 16:10:12

踩

神秘电报密码-哈夫曼编码1 6 a 0.05 b 0.32 c 0.18 d 0.07 e 0.25 f 0.13

文章目录

BUCTOJ - 2023上半年ACM&蓝桥杯每周训练题-1-A~K题C++Python双语版
前言
The End

BUCTOJ - 2023上半年ACM&蓝桥杯每周训练题-1-A~K题C++Python双语版

知识点：题解, BUCTOJ, 中等, 数组, 递归, 动态规划, 循环, 模拟, 素数, 质数, 贪心, 排序, 图论, 图, 迪杰斯特拉, Dijstra, 树, 哈夫曼树, 最小生成树, 归并排序

前言

这篇题解写包含《2023上半年ACM&蓝桥杯每周训练题-1》的A~K题的解析以及C++和Python双版本代码

蒟蒻的我为了《问题 H: 2.5 一场说走就走的旅行》还心血来潮地做了个无人问津的视频，也耽误了不少时间，导致题解现在才完成至这个模样。

PDF不能播放视频，且一段代码可能会分页显示，因此还是比较推荐在网页端看题解的。地址：https://leetcode.letmefly.xyz/2023/02/21/BUCT-BUCT2023LanQiaoWeekly1

若想查找某一知识点，可以直接Ctrl + F。

问题 A: 1.2 神奇兔子数列

题目地址

知识点：数组，递归，动态规划

题目描述

假设第 1 个月有 1 对刚诞生的兔子，第 2 个月进入成熟期，第 3 个月开始生育兔子，而1 对成熟的兔子每月会生 1 对兔子，兔子永不死去……那么，由 1 对初生兔子开始，12 个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci，1170—1250）。1202 年，他撰写了《算盘全书（《Liber Abaci》）一书，该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数，并研究了一些简单的一次同余式组。

输入

无

输出

一个整数（12个月后有多少对兔子）

解题思路

这道题就是要求斐波那契数列的第12项

在计算斐波那契数列的过程中，我们只需要关注连续的3项。

使用两个变量_1和_2代表已经计算出的第一项和第二项，那么要计算出的第三项_3就等于 $_1 + _2$

如此往复，更新第一项和第二项为原来的第二项和第三项，就能不断求出新的第三项。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

int main() {
    ll _1 = 1, _2 = 1, _3;
    for (int i = 3; i <= 12; i++) {
        _3 = _1 + _2;
        _1 = _2, _2 = _3;
    }
    cout << _3 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Python

_1, _2, _3 = 1, 1, ''
for i in range(3, 13):
    _3 = _1 + _2
    _1, _2 = _2, _3
print(_3)
1
2
3
4
5

问题 B: 1.3 马克思手稿中的数学题

题目地址

知识点：循环，模拟

题目描述

马克思手稿中有一道趣味数学问题：有 30 个人，其中有男人、女人和小孩，这些人在一家饭馆吃饭花了 50 先令；每个男人花 3 先令，每个女人花 2 先令，每个小孩花 1 先令；问男人、女人和小孩各有几人？

输入

无

输出

输出所有可能的解
每行三个整数x，y，z（用空格隔开，x代表男人，y代表女人，z代表小孩，按x升序排列）：
x y z

解题思路

数据量并不大，我们暴力枚举0到30范围内的所有x、y、z即可。

注意题目中说“其中有男人、女人和小孩”，也就是说每种人都有，不能为0。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

int main() {
    fi (x, 1, 31) {
        fi (y, 1, 31) {
            fi (z, 1, 31) {
                if (x + y + z == 30 && 3 * x + 2 * y + z == 50) {
                    cout << x << ' ' << y << ' ' << z << endl;
                }
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Python

for x in range(1, 31):
    for y in range(1, 31):
        for z in range(1, 31):
            if  x + y + z == 30 and 3 * x + 2 * y + z == 50:
                print(x, y, z)
1
2
3
4
5

问题 C: 1.4 爱因斯坦的阶梯

题目地址

知识点：模拟

题目描述

爱因斯坦家里有一条长阶梯，若每步跨 2 阶，则最后剩 1 阶；若每步跨 3 阶，则最后剩 2 阶；若每步跨 5 阶，则最后剩 4 阶；若每步跨 6 阶，则最后剩 5 阶。只有每次跨 7 阶，最后才正好 1 阶不剩。请问这条阶梯共有多少阶？

输入

无

输出

满足题目的最小整数

解题思路

从1开始往上模拟即可

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

int main() {
    int ans = 1;
    while (true) {
        if (ans % 2 == 1 && ans % 3 == 2 && ans % 5 == 4 && ans % 6 == 5 && ans % 7 == 0) {
            cout << ans << endl;
            break;
        }
        ans++;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Python

ans = 1
while True:
    if ans % 2 == 1 and ans % 3 == 2 and ans % 5 == 4 and ans % 6 == 5 and ans % 7 == 0:
        print(ans)
        break
    ans += 1
1
2
3
4
5
6

问题 D: 1.5 哥德巴赫猜想

题目地址

知识点：模拟、素数/质数

题目描述

哥德巴赫猜想：任一大于 2 的偶数，都可表示成两个素数之和。
验证：2000 以内大于 2 的偶数都能够分解为两个素数之和。

输入

无

输出

2000 以内大于 2 的偶数被分解的两个素数
按升序排列，第一个素数为最小值
4=2+2
6=3+3
8=3+5
10=3+7
12=5+7
14=3+11
16=3+13

......
1
2
3
4
5
6
7
8
9
10
11

解题思路

题目数据范围不大，我们可以先求出2000以内的素数并放入数组和哈希表中，接着对于某个偶数，从最小的素数开始尝试，快速得到 $偶数 - 这个素数$ 是否也为素数。若是则输出，否则尝试大一点的素数。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

bool isPrime(int n) {
    int k = sqrt(n);
    for (int i = 2; i <= k; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<int> prime;
    unordered_set<int> se;
    for (int i = 2; i <= 2000; i++) {
        if (isPrime(i)) {
            prime.push_back(i);
            se.insert(i);
        }
    }

    for (int i = 4; i <= 2000; i += 2) {
        for (int t : prime) {
            if (se.count(i - t)) {
                printf("%d=%d+%d\n", i, t, i - t);
                break;
            }
        }
    }
    return 0;
}
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
35
36
37
38

Python

from math import sqrt


def isPrime(n):
    k = int(sqrt(n))
    for i in range(2, k + 1):
        if n % i == 0:
            return False
    return True


prime = []
se = set()

for i in range(2, 2001):
    if isPrime(i):
        prime.append(i)
        se.add(i)

for i in range(4, 2001, 2):
    for t in prime:
        if i - t in se:
            print(f"{i}={t}+{i-t}")
            break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

问题 E: 2.2 加勒比海盗船

题目地址

知识点：贪心

题目描述

   在北美洲东南部，有一片神秘的海域，那里碧海蓝天、阳光明媚，这正是传说中海盗最活跃的加勒比海（Caribbean Sea）。17 世纪时，这里更是欧洲大陆的商旅舰队到达美洲的必经之地，所以当时的海盗活动非常猖獗，海盗不仅攻击过往商人，甚至攻击英国皇家舰……
   有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为 C，每件古董的重量为 wi，海盗们该如何把尽可能多数量的宝贝装上海盗船呢？
1
2

输入

请输入问题的组数 m：
m ( 0 < m < 100 )
请输入载重量 c 及古董个数 n：
c n (0 < c, n < 10000)
请输入每个古董的重量，用空格分开：
w1 w2 w3 ... wn  (0 < wi < 100)
1
2
3
4
5
6

输出

能装入的古董最大数量为:
ans

输入样例

1
30 8
4 10 7 11 3 5 14 2
1
2
3

输出样例

5
1

解题思路

装载数量优先，那必是先装重量小的。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

int a[10010];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int m, n;
        cin >> m >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        int ans = 0;
        while (m > 0 && ans < n) {
            if (m >= a[ans]) {
                m -= a[ans++];
            }
            else {
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
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

Python

T = int(input())
for _ in range(T):
    m, n = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    while m > 0 and ans < n:
        if m >= a[ans]:
            m -= a[ans]
            ans += 1
        else:
            break
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13

问题 F: 2.3 阿里巴巴与四十大盗

题目地址

知识点：贪心

题目描述

   有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着直向上空飞扬，朝他这儿卷过来，而且越来越近。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋，从丛林中一直来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴待在树上观察他们，直到他们走得无影无踪之后，才从树上下来。他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。
   他小心翼翼地走了进去，一下子惊呆了，洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金银财富，阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用驴子运走最大价值的财宝分给穷人呢？阿里巴巴陷入沉思中……
1
2

输入

样例的组数 t
t ( 0 < t < 100 )
宝物数量m和驴子的承载重量 n
m  n ( 0 < m, n < 10000 )
第i个宝物的重量和价值 ( 0 < wi, vi < 100 )

w1  v1  
w2  v2
...
wm  vm
1
2
3
4
5
6
7
8
9
10

输出

装入宝物的最大价值

输入样例

输出样例

24.6
1

解题思路

注意题目描述了吗？“如果太重就用锤子凿开”。好家伙，凿开还是宝物的话，那就看哪个宝物的“含金密度”大呗！

接下来我们给每个宝物评分，评分规则是宝物的“密度”（ $\frac{重量}{体积}$ ）

需要注意的是，这道题数据有误，数据中存在重量为0的宝物，也就是说其分数（密度）无限大。注意这时候不能用“重量 * 分数”来计算其总价值了。

还需要注意的是，题目中没有说明输出格式。经测试得知当答案为整数时输出0位小数，答案非整数时输出一些位的小数，完美贴合C++的cout。

还需要注意的是，题目中没有说明多组输入的格式，样例中的多组输入数据之间是有一个空行的，Python选手需要注意

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

struct Treasure {
    int w, v;
    double score;
} a[10010];

bool cmp(Treasure& a, Treasure& b) {
    return a.score > b.score;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int m, n;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &a[i].w, &a[i].v);
            a[i].score = 1. * a[i].v / a[i].w;
        }
        sort(a, a + n, cmp);
        double v = 0;
        double w = m;
        int th = 0;
        while (w > 0 && th < n) {
            if (!a[th].w) {
                v += a[th++].v;
                continue;
            }
            int thisW = min((double)a[th].w, w);
            v += thisW * a[th].score;
            w -= thisW;
            th++;
        }
        cout << v << endl;
    }
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45

Python

Python提交上去会超时。。。

class Treasure:
    def __init__(self, v, w) -> None:
        self.v = v
        self.w = w
        self.score = v / w if w else 100000000


T = int(input())
for _ in range(T):
    while True:
        thisLine = input()
        if thisLine:
            break
    n, m = map(int, thisLine.split())
    a = []
    for __ in range(n):
        w, v = map(int, input().split())
        a.append(Treasure(v, w))
    a.sort(key=lambda x: -x.score)
    v = 0
    w = m
    th = 0
    while w > 0 and th < n:
        # print('*' * 50)
        if not a[th].w:
            v += a[th].v
            th += 1
            continue
        thisW = min(w, a[th].w)
        v += thisW * a[th].score
        w -= thisW
        th += 1
    if int(v) == v:
        print(int(v))
    else:
        print("{:.1f}".format(v))
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
35
36

问题 G: 2.4 高级钟点秘书

题目地址

知识点：排序、贪心

题目描述

所谓“钟点秘书”，是指年轻白领女性利用工余时间为客户提供秘书服务，并按钟点收取酬金。“钟点秘书”为客户提供有偿服务的方式一般是：采用电话、电传、上网等“遥控”式服务，或亲自到客户公司处理部分业务。其服务对象主要有三类：一是外地前来考察商务经营、项目投资的商人或政要人员，他们由于初来乍到，急需有经验和熟悉本地情况的秘书帮忙；二是前来开展短暂商务活动，或召开小型资讯发布会的国外客商；三是本地一些请不起长期秘书的企、事业单位。这些客户普遍认为：请“钟点秘书”，一则可免去专门租楼请人的大笔开销；二则可根据开展的商务活动请有某方面专长的可用人才；三则由于对方是临时雇用关系，工作效率往往比固定的秘书更高。据调查，在上海“钟点秘书”的行情日趋看好。对此，业内人士认为：为了便于管理，各大城市有必要组建若干家“钟点秘书服务公司”，通过会员制的形式，为众多客户提供规范、优良、全面的服务，这也是建设国际化大都市所必需的。
某跨国公司总裁正分身无术，为一大堆会议时间表焦头烂额，希望高级钟点秘书能做出合理的安排，能在有限的时间内召开更多的会议。
1
2

输入

输入样例组数：
t ( 0 < t < 10 )
输入会议总数：
n ( 0 < n < 10000)
输入会议的开始时间和结束时间，以空格分开： ( 0 < bi, ei < 50 )
b1  e1
b2  e2
...
bn  en
1
2
3
4
5
6
7
8
9

输出

最多可以安排的会议数目m

输入样例

输出样例

4
1

解题思路

对所有的会议排序，排序规则是：结束早的会议优先靠前。

这样，我们只需要从前到后遍历所有的会议，如果某个会议的开始时间不早于“秘书最后参会”的结束时间，那么就参加这个会议。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
typedef pair<int, int> pii;
pii a[10010];

bool cmp(pii& a, pii& b) {
    return a.second < b.second;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &a[i].first, &a[i].second);
        }
        sort(a, a + n, cmp);
        int lastEnd = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i].first >= lastEnd) {
                ans++;
                lastEnd = a[i].second;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
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
35
36

Python

T = int(input())
for _ in range(T):
    thisLine = ''
    while not thisLine:
        thisLine = input()
    n = int(thisLine)
    a = []
    for __ in range(n):
        thisInput = input().split()
        a.append((int(thisInput[0]), int(thisInput[1])))
    # print(a)
    a.sort(key=lambda x: x[1])
    lastEnd = 0
    ans = 0
    for p in a:
        if p[0] >= lastEnd:
            ans += 1
            lastEnd = p[1]
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

问题 H: 2.5 一场说走就走的旅行

题目地址

知识点：图论/图，Dijstra算法/迪杰斯特拉算法

题目描述

有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”
马尔代夫？我也想去！没有人不向往一场说走就走的旅行！
“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。
于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
“哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太 out 了，学计算机的最短路线你用手算？”
暴汗……，“小子你别牛，你知道怎么算？”
“呃，好像是叫什么迪科斯彻的人会算。”
哈哈，关键时刻还要老妈上场了！
1
2
3
4
5
6
7
8

输入

样例组数：
t ( 0 < t <= 10 )
城市的个数：
n ( 0 < n < 100 )
城市之间的路线的个数：
m ( 0 < m < 10000 )
请输入城市之间的路线以及距离：
( 0 < ui, vi, di <= 100 )
u1 v1 d1
u2 v2 d2
...
ui vi di
请输入小明所在的位置：
l ( 0 < l < 100 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出

小明到各个城市的最短距离;
l1 l2 ... ln (若某城市无法达到则输出impossible）
1
2

输入样例

输出样例

8 24 23 30 0
1

解题思路

这道题是典型的单源起点最短路径的Dijstra算法。

这里不得不提一提我的班主任彭老师，他的数据结构PPT做得特别好。其中图论PPT地址为：https://github.com/TeacherPeng/Datastruct/blob/master/教案/第07章图.pptx，此算法在75页。（05064f61c0b16a8764e7d63ae2bfef0b2dd04798版本）

注意，这道题是单向边，AC代码中是按单向边处理的。

Dijstra单源起点最短路径算法的思路是，从起点开始，遍历所有的起点能到达的点中，路径最短的一条。

接着将“路径最短的一条路径”所到达的点标记为“已算出”，再更新从这个点出发的所有的路径所能到达的顶点中，距离起点的最近距离（原始距离或起点到刚刚算出的点的距离+刚刚点的距离到这个点的距离）。

直到起点到所有点的最短距离都计算出来为止。

AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
typedef pair<int, int> pii;
#define INF 1e9

int shortest[111];
vector<pii> graph[111];
bool visited[111];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        // init
        for (int i = 1; i <= n; i++) {
            shortest[i] = INF;
            visited[i] = false;
            graph[i].clear();
        }
        // cin
        for (int i = 0; i < m; i++) {
            int u, v, d;
            scanf("%d%d%d", &u, &v, &d);
            graph[u].push_back({v, d});
        }
        int start;
        cin >> start;
        // begin
        shortest[start] = 0;
        for (int i = 0; i < n; i++) {  // 第一次求出start到start的最短距离
            int thisMinDistance = INF;
            int shortestPoint = -1;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && shortest[j] < thisMinDistance) {
                    thisMinDistance = shortest[j];
                    shortestPoint = j;
                }
            }
            if (shortestPoint == -1) {  // 节点可达
                break;
            }
            visited[shortestPoint] = true;
            for (auto[toPoint, distance] : graph[shortestPoint]) {
                shortest[toPoint] = min(shortest[toPoint], shortest[shortestPoint] + distance);
            }
        }
        // cout
        for (int i = 1; i <= n; i++) {
            if (shortest[i] == INF) {
                printf("impossible ");
            }
            else {
                printf("%d ", shortest[i]);
            }
        }
    }
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

Python

T = int(input())
for __CASE in range(T):
    n, m = map(int, input().split())
    # init
    visited = [False for _ in range(n + 1)]
    graph = [[] for _ in range(n + 1)]
    shortestDistance = [1e9 for _ in range(n + 1)]
    # cin
    for _ in range(m):
        u, v, d = map(int, input().split())
        graph[u].append((v, d))
    start = int(input())
    # begin
    shortestDistance[start] = 0
    for _ in range(n):
        thisMinDistance = 1e9
        shortestPoint = -1
        for j in range(1, n + 1):
            if not visited[j] and shortestDistance[j] < thisMinDistance:
                thisMinDistance = shortestDistance[j]
                shortestPoint = j
        if shortestPoint == -1:
            break
        visited[shortestPoint] = True
        for toPoint, thisDistance in graph[shortestPoint]:
            shortestDistance[toPoint] = min(shortestDistance[toPoint], shortestDistance[shortestPoint] + thisDistance)
    # cout
    for i in range(1, n + 1):
        if shortestDistance[i] == 1e9:
            print("impossible", end=' ')
        else:
            print(shortestDistance[i], end=' ')
    print()
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

我做了个讲解Dijstra算法的视频，快去看看吧！https://www.bilibili.com/video/BV1Y84y1N7Lm

单源最短路的Dijstra算法

问题 I: 2.6 神秘电报密码

题目地址

知识点：树、哈夫曼树

题目描述

看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已！吴志国大队长在受了残忍的“针刑”之后躺在手术台上唱空城计，变了音调，把消息传给了护士，顾晓梦在 衣服上缝补了长短不一的针脚……那么，片中无处不在的摩尔斯码到底是什么？它又有着怎
样的神秘力量呢？
摩尔斯电码（Morse code）由点 dot（. ）、划 dash（-）两种符号组成。它的基本原理是：
把英文字母表中的字母、标点符号和空格按照出现的频率排序，然后用点和划的组合来代表这些字母、标点符号和空格，使频率最高的符号具有最短的点划组合。
1
2
3
4

输入

输入样例组数：
t ( 0 < t < 10 )
输入节点数目：
n ( 0 < n < 30 )
输入节点的名称和值：
( x 为字母， 0 <= v < 1 )
x1 v1
x2 v2

...
xi vi
1
2
3
4
5
6
7
8
9
10
11

输出

输出每一个节点的哈夫曼编码：( 注：不同节点间用空格隔开，每个节点内冒号后用空格隔开）
x: y
1
2

输入样例

输出样例

a: 1000 b: 11 c: 00 d: 1001 e: 01 f: 101
1

解题思路

哈夫曼编码的核心思想是“权重越小的距离根越远”

构建哈夫曼树时，在节点数量大于1时，每次选取权重最小的两个节点，合并为一个节点（权重累加）

最终剩下一个节点，哈夫曼树就构建完成了。

确定字符的编码时，从根节点开始往叶节点遍历。在遍历的过程中，若是往左子树遍历，则编码记为0，否则记为1。

Not AC代码

C++

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

struct Node {
    char c;
    bool isLeaf;
    Node *leftChild, *rightChild;
    double weight;
};

struct cmp {
    bool operator() (Node* a, Node* b) {
        return a->weight > b->weight;  // 权重小的在前
    }
};

void output(Node* root, string nowString, unordered_map<char, string>& output2where) {
    if (root->isLeaf) {
        output2where[root->c] = nowString;
        return;
    }
    // not leaf
    if (root->leftChild) {
        output(root->leftChild, nowString + '0', output2where);
    }
    if (root->rightChild) {
        output(root->rightChild, nowString + '1', output2where);
    }
}

void destroyTree(Node* root) {
    if (root->isLeaf) {
        delete root;
        return;
    }
    if (root->leftChild) {
        destroyTree(root->leftChild);
    }
    if (root->rightChild) {
        destroyTree(root->rightChild);
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        priority_queue<Node*, vector<Node*>, cmp> pq;
        vector<char> charOrder;
        unordered_map<char, string> ans;
        // input
        for (int i = 0; i < n; i++) {
            char c;
            double weight;
            cin >> c >> weight;
            charOrder.push_back(c);
            Node* thisNode = new Node;
            thisNode->c = c;
            thisNode->isLeaf = true;
            thisNode->weight = weight;
            pq.push(thisNode);
        }
        // build
        while (pq.size() > 1) {
            Node* leftNode = pq.top();
            pq.pop();
            Node* rightNode = pq.top();
            pq.pop();
            Node* newNode = new Node;
            newNode->isLeaf = false;
            newNode->weight = leftNode->weight + rightNode->weight;
            newNode->leftChild = leftNode, newNode->rightChild = rightNode;
            pq.push(newNode);
            // printf("[%lf + %lf]\n", leftNode->weight, rightNode->weight);
        }
        Node* root;
        if (pq.top()->isLeaf) {
            root = new Node;
            root->leftChild = pq.top();
            root->rightChild = nullptr;
            root->isLeaf = false;
            root->weight = pq.top()->weight;
        }
        else {
            root = pq.top();
        }
        // output
        output(root, "", ans);
        for (char c : charOrder) {
            cout << c << ": " << ans[c] << ' ';
        }
        puts("");
        // end
        destroyTree(root);
    }
    return 0;
}

/*
1
6 
a 0.05 
b 0.32 
c 0.18 
d 0.07 
e 0.25 
f 0.13

a: 1000 b: 11 c: 00 d: 1001 e: 01 f: 101
*/

/*
6
19
b 0.28
c 0.57
d 0.05
e 0.02
f 0.04
g 0.02
h 0.01
i 0.01
j 0.00
k 0.00
l 0.00
m 0.00
n 0.00
o 0.00
p 0.00
q 0.00
r 0.00
s 0.00
t 0.00
16
b 0.33
c 0.07
d 0.44
e 0.14
f 0.02
g 0.00
h 0.00
i 0.00
j 0.00
k 0.00
l 0.00
m 0.00
n 0.00
o 0.00
p 0.00
q 0.00
14
b 0.39
c 0.55
d 0.02
e 0.04
f 0.00
g 0.00
h 0.00
i 0.00
j 0.00
k 0.00
l 0.00
m 0.00
n 0.00
o 0.00
14
b 0.10
c 0.69
d 0.10
e 0.11
f 0.00
g 0.00
h 0.00
i 0.00
j 0.00
k 0.00
l 0.00
m 0.00
n 0.00
o 0.00
7
b 0.85
c 0.08
d 0.03
e 0.01
f 0.03
g 0.00
h 0.00
12
b 0.15
c 0.06
d 0.60
e 0.05
f 0.13
g 0.01
h 0.00
i 0.00
j 0.00
k 0.00
l 0.00
m 0.00

b: 01 c: 1 d: 0011 e: 00100 f: 0001 g: 00101 h: 000011 i: 00000 j: 0000101010 k: 0000101011 l: 0000101100 m: 0000101101 n: 0000101110 o: 0000101111 p: 000010000 q: 000010001 r: 000010010 s: 000010011 t: 000010100
b: 11 c: 1001 d: 0 e: 101 f: 10001 g: 100001010 h: 100001011 i: 100001100 j: 100001101 k: 100001110 l: 100001111 m: 10000000 n: 10000001 o: 10000010 p: 10000011 q: 10000100
b: 01 c: 1 d: 0001 e: 001 f: 00001100 g: 00001101 h: 00001110 i: 00001111 j: 0000000 k: 0000001 l: 0000010 m: 0000011 n: 0000100 o: 0000101
b: 0111 c: 1 d: 010 e: 00 f: 01101100 g: 01101101 h: 01101110 i: 01101111 j: 0110000 k: 0110001 l: 0110010 m: 0110011 n: 0110100 o: 0110101
b: 1 c: 01 d: 0011 e: 00101 f: 000 g: 001000 h: 001001
b: 00 c: 0100 d: 1 e: 01011 f: 011 g: 010101 h: 010100100 i: 010100101 j: 010100110 k: 010100111 l: 01010000 m: 01010001
*/
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216

上述代码我不认为它是错误的，但是它不能通过本题。

因为题目给定的数据中，有很多权重相同的节点。题目中未规定这些节点的编码顺序。因此答案不唯一，但本题无特判。

我的上述代码使用的是“C++的优先队列”，本质上是堆。这样在获取“weight最低的两个节点”时效率较高。而题目的作者应该是遍历所有节点来获取的。因此答案不同。

Python

class Node:
    c = ''
    isLeaf = False
    leftChild, rightChild = '', ''
    weight = 0

ans = dict()

def output(root: Node, nowString: str):
    if root.isLeaf:
        ans[root.c] = nowString
        return
    if root.leftChild:
        output(root.leftChild, nowString + '0')
    if root.rightChild:
        output(root.rightChild, nowString + '1')

T = int(input())
for _CASE in range(T):
    n = int(input())
    charOrder = []
    ans.clear()
    Nodes = []
    # input
    for _ in range(n):
        c, weight = input().split()
        weight = float(weight)
        charOrder.append(c)
        thisNode = Node()
        thisNode.c = c
        thisNode.weight = weight
        thisNode.isLeaf = True
        Nodes.append(thisNode)
    # build
    while len(Nodes) > 1:
        Nodes.sort(key=lambda x : x.weight)
        leftNode, rightNode = Nodes[0], Nodes[1]
        Nodes = Nodes[2:]
        newNode = Node()
        newNode.isLeaf = False
        newNode.weight = leftNode.weight + rightNode.weight
        newNode.leftChild = leftNode
        newNode.rightChild = rightNode
        Nodes.append(newNode)
    root = ''
    if Nodes[0].isLeaf:
        root = Node()
        root.isLeaf = False
        root.leftChild = Nodes[0]
        root.rightChild = ''
        root.weight = Nodes[0].weight
    else:
        root = Nodes[0]
    # output
    output(root, '')
    for c in charOrder:
        print(f"{c}: {ans[c]} ", end='')
    print()
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

在Python版本的代码中，我没有使用优先队列，而是采用了排序的方式，恰好和答案编码相同。

以下是我对本题如何Special judge的一点思路：

首先判断用户答案的合法性：

不同节点路径不同
一个节点的路径不会为另一个节点的子路径

接着判断用户答案的“压缩程度”：

$\sum len(code_i)\times freq(char_i)$

简言之就是字符编码的长度×字符出现频率之和。

如果“压缩程度”和标准答案相同，则视为用户的答案是正确的
如果“压缩程度”大于标准答案，则说明用户的答案不是最优解
如果“压缩程度”小于标准答案，则说明标准答案错误，标准答案不是最优解

问题 J: 2.7 沟通无限校园网

题目地址

知识点：图论/图、最小生成树

题目描述

校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以形成多个局域网络，并通过有线或无线方式连接起来。

原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部，这些情况严重地阻碍了整个学校的网络化需求。现在需要设计网络电缆布线，将各个单位的局域网络连通起来，如何设计能够使费用最少呢？

输入

输入样例组数：
t ( 0 < t < 10 )
输入结点数和边数：
n m ( 0 < n < 100 , 0 < m < 10000 )
输入结点数u，v和边值 w： ( 0 < w < 100 )
u1 v1 w1
u2 v2 w2
...
ui vi wi
1
2
3
4
5
6
7
8
9

输出

最小的花费 ans

输入样例

输出样例

57
1

解题思路

写在前面： 这道题没有说：“当给定图为非连通图时，输出0”。。。。。。

还有： 样例最后一行多出来的那个1是什么鬼

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/613547