蓝桥杯 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~

 

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

剪邮票如【图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~

 

 

第七届 蓝桥杯 省赛 第六题 方格填数(next_permutation)

填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)
一共有多少种可能填写的方案?
请填写表示方案数目的整数~

分析:从左到右从上到下标为0~9,将a[10]中的数字依次填入,所以只要将a数组从0123456789一直全排列试到9876543210,测试每一个结果是否满足,满足条件的次数累加得到的就是方案数目~答案是1580~

 

蓝桥杯 算法提高 队列操作

问题描述
  队列操作题。根据输入的操作命令,操作队列(1)入队、(2)出队并输出、(3)计算队中元素个数并输出。
输入格式
  第一行一个数字N。
  下面N行,每行第一个数字为操作命令(1)入队、(2)出队并输出、(3)计算队中元素个数并输出。
输出格式
  若干行每行显示一个2或3命令的输出结果。注意:2.出队命令可能会出现空队出队(下溢),请输出“no”,并退出。
样例输入
7
1 19
1 56
2
3
2
3
2
样例输出
19
1
56
0
no
数据规模和约定
  1<=N<=50

分析:用C++的STL队列实现~