【2022暑期训练-5】7-5 3824经典游戏
24点游戏,也叫3824游戏,是一款经典的心算数字游戏。给出区间[1,13]内的四个整数,验证能否用加、减、乘、除四则运算,将这四个整数组合成24。比如:(3,8,2,4) 可以算出 8∗(4−3+2)=24或者(8−4)∗(2∗3)=24,而(1,1,2,2)无法算出24。注意整除必须除尽,即9/2+10+10=24这种计算无效。
输入格式第一行给出正整数N(1≤N≤1000)。接下来N行数据,每行给出四个正整数ai bi ci di, 用空格分开。(∀i∈{1,…,N}:1≤ai,bi,ci,di≤13)
输出格式输出N行数据,第i行对应输入数据(ai,bi,ci,di),如果能算出24,则输出24,如果不能则输出0。
输入样例1234541 1 1 11 2 3 43 9 11 213 3 5 7
输出样例1234024024
(1,1,1,1)和(3,9,11,2)都无法算出24,(1,2,3,4)和(13,3,5,7)可以算出:1∗2∗3∗4=24和(13∗5+7)/3=24。
解题思路此题大意是计算4个数通过各种组合能否计算出结果24,我们通过回溯还是可以遍历每一种加减 ...
【2022暑期训练-5】7-3 找零钱
收银员现有 n 张面值分别为 v1,v2,…,vn 的纸币。若找零金额为 m,则一共有多少种找零方法?
注:0<n≤1000,0<v1,v2,…,vn≤10000,0<m≤10000
输入格式123nv1,v2,...,vnm
输出格式12若有解,则输出全部找零方案,每输出一种若无解,则输出“None”
输入样例112363 1 4 3 2 79
输出样例112343 1 3 23 4 24 3 22 7
输入样例212355 3 4 6 72
输出样例21None
解题思路通过分析题目可知,我们可以将手中n个钞票面值的子集做相加,让和等于m。因此改题的解空间树是子集树。
定义 v[ ] 数组存放面值
book [ ] 数组记录,每一个元素的值是0或1,在子集树中代表该节点的两个分支。0 代表该层节点不放入子集中,1代表该节点放入子集中。
子集树的层数为 n+1 层,因为最后一层也需要判断是否进入子集,就会多一层分支。
扩展节点的约束条件是 n_num < m,只要当前选择的面值和小于找零总数 m ,就要深入子集树,寻找下一个节点。
扩展节点的限界条 ...
【2022暑期训练-5】7-1 子集和问题
给定n个不同的正整数集合w=(w1,w2,…,wn)和一个正数W,要求找出w的子集s,使该子集中所有元素的和为W。
输入格式第一行输入n和W,第二行依次输入n个数。
输出格式每行输出一个符合要求的子集。
输入样例124 3111 13 24 7
输出样例1211 13 7 24 7
解题思路定义的a[ ]数组,是用来存放输入的数据
定义的x[ ]数组,每一个元素的值是0或1,用来判断当前节点是在子集树中是向左走还是向右走。
通过题目分析可知,本题中应当使用 子集树 作为解空间,使用tw记录当前整数和,使用rw记录余下的整数的和。
扩展节点的约束条件:tw+a[i] <= c i 表示子集树的层数
如果把当前节点加入到当前的整数和中小于等于目标c,那么表示当前节点需要加进来,用x[i]=1表示加进来了,也表示向左走。加进来之后tw=tw+a[i],rw=rw-a[i]
扩展节点的限界函数:tw+rw-a[i]>=c||tw+a[i]>=c
如果a[i]加不进来,那么x[i]=0,代表向右走。
tw+rw-a[i]>=c 表示不加a[i]当前的tw和那些没有被 ...
区块链
区块链区块链是一种以密码学方式保证的不可篡改和不可伪造的分布式账本。
区块链的几个特性
去中心化。没有第三方中介,一切都由程序来完成。
安全性。主要体现在分布式、51%攻击,即使一个节点被攻击或宕机也不会影响网络的运行。
最核心的就是:去信任。一切社会行为都要建立在”信任“的基础上,这也是区块链解决的最根本的问题。
型的攻击,这些攻击很容易将您的所有数据泄露给黑客。
区块链的发展历程
萌发阶段(2007 年—2009 年): 比特币现出区块链进入视野
“奇客”小众阶段( 2010 年—2012 年):比特币交易所出现,互联网热狂热人参与比特币
市场酝酿阶段( 2013 年—2015 年):德国确认了比特的地位、百度开通比特币支付通道
区块链主流期( 2016 年—2018 年):避险功能的比特币开始复苏市场需求量变大、比特币的致富效 应、芝加哥商品交易所上线比特币期货交易;
产业落地阶段( 2019 年—2021 年):虚拟币和区块链回归理性、加快区块链与市场融合应用。
区块链的核心技术
1.分布式账本:交易记账由多个节点共同完成,而且每一个节点都记录的是完整的账目 ...
day23 Carbon语言
取代 C++,Google 强势开源 Carbon语言每一种编程语言都曾想一统江湖,将其他语言取而代之。但事实上,能够在众多竞争者中脱颖而出并雄霸一方天地并非易事。今天,谷歌重磅公开了其内部建立的最新编程语言——Carbon,剑指 C++,欲成为其实验性继任者。
历朝历代的“继承者们”多年来,谷歌创建了许多编程语言,其中一些已经广为流行并深受大家的喜爱。例如,Golang(简称 Go)是为了改善服务器和分布式系统的开发而创建的,后来被公众采用。同时,Dart 编程语言,最初是作为 JavaScript 的替代品,直到 Flutter 的发布后终于成为主流语言。
日前在多伦多举行的 Cpp North 大会(专门讨论 C++ 的会议)上,谷歌首席软件工程师和开源软件开发者 Chandler Carruth 分享了一种名为 Carbon 的新编程语言的愿景。Carruth 展示了当今许多最流行的编程语言是如何拥有继承者的,这些继承者们利用了现代语言设计的优势,使开发者能够迅速提高生产力。
正如我们熟知的,C++ 是 C 语言的继承者,Kotlin 是 Java 的继承者,Swift 是 O ...
day21 开发者偏爱Linux的9大理由
开发者偏爱Linux的9大理由我们日常使用的大多数设备运行的都是 Linux 或定制版本的 Linux。包括 Android 手机、平板电脑、相机、录像机、可穿戴设备、Chromebook 和其他设备。
有趣的事实:您使用的大多数互联网服务和社交媒体网站都在 Linux 上运行,因为这是最值得信赖的操作系统。
01强大的命令行
命令行有很多功能,它使您能够快速开发并自动执行日常任务。很多开发者喜欢它,正是因为它不需要鼠标或触控板。
除此以外还能使日常任务可以自动化。这可以帮助开发者专注于手头更重要的任务,并节省大量时间。Linux虽然不完美,但保持了终端的纯度。
02Linux 非常安全
因为 Linux 是开源的,由大型开发人员社区开发和维护的,所以捕获和修复安全漏洞的几率更高。此外,Windows 仍然是最受欢迎的操作系统,约占台式机和笔记本电脑市场的76.7%。因此,大多数攻击针对的都是Windows 而不是 Linux。
03对开发人员非常友好
与 Windows 用户相比,Linux 比以往任何时候都更加对用户友好。但正因为Linux 专门为开发人员提供的工具 ...
【2022暑期训练-4】7-7 公路村村通
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。
输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−1,表示需要建设更多公路。
输入样例:123456789101112131415166 151 2 51 3 31 4 71 5 41 6 22 3 42 4 62 5 22 6 63 4 63 5 13 6 14 5 104 6 85 6 3
输出样例:112
思路: 该题为最小生成树问题,一般有两种算法,Prim算法、Kruskal算法。这里边的个数M≤3N,说明边的数量级与结点个数一致,使用Kruskal算法更好。如下采用Kruskal算法
代码:12345678910111213141516171819202122232425262728293031323334 ...
【2022暑期训练-4】7-5 最短路径算法(Floyd-Warshall)
在带权有向图G中,求G中的任意一对顶点间的最短路径问题,也是十分常见的一种问题。
解决这个问题的一个方法是执行n次迪杰斯特拉算法,这样就可以求出每一对顶点间的最短路径,执行的时间复杂度为O(n3)。而另一种算法是由弗洛伊德提出的,时间复杂度同样是O(n3),但算法的形式简单很多。
在本题中,读入一个有向图的带权邻接矩阵(即数组表示),建立有向图并使用Floyd算法求出每一对顶点间的最短路径长度。
输入格式:输入的第一行包含1个正整数n,表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数,如果大于0,则表示第i个顶点有指向第j个顶点的有向边,且权值为对应的整数值;如果这个整数为0,则表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为0。
输出格式:共有n行,每行有n个整数,表示源点至每一个顶点的最短路径长度。
如果不存在从源点至相应顶点的路径,输出-1。对于某个顶点到其本身的最短路径长度,输出0。
请在每个整数后输出一个空格,并请注意行尾输出换行。
输入样例:1234540 3 0 10 0 4 02 0 0 00 0 1 ...
【2022暑期训练-4】7-6 哈利·波特的考试
哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。
现在哈利·波特的手里有一本教材,里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场,要考察他把这只动物变成任意一只指定动物的本事。于是他来问你:带什么动物去可以让最难变的那种动物(即该动物变为哈利·波特自己带去的动物所需要的魔咒最长)需要的魔咒最短?例如:如果只有猫、鼠、鱼,则显然哈利·波特应该带鼠去,因为鼠变成另外两种动物都只需要念4个字符;而如果带猫去,则至少需要念6个字符才能把猫变成鱼;同理,带鱼去也不是最好的选择。
输入格式:输入说明:输入第1行给出两个正整数N (≤100)和M,其中N是考试涉及的动物总数,M是用于直接变形的魔咒条数。为简单起见,我们将动物按1~N编号。随后M行,每行给出了3个正整数,分别是两种 ...
【2022暑期训练-4】7-1 列出叶结点
“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子,叫“右视图”;女生的侧影是从她左侧看过去的样子,叫“左视图”。
520 这个日子还在打比赛的你,也就抱着一棵二叉树左看看右看看了……
我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树,其右视图就是 { 1, 2, 3, 4, 5 },左视图就是 { 1, 6, 7, 8, 5 }。
于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树,然后你要输出这棵树的左视图和右视图。
输入格式:输入第一行给出一个正整数 N (≤20),为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同,其数值大小无关紧要,都不超过 int 的范围。
输出格式:第一行输出右视图,第二行输出左视图,格式如样例所示。
输入样例:12386 8 7 4 5 1 3 28 5 4 7 6 3 2 1
输出样例:12R: 1 2 3 4 5L: 1 6 7 8 5
思路: 根据树的中序和后序遍历序列建立树,得到树的层次遍历序列 ...