蓝桥杯 ALGO-4 算法训练 结点选择

问题描述

有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?

输入格式

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行,每行描述树上的一条边。

输出格式
输出一个整数,代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点,权值和为 3+4+5 = 12 。
数据规模与约定

对于20%的数据, n <= 20。

对于50%的数据, n <= 1000。

对于100%的数据, n <= 100000。

权值均为不超过1000的正整数。

分析:题目给出的数据不一定是二叉树,所以可以看作图来处理~其实就是用邻接表存储啦~v[i]数组中保存i结点的孩子节点们~dp[i][0]表示不取i结点的结果~dp[i][1]表示取i结点的结果~

用深度优先搜索+动态规划,每个点的最大权值有取当前这个点和不取当前这个点两种情况~如果取当前点,则不能取与它相邻的任何点;不取当前点,则取与它相邻点的最大值进行累加~从底向上累加到顶部~max(dp[1][0], dp[1][1])就是所求结果~

用一个变量pre保存当前结点的前一个结点~如果等于pre说明访问到了它的父亲结点,为了防止重复访问,要在v[node][i]不等于pre时候继续dfs下去~否则可能会形成无限循环的环~

 

第六届 蓝桥杯 省赛 第一题 奖券数目

有些人很迷信数字,比如带“4”的数字,认为和“死”谐音,就觉得不吉利。

虽然这些说法纯属无稽之谈,但有时还要迎合大众的需求。某抽奖活动的奖券号码是5位数(10000-99999),

要求其中不要出现带“4”的号码,主办单位请你计算一下,如果任何两张奖券不重号,最多可发出奖券多少张。

请提交该数字(一个整数),不要写任何多余的内容或说明性文字。

分析:从10000~99999,统计没有一位为4的数字的个数~结果为52488~

当然也可以不用代码解决~用排列组合~8*9*9*9*9=52488~

 

第七届 蓝桥杯 省赛 第九题 交换瓶子

有N个瓶子,编号 1 ~ N,放在架子上。
比如有5个瓶子:
2 1 3 5 4
要求每次拿起2个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5
对于这么简单的情况,显然,至少需要交换2次就可以复位。
如果瓶子更多呢?你可以通过编程来解决。
输入格式为两行:
第一行: 一个正整数N(N<10000), 表示瓶子的数目
第二行:N个正整数,用空格分开,表示瓶子目前的排列情况。
输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。
例如,输入:
5
3 1 2 5 4
程序应该输出:
3
再例如,输入:
5
5 4 3 2 1
程序应该输出:
2
资源约定:
峰值内存消耗 < 256M
CPU消耗  < 1000ms

分析:遍历数组,如果当前位置的瓶子编号不对,就找到那个正确编号的瓶子交换过来,累加得到交换的次数cnt~

 

第七届 蓝桥杯 省赛 第八题 四平方和

四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去,就正好可以表示为4个数的平方和。

比如:
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符号表示乘方的意思)

对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对4个数排序:
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法

程序输入为一个正整数N (N<5000000)
要求输出4个非负整数,按从小到大排序,中间用空格分开

例如,输入:
5
则程序应该输出:
0 0 1 2

再例如,输入:
12
则程序应该输出:
0 2 2 2

再例如,输入:
773535
则程序应该输出:
1 1 267 838

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

分析:直接四层循环可能会超时,可以考虑先将两个数能构成的平方和保存在map里面,如果在前两层循环的时候,发现剩下的数并不能由两个数的平方构成,就直接continue跳过~否则就判断第三层循环,然后用sqrt(num – a * a – b * b – c * c)算出最后一个数temp,看它是否为整数~如果是整数就输出~并且退出程序~

 

 

第七届 蓝桥杯 省赛 第七题 剪邮票

剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

请你计算,一共有多少种不同的剪取方法。

分析:i1、i2、i3、i4和i5为枚举要剪下的5个数,对这五个数构成的连通性进行dfs判断,如果dfs后测得从i1出发从上下左右四个方向上深度优先搜索遍历为i2~i5之间的所有点,cnt标记i5能够走到的是i1~i5这些点的个数,如果cnt == 5就说明是连在一起的,注意从4和8向右行走走不到5和9,并且从5和9出发向左行走走不到4和8~所以遇到index == 4或者index == 8并且是向右走的时候continue~(index == 5和9并向左走同理~)将result加一~累加得到的result就是结果116~