海南中小企业网站建设,搜房网站要怎么 做,电子商务网站建设精英,wordpress迁移网站文章目录BUCTOJ - 2023上半年ACM蓝桥杯每周训练题-1-A~K题CPython双语版前言问题 A: 1.2 神奇兔子数列题目描述输入输出解题思路AC代码CPython问题 B: 1.3 马克思手稿中的数学题题目描述输入输出解题思路AC代码CPython问题 C: 1.4 爱因斯坦的阶梯题目描述输入输出解题思路…
文章目录BUCTOJ - 2023上半年ACM蓝桥杯每周训练题-1-A~K题CPython双语版前言问题 A: 1.2 神奇兔子数列题目描述输入输出解题思路AC代码CPython问题 B: 1.3 马克思手稿中的数学题题目描述输入输出解题思路AC代码CPython问题 C: 1.4 爱因斯坦的阶梯题目描述输入输出解题思路AC代码CPython问题 D: 1.5 哥德巴赫猜想题目描述输入输出解题思路AC代码CPython问题 E: 2.2 加勒比海盗船题目描述输入输出输入样例输出样例解题思路AC代码CPython问题 F: 2.3 阿里巴巴与四十大盗题目描述输入输出输入样例输出样例解题思路AC代码CPython问题 G: 2.4 高级钟点秘书题目描述输入输出输入样例输出样例解题思路AC代码CPython问题 H: 2.5 一场说走就走的旅行题目描述输入输出输入样例输出样例解题思路AC代码CPython问题 I: 2.6 神秘电报密码题目描述输入输出输入样例输出样例解题思路Not AC代码CPython问题 J: 2.7 沟通无限校园网题目描述输入输出输入样例输出样例解题思路AC代码CPython问题 K: 3.3 合久必分分久必合题目描述输入输出输入样例输出样例解题思路AC代码CPythonThe EndBUCTOJ - 2023上半年ACM蓝桥杯每周训练题-1-A~K题CPython双语版
前言
这篇题解写包含《2023上半年ACM蓝桥杯每周训练题-1》的A~K题的解析以及C和Python双版本代码
蒟蒻的我为了《问题 H: 2.5 一场说走就走的旅行》还心血来潮地做了个无人问津的视频也耽误了不少时间导致题解现在才完成至这个模样。
PDF不能播放视频还是比较推荐在网页端看题解的。地址https://leetcode.letmefly.xyz/2023/02/21/BUCT-BUCT2023LanQiaoWeekly1
问题 A: 1.2 神奇兔子数列
题目地址
题目描述
假设第 1 个月有 1 对刚诞生的兔子第 2 个月进入成熟期第 3 个月开始生育兔子而1 对成熟的兔子每月会生 1 对兔子兔子永不死去……那么由 1 对初生兔子开始12 个月后会有多少对兔子呢 兔子数列即斐波那契数列它的发明者是意大利数学家列昂纳多·斐波那契Leonardo Fibonacci1170—1250。1202 年他撰写了《算盘全书《Liber Abaci》一书该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则介绍了中国的“盈不足术”引入了负数并研究了一些简单的一次同余式组。
输入
无
输出
一个整数12个月后有多少对兔子
解题思路
这道题就是要求斐波那契数列的第12项
在计算斐波那契数列的过程中我们只需要关注连续的3项。
使用两个变量_1和_2代表已经计算出的第一项和第二项那么要计算出的第三项_3就等于12_1 _212
如此往复更新第一项和第二项为原来的第二项和第三项就能不断求出新的第三项。
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;
}Python
_1, _2, _3 1, 1,
for i in range(3, 13):_3 _1 _2_1, _2 _2, _3
print(_3)问题 B: 1.3 马克思手稿中的数学题
题目地址
题目描述
马克思手稿中有一道趣味数学问题有 30 个人其中有男人、女人和小孩这些人在一家饭馆吃饭花了 50 先令每个男人花 3 先令每个女人花 2 先令每个小孩花 1 先令问男人、女人和小孩各有几人
输入
无
输出
输出所有可能的解 每行三个整数xyz用空格隔开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;
}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)问题 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;
}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)breakans 1问题 D: 1.5 哥德巴赫猜想
题目地址
题目描述
哥德巴赫猜想任一大于 2 的偶数都可表示成两个素数之和。 验证2000 以内大于 2 的偶数都能够分解为两个素数之和。
输入
无
输出
2000 以内大于 2 的偶数被分解的两个素数
按升序排列第一个素数为最小值
422
633
835
1037
1257
14311
16313......解题思路
题目数据范围不大我们可以先求出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() {vectorint prime;unordered_setint 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;
}Python
from math import sqrtdef isPrime(n):k int(sqrt(n))for i in range(2, k 1):if n % i 0:return Falsereturn Trueprime []
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问题 E: 2.2 加勒比海盗船
题目地址
题目描述 在北美洲东南部有一片神秘的海域那里碧海蓝天、阳光明媚这正是传说中海盗最活跃的加勒比海Caribbean Sea。17 世纪时这里更是欧洲大陆的商旅舰队到达美洲的必经之地所以当时的海盗活动非常猖獗海盗不仅攻击过往商人甚至攻击英国皇家舰……有一天海盗们截获了一艘装满各种各样古董的货船每一件古董都价值连城一旦打碎就失去了它的价值。虽然海盗船足够大但载重量为 C每件古董的重量为 wi海盗们该如何把尽可能多数量的宝贝装上海盗船呢输入
请输入问题的组数 m
m ( 0 m 100 )
请输入载重量 c 及古董个数 n
c n (0 c, n 10000)
请输入每个古董的重量用空格分开
w1 w2 w3 ... wn (0 wi 100)输出
能装入的古董最大数量为: ans
输入样例
1
30 8
4 10 7 11 3 5 14 2输出样例
5解题思路
装载数量优先那必是先装重量小的。
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;
}Python
T int(input())
for _ in range(T):m, n map(int, input().split())a list(map(int, input().split()))a.sort()ans 0while m 0 and ans n:if m a[ans]:m - a[ans]ans 1else:breakprint(ans)问题 F: 2.3 阿里巴巴与四十大盗
题目地址
题目描述 有一天阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时远处突然出现一股烟尘弥漫着直向上空飞扬朝他这儿卷过来而且越来越近。靠近以后他才看清原来是一支马队他们共有四十人一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋从丛林中一直来到那个大石头跟前喃喃地说道“芝麻开门吧”随着那个头目的喊声大石头前突然出现一道宽阔的门路于是强盗们鱼贯而入。阿里巴巴待在树上观察他们直到他们走得无影无踪之后才从树上下来。他大声喊道“芝麻开门吧”他的喊声刚落洞门立刻打开了。他小心翼翼地走了进去一下子惊呆了洞中堆满了财物还有多得无法计数的金银珠宝有的散堆在地上有的盛在皮袋中。突然看见这么多的金银财富阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界见识一下这些宝物他想一种宝物只拿一个如果太重就用锤子凿开但毛驴的运载能力是有限的怎么才能用驴子运走最大价值的财宝分给穷人呢阿里巴巴陷入沉思中……输入
样例的组数 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
6 19
2 8
6 1
7 9
4 3
10 2
3 4输出样例
24.6解题思路
注意题目描述了吗“如果太重就用锤子凿开”。好家伙凿开还是宝物的话那就看哪个宝物的“含金密度”大呗
接下来我们给每个宝物评分评分规则是宝物的“密度”重量体积\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;
}Python
Python提交上去会超时。。。
class Treasure:def __init__(self, v, w) - None:self.v vself.w wself.score v / w if w else 100000000T int(input())
for _ in range(T):while True:thisLine input()if thisLine:breakn, m map(int, thisLine.split())a []for __ in range(n):w, v map(int, input().split())a.append(Treasure(v, w))a.sort(keylambda x: -x.score)v 0w mth 0while w 0 and th n:# print(* * 50)if not a[th].w:v a[th].vth 1continuethisW min(w, a[th].w)v thisW * a[th].scorew - thisWth 1if int(v) v:print(int(v))else:print({:.1f}.format(v))问题 G: 2.4 高级钟点秘书
题目地址
题目描述
所谓“钟点秘书”是指年轻白领女性利用工余时间为客户提供秘书服务并按钟点收取酬金。“钟点秘书”为客户提供有偿服务的方式一般是采用电话、电传、上网等“遥控”式服务或亲自到客户公司处理部分业务。其服务对象主要有三类一是外地前来考察商务经营、项目投资的商人或政要人员他们由于初来乍到急需有经验和熟悉本地情况的秘书帮忙二是前来开展短暂商务活动或召开小型资讯发布会的国外客商三是本地一些请不起长期秘书的企、事业单位。这些客户普遍认为请“钟点秘书”一则可免去专门租楼请人的大笔开销二则可根据开展的商务活动请有某方面专长的可用人才三则由于对方是临时雇用关系工作效率往往比固定的秘书更高。据调查在上海“钟点秘书”的行情日趋看好。对此业内人士认为为了便于管理各大城市有必要组建若干家“钟点秘书服务公司”通过会员制的形式为众多客户提供规范、优良、全面的服务这也是建设国际化大都市所必需的。
某跨国公司总裁正分身无术为一大堆会议时间表焦头烂额希望高级钟点秘书能做出合理的安排能在有限的时间内召开更多的会议。输入
输入样例组数
t ( 0 t 10 )
输入会议总数
n ( 0 n 10000)
输入会议的开始时间和结束时间以空格分开 ( 0 bi, ei 50 )
b1 e1
b2 e2
...
bn en输出
最多可以安排的会议数目m
输入样例
1
10
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14输出样例
4解题思路
对所有的会议排序排序规则是结束早的会议优先靠前。
这样我们只需要从前到后遍历所有的会议如果某个会议的开始时间不早于“秘书最后参会”的结束时间那么就参加这个会议。
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 pairint, 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;
}Python Author: LetMeFly
Date: 2023-02-24 11:15:31
LastEditors: LetMeFly
LastEditTime: 2023-02-24 20:58:03T 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(keylambda x: x[1])lastEnd 0ans 0for p in a:if p[0] lastEnd:ans 1lastEnd p[1]print(ans)问题 H: 2.5 一场说走就走的旅行
题目地址
题目描述
有一天孩子回来对我说“妈妈听说马尔代夫很不错放假了我想去玩。”
马尔代夫我也想去没有人不向往一场说走就走的旅行
“其实我想去的地方很多呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。
于是我们拿出地图标出想去的地点然后计算最短路线估算大约所需的时间有了这张秘制地图一场说走就走的旅行不是梦
“哇感觉我们像凡尔纳的《环游地球八十天》好激动可是老妈你也太 out 了学计算机的最短路线你用手算”
暴汗……“小子你别牛你知道怎么算”
“呃好像是叫什么迪科斯彻的人会算。”
哈哈关键时刻还要老妈上场了输入
样例组数
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 )输出
小明到各个城市的最短距离;
l1 l2 ... ln (若某城市无法达到则输出impossible输入样例
1
5 11
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
5输出样例
8 24 23 30 0解题思路
这道题是典型的单源起点最短路径的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 pairint, int pii;
#define INF 1e9int shortest[111];
vectorpii graph[111];
bool visited[111];int main() {int T;cin T;while (T--) {int n, m;cin n m;// initfor (int i 1; i n; i) {shortest[i] INF;visited[i] false;graph[i].clear();}// cinfor (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;// beginshortest[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);}}// coutfor (int i 1; i n; i) {if (shortest[i] INF) {printf(impossible );}else {printf(%d , shortest[i]);}}}return 0;
}Python
T int(input())
for __CASE in range(T):n, m map(int, input().split())# initvisited [False for _ in range(n 1)]graph [[] for _ in range(n 1)]shortestDistance [1e9 for _ in range(n 1)]# cinfor _ in range(m):u, v, d map(int, input().split())graph[u].append((v, d))start int(input())# beginshortestDistance[start] 0for _ in range(n):thisMinDistance 1e9shortestPoint -1for j in range(1, n 1):if not visited[j] and shortestDistance[j] thisMinDistance:thisMinDistance shortestDistance[j]shortestPoint jif shortestPoint -1:breakvisited[shortestPoint] Truefor toPoint, thisDistance in graph[shortestPoint]:shortestDistance[toPoint] min(shortestDistance[toPoint], shortestDistance[shortestPoint] thisDistance)# coutfor i in range(1, n 1):if shortestDistance[i] 1e9:print(impossible, end )else:print(shortestDistance[i], end )print()我做了个讲解Dijstra算法的视频快去看看吧https://www.bilibili.com/video/BV1Y84y1N7Lm
问题 I: 2.6 神秘电报密码
题目地址
题目描述
看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已吴志国大队长在受了残忍的“针刑”之后躺在手术台上唱空城计变了音调把消息传给了护士顾晓梦在 衣服上缝补了长短不一的针脚……那么片中无处不在的摩尔斯码到底是什么它又有着怎
样的神秘力量呢
摩尔斯电码Morse code由点 dot. 、划 dash-两种符号组成。它的基本原理是
把英文字母表中的字母、标点符号和空格按照出现的频率排序然后用点和划的组合来代表这些字母、标点符号和空格使频率最高的符号具有最短的点划组合。输入
输入样例组数
t ( 0 t 10 )
输入节点数目
n ( 0 n 30 )
输入节点的名称和值
( x 为字母 0 v 1 )
x1 v1
x2 v2...
xi vi输出
输出每一个节点的哈夫曼编码( 注不同节点间用空格隔开每个节点内冒号后用空格隔开
x: y输入样例
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解题思路
哈夫曼编码的核心思想是“权重越小的距离根越远”
构建哈夫曼树时在节点数量大于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_mapchar, string output2where) {if (root-isLeaf) {output2where[root-c] nowString;return;}// not leafif (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_queueNode*, vectorNode*, cmp pq;vectorchar charOrder;unordered_mapchar, string ans;// inputfor (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);}// buildwhile (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();}// outputoutput(root, , ans);for (char c : charOrder) {cout c : ans[c] ;}puts();// enddestroyTree(root);}return 0;
}/*
1
6
a 0.05
b 0.32
c 0.18
d 0.07
e 0.25
f 0.13a: 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.00b: 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
*/上述代码我不认为它是错误的但是它不能通过本题。
因为题目给定的数据中有很多权重相同的节点。题目中未规定这些节点的编码顺序。因此答案不唯一但本题无特判。
我的上述代码使用的是“C的优先队列”本质上是堆。这样在获取“weight最低的两个节点”时效率较高。而题目的作者应该是遍历所有节点来获取的。因此答案不同。
Python
class Node:c isLeaf FalseleftChild, rightChild , weight 0ans dict()def output(root: Node, nowString: str):if root.isLeaf:ans[root.c] nowStringreturnif 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 []# inputfor _ in range(n):c, weight input().split()weight float(weight)charOrder.append(c)thisNode Node()thisNode.c cthisNode.weight weightthisNode.isLeaf TrueNodes.append(thisNode)# buildwhile len(Nodes) 1:Nodes.sort(keylambda x : x.weight)leftNode, rightNode Nodes[0], Nodes[1]Nodes Nodes[2:]newNode Node()newNode.isLeaf FalsenewNode.weight leftNode.weight rightNode.weightnewNode.leftChild leftNodenewNode.rightChild rightNodeNodes.append(newNode)root if Nodes[0].isLeaf:root Node()root.isLeaf Falseroot.leftChild Nodes[0]root.rightChild root.weight Nodes[0].weightelse:root Nodes[0]# outputoutput(root, )for c in charOrder:print(f{c}: {ans[c]} , end)print()在Python版本的代码中我没有使用优先队列而是采用了排序的方式恰好和答案编码相同。
以下是我对本题如何Special judge的一点思路
首先判断用户答案的合法性
不同节点路径不同一个节点的路径不会为另一个节点的子路径
接着判断用户答案的“压缩程度”
∑len(codei)×freq(chari)\sum len(code_i)\times freq(char_i)∑len(codei)×freq(chari)
简言之就是 字符编码的长度×字符出现频率 之和。
如果“压缩程度”和标准答案相同则视为用户的答案是正确的如果“压缩程度”大于标准答案则说明用户的答案不是最优解如果“压缩程度”小于标准答案则说明标准答案错误标准答案不是最优解
问题 J: 2.7 沟通无限校园网
题目地址
题目描述
校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门也可以形成多个局域网络并通过有线或无线方式连接起来。
原来的网络系统只局限于以学院、图书馆为单位的局域网不能形成集中管理以及各种资源的共享个别学院还远离大学本部这些情况严重地阻碍了整个学校的网络化需求。现在需要设计网络电缆布线将各个单位的 局域网络连通起来如何设计能够使费用最少呢
输入
输入样例组数
t ( 0 t 10 )
输入结点数和边数
n m ( 0 n 100 , 0 m 10000 )
输入结点数uv和边值 w ( 0 w 100 )
u1 v1 w1
u2 v2 w2
...
ui vi wi输出
最小的花费 ans
输入样例
1
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
1输出样例
57解题思路
写在前面 这道题没有说“当给定图为非连通图时输出0”。。。。。。
还有 样例最后一行多出来的那个1是什么鬼
这道题是典型的最小生成树问题。
我C代码所采用的方案是从某个点开始将所有能走的路“入队”。接着每次从队列中取出权重最小的那一条如果这条边的终点还未被接通就使用这条边并将终点能到达的所有边入队。
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 Edge {int toNode;int weight;Edge(int toNode, int weight) : toNode(toNode), weight(weight) {}friend bool operator (const Edge a, const Edge b) {return a.weight b.weight; // 权重小的在前}
};int main() {// freopen(C:/Users/LetMe/Desktop/test1.in, r, stdin);int T;cin T;while (T--) {int n, m;cin n m;vectorbool visited(n 1, false);vectorvectorEdge graph(n 1);for (int i 0; i m; i) {int u, v, w;scanf(%d%d%d, u, v, w);graph[u].push_back({v, w});graph[v].push_back({u, w});}visited[1] true;priority_queueEdge pq;for (Edge thisEdge : graph[1]) {pq.push(thisEdge);}int ans 0;int cntEdge 0;while (cntEdge n - 1) {if (!pq.size()) {break;}Edge thisEdge pq.top();pq.pop();// printf(pq.size() %lld\n, pq.size()); //*********if (!visited[thisEdge.toNode]) {visited[thisEdge.toNode] true;ans thisEdge.weight;cntEdge;for (Edge thatEdge : graph[thisEdge.toNode]) {pq.push(thatEdge);}}}// printf(n %d, cntEdge %d, ans ,n, cntEdge); //*********if (cntEdge ! n - 1) {puts(0);}else {cout ans endl;}}return 0;
}Python
from queue import PriorityQueueclass Edge:toNode weight 0def __init__(self, toNode, weight) - None:self.toNode toNodeself.weight weightdef __lt__(self, other: Edge) - bool:return self.weight other.weightT int(input())
for _CASE in range(T):n, m map(int, input().split())visited [False for _ in range(n 1)]graph [[] for _ in range(n 1)]for _ in range(m):u, v, w map(int, input().split())graph[u].append(Edge(v, w))graph[v].append(Edge(u, w))visited[1] Truepq PriorityQueue()for thisNode in graph[1]:pq.put(thisNode)ans 0cntEdge 0while cntEdge n - 1:if pq.empty():breakthisEdge pq.get()if not visited[thisEdge.toNode]:visited[thisEdge.toNode] Trueans thisEdge.weightcntEdge 1for thatEdge in graph[thisEdge.toNode]:pq.put(thatEdge)if cntEdge is not n - 1:print(0)else:print(ans)问题 K: 3.3 合久必分分久必合
题目地址
题目描述
在数列排序中如果只有一个数那么他本身就是有序的如果只有两个数那么一次比较就可以完成排序。也就是说数越少排序越容易。那么如果有一个有大量数据组成的数列我们很难快速完成排序该怎么办呢可以考虑将其分解为很小的数列直到只剩下一个数时本身已有序再把这些有序的数列合并在一起执行一个和分解相反的过程从而完成整个数列的排序。输入
请输入样例组数
t ( 0 t 100 )
请输入数列中元素的个数
n ( 0 n 10000 )
请依次输入数列中的元素
x1 x2 ... xn ( 0 x 10000 )输出
合并排序的结果
x1 x2 ... xn输入样例
1
8
42 15 20 6 8 38 50 12输出样例
6 8 12 15 20 38 42 50解题思路
题目作者大概是想让我们使用“归并排序”吧
遇到这种题当然是要先愉快地AC了再说。先直接一个内置的sort
AC代码
C
内置sort版
#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 n;cin n;for (int i 0; i n; i) {scanf(%d, a[i]);}sort(a, a n);for (int i 0; i n; i) {printf(%d , a[i]);}puts();}return 0;
}真正的归并排序版
#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 temp[10010];void mergeSort(int l, int r) {if (l 1 r) {return;}int m (l r) 1;mergeSort(l, m);mergeSort(m, r);int ll l, lr m; // loc l, loc rint lt l; // loc tempwhile (ll m lr r) {if (a[ll] a[lr]) {temp[lt] a[ll];}else {temp[lt] a[lr];}}while (ll m) {temp[lt] a[ll];}while (lr r) {temp[lt] a[lr];}for (int i l; i r; i) {a[i] temp[i];}
}int main() {int T;cin T;while (T--) {int n;cin n;for (int i 0; i n; i) {scanf(%d, a[i]);}mergeSort(0, n);for (int i 0; i n; i) {printf(%d , a[i]);}puts();} return 0;
}/*
1
8
42 15 20 6 8 38 50 12*/Python
内置sort版
T int(input())
for _CASE in range(T):n int(input())a list(map(int, input().split()))a.sort()for i in a:print(i, end )print()真正的归并排序版
a []
temp [0 for _ in range(10010)]def mergeSort(l: int, r: int) - None:if l 1 r:returnm (l r) 1mergeSort(l, m)mergeSort(m, r)ll, lr l, mlt lwhile ll m and lr r:if a[ll] a[lr]:temp[lt] a[ll]lt 1ll 1else:temp[lt] a[lr]lt 1lr 1while ll m:temp[lt] a[ll]lt 1ll 1while lr r:temp[lt] a[lr]lt 1lr 1for i in range(l, r):a[i] temp[i]T int(input())
for _CASE in range(T):n int(input())a list(map(int, input().split()))mergeSort(0, n)# for i in a:# print(i, end )# print()print(*a)对于test1.in需要执行约4s的时间在BUCTOJ上可能会T
The End
题解是从2月21号开始写的但这都结束一周了就先这样吧。 同步发文于CSDN原创不易转载请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/129327761
