2015年蓝桥杯初赛b组试题

第一题 结果填空 3 奖券数目 有些人很迷信数字 比如带 4 的数字 认为和 死 谐音 就觉得不吉利 虽然这些说法纯属无稽之谈 但有时还要迎合大众的需求 某抽奖活动的奖券号码是 5 位 数 10 99 要求其中不要出现带 4 的号码 主办单位请你计算一下 如果任何两张 奖券不重号 最多可发出奖券多少张 请提交该数字 一个整数 不要写任何多余的内容或说明性文字 题解 考试的时候写了个回溯法 然后屁颠屁颠的开始做下面一题了 结果错了 1 include 2 using namespace std 3 bool fuck int t 4 5 while t 6 7 if t 10 4 return false 8 t 10 9 10 return true 11 12 int main 13 14 int ans 0 t 10 15 while t 100 16 if fuck t ans 17 cout ans endl 18 return 0 19 第一题 正确答案 52488 我居然上来第一题就错了 居然写了 13440 cout 8 9 9 9 9 第二题 结果填空 5 星系炸弹 在 X 星系的广袤空间中漂浮着许多 X 星人造 炸弹 用来作为宇宙中的路标 每个炸弹都可以设定多少天之后爆炸 比如 阿尔法炸弹 2015 年 1 月 1 日放置 定时为 15 天 则它在 2015 年 1 月 16 日爆炸 有一个贝塔炸弹 2014 年 11 月 9 日放置 定时为 1 天 请你计算它爆炸的准确日期 请填写该日期 格式为 yyyy mm dd 即 4 位年份 2 位月份 2 位日期 比如 2015 02 19 请严格按照格式书写 不能出现其它文字或符号 题解 不用废话 直接手算顶多 3 分钟 注意 2016 是闰年 正确答案 2017 08 05 第三题 结果填空 9 三羊献瑞 观察下面的加法算式 祥 瑞 生 辉 三 羊 献 瑞 三 羊 生 瑞 气 如果有对齐问题 可以参看 图 1 jpg 其中 相同的汉字代表相同的数字 不同的汉字代表不同的数字 请你填写 三羊献瑞 所代表的 4 位数字 答案唯一 不要填写任何多余内容 题解 水题 给 祥瑞生辉三羊献气 编号 直接回溯穷举即可 1 include 2 using namespace std 3 int a 8 4 bool b 10 5 void dfs int cur 6 7 if cur 8 8 9 int x a 0 1 a 1 100 a 2 10 a 3 y a 4 1 a 5 100 a 6 10 a 1 z a 4 10 a 5 1 a 2 100 a 1 10 a 7 10 if x y z cout a 4 a 5 a 6 a 1 endl 11 12 else 13 14 for int i 0 i 10 i 15 16 if cur 0 17 if cur 4 18 if b i 19 20 b i 1 21 a cur i 22 dfs cur 1 23 b i 0 24 25 26 27 28 int main 29 30 dfs 0 31 return 0 32 第三题 正确答案 1085 第四题 代码填空 11 格子中输出 StringInGrid 函数会在一个指定大小的格子中打印指定的字符串 要求字符串在水平 垂直两个方向上都居中 如果字符串太长 就截断 如果不能恰好居中 可以稍稍偏左或者偏上一点 下面的程序实现这个逻辑 请填写划线部分缺少的代码 1 include 2 include 3 4 void StringInGrid int width int height const char s 5 6 int i k 7 char buf 1 8 strcpy buf s 9 if strlen s width 2 buf width 2 0 10 11 printf 12 for i 0 i width 2 i printf 13 printf n 14 15 for k 1 k height 1 2 k 16 17 printf 18 for i 0 i width 2 i printf 19 printf n 20 21 22 printf 23 24 printf s s s 填空 25 26 printf n 27 28 for k height 1 2 1 k height 1 k 29 30 printf 31 for i 0 i width 2 i printf 32 printf n 33 34 35 printf 36 for i 0 i width 2 i printf 37 printf n 38 39 40 int main 41 42 StringInGrid 20 6 abcd1234 43 return 0 44 对于题目中数据 应该输出 abcd1234 如果出现对齐问题 参看 图 1 jpg 注意 只填写缺少的内容 不要书写任何题面已有代码或说明性文字 题解 我是一名 OI 党 入门直接学的是 C 结果考了个 printf 里面 s 的用法 太特么冷门了 穷举了没试出来 原来后面的参数要跟两个 分数 11 分怒 丢 正确答案 width strlen s 2 2 s width strlen s 1 2 备注 答案可以形式多样性 只要代入使得代码成立即可 但要注意奇偶问题所以后面一 个要 1 不然 sample 过了也是错的 第五题 代码填空 13 九数组分数 1 2 3 9 这九个数字组成一个分数 其值恰好为 1 3 如何组法 下面的程序实现了该功能 请填写划线部分缺失的代码 1 include 2 3 void test int x 4 5 int a x 0 1 x 1 100 x 2 10 x 3 6 int b x 4 10 x 5 1 x 6 100 x 7 10 x 8 7 8 if a 3 b printf d d n a b 9 10 11 void f int x int k 12 13 int i t 14 if k 9 15 16 test x 17 return 18 19 20 for i k i 9 i 21 22 t x k x k x i x i t 23 f x k 1 24 填空处 25 26 27 28 int main 29 30 int x 1 2 3 4 5 6 7 8 9 31 f x 0 32 return 0 33 注意 只填写缺少的内容 不要书写任何题面已有代码或说明性文字 题解 水题 回溯法的最最基本常识 全局变量回溯完成后必须更改回初值 正确答案 t x k x k x i x i t 备注 1 答案可以形式多样性 只要代入使得代码成立即可 2 我个人认为一个横线可以填多个语句 所以去掉大括号 或者利用原有 t 值少写一句子 no problem 第六题 结果填空 17 加法变乘法 我们都知道 1 2 3 49 1225 现在要求你把其中两个不相邻的加号变成乘号 使得结果为 2015 比如 1 2 3 10 11 12 27 28 29 49 2015 就是符合要求的答案 请你寻找另外一个可能的答案 并把位置靠前的那个乘号左边的数字提交 对于示例 就 是提交 10 注意 需要你提交的是一个整数 不要填写任何多余的内容 题解 水题 一共是 48 个位置 C 48 2 扣掉连在一起的情况 穷举一遍过即可 1 include 2 using namespace std 3 int main 4 5 for int i 1 i 47 i 6 for int j i 2 j 49 j 7 8 int sum 0 9 for int k 1 k i k sum k 10 sum i i 1 11 for int k i 2 k j k sum k 12 sum j j 1 13 for int k j 2 k 50 k sum k 14 if sum 2015 cout i endl 15 16 return 0 17 第六题 正确答案 16 第七题 结果填空 21 牌型种数 小明被劫持到 X 赌城 被迫与其他 3 人玩牌 一副扑克牌 去掉大小王牌 共 52 张 均匀发给 4 个人 每个人 13 张 这时 小明脑子里突然冒出一个问题 如果不考虑花色 只考虑点数 也不考虑自己得到的牌的先后顺序 自己手里能拿到的初 始牌型组合一共有多少种呢 请填写该整数 不要填写任何多余的内容或说明文字 题解 水题 一共是记号为 A 2 3 4 5 6 7 8 9 10 J Q k 的十三个元素 每个元素的情况可 能是 0 1 2 3 4 这十三个元素的和为 13 即可 回溯穷举再剪枝即可 1 include 2 using namespace std 3 int ans 0 sum 0 4 void dfs int cur 5 6 if sum 13 return 7 if cur 13 8 9 if sum 13 ans 10 return 11 12 else 13 14 for int i 0 i 5 i 15 16 sum i 17 dfs cur 1 18 sum i 19 20 21 22 int main 23 24 dfs 0 25 cout ans endl 26 return 0 27 第七题 正确答案 第八题 程序设计 15 移动距离 X 星球居民小区的楼房全是一样的 并且按矩阵样式排列 其楼房的编号为 1 2 3 当排满一行时 从下一行相邻的楼往反方向排号 比如 当小区排号宽度为 6 时 开始情形如下 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 我们的问题是 已知了两个楼号 m 和 n 需要求出它们之间的最短移动距离 不能斜线方 向移动 输入为 3 个整数 w m n 空格分开 都在 1 到 10 范围内 w 为排号宽度 m n 为待计算的楼号 要求输出一个整数 表示 m n 两楼间最短移动距离 例如 用户输入 6 8 2 则 程序应该输出 4 再例如 用户输入 4 7 20 则 程序应该输出 5 资源约定 峰值内存消耗 256M CPU 消耗 1ms 请严格按要求输出 不要画蛇添足地打印类似 请您输入 的多余内容 所有代码放在同一个源文件中 调试通过后 拷贝提交该源码 注意 main 函数需要返回 0 注意 只使用 ANSI C ANSI C 标准 不要调用依赖于编译环境或操作系统的特殊函数 注意 所有依赖的函数必须明确地在源文件中 include 不能通过工程设置而省 略常用头文件 提交时 注意选择所期望的编译器类型 题解 从分值上都能看出来是水题 比前面两个填空题的分值都低 最简单的做法 小学生都会的 用数论的完全剩余系 我们强行更改矩阵的编号 比如题目中的强行更改为 0 1 2 3 4 5 11 10 9 8 7 6 12 13 14 这样就算起来非常方便了 要求的答案就是坐标之差 include include using namespace std int main int w m n cin w m n m n int m1 m w m2 m w if m1 int n1 n w n2 n w if n1 cout abs m1 n1 abs m2 n2 endl return 0 第八题 第九题 程序设计 25 垒骰子 赌圣 atm 晚年迷恋上了垒骰子 就是把骰子一个垒在另一个上边 不能歪歪扭扭 要垒成 方柱体 经过长期观察 atm 发现了稳定骰子的奥秘 有些数字的面贴着会互相排斥 我们先来规范一下骰子 1 的对面是 4 2 的对面是 5 3 的对面是 6 假设有 m 组互斥现象 每组中的那两个数字的面紧贴在一起 骰子就不能稳定的垒起来 atm 想计算一下有多少种不同的可能的垒骰子方式 两种垒骰子方式相同 当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同 由于方案数可能过多 请输出模 10 9 7 的结果 不要小看了 atm 的骰子数量哦 输入格式 第一行两个整数 n m n 表示骰子数目 接下来 m 行 每行两个整数 a b 表示 a 和 b 数字不能紧贴在一起 输出格式 一行一个数 表示答案模 10 9 7 的结果 样例输入 2 1 1 2 样例输出 544 数据范围 对于 30 的数据 n 5 对于 60 的数据 n 100 对于 100 的数据 0 n 10 9 m 36 资源约定 峰值内存消耗 256M CPU 消耗 2ms 请严格按要求输出 不要画蛇添足地打印类似 请您输入 的多余内容 所有代码放在同一个源文件中 调试通过后 拷贝提交该源码 注意 main 函数需要返回 0 注意 只使用 ANSI C ANSI C 标准 不要调用依赖于编译环境或操作系统的特殊函数 注意 所有依赖的函数必须明确地在源文件中 include 不能通过工程设置而省 略常用头文件 提交时 注意选择所期望的编译器类型 题解 终于不是水题了 然而却没全做出来 难度跳跃太大 考场上 我先用 dfs 做 结果数字大于 5 的时间就 hold 不住了 于是果断改成记忆化动 态规划 但是只能到一万 实在没办法了 大神跟我说用矩阵快速幂做 所以现在立马现学现用 程序有空补 考场程序 讲解 利用记忆化 DP 穷举底面衔接的所有情况 dp p q 表示第 p 层底面 是 q 的情况种数 侧面是相互独立的最后乘以 4 n 即可比如提给数据就是 34 再乘上两个 4 但是上限 1 实在是达不到了 1 include 2 include 3 define N 1007 4 using namespace std 5 考场上我用的 map现在想想发现多余了 6 int o 7 0 4 5 6 1 2 3 7 bool fuck 7 7 8 int n m 9 long long ans 0 10 const int maxn 25 11 long long dp maxn 7 12 long long dfs int cur int p 13 14 if cur n return 1 15 else 16 17 if dp cur p 0 return dp cur p 18 long long t 0 19 for int i 1 i n m 32 for int i 0 i t1 t2 36 fuck t1 t2 1 37 fuck t2 t1 1 38 39 for int i 1 i 7 i 40 41 ans dfs 1 i 42 ans N 43 44 for int i 0 i n i 45 46 ans 4 47 ans N 48 49 cout ans endl 50 return 0 51 考场程序 数据不够大所以要扣分 最大只能到 10 AC 版本 矩阵快速幂 同理我们只考虑底面的情况 最后乘上 4 n 即可 我们设六阶矩阵 An 其中 An的第 a 行第 b 列表示第一层底面数字为 a 第 n 层数字为 b 的所有排列的情况 记六阶矩阵 X 中 第 a 行第 b 列表示相邻两层的是否能成功连接的情况 a 和 b 能连则为 1 a 和 b 不能连则为 0 注意是相邻两层的底面 不是衔接面 所以要转化 比如题给的 1 2 要改为 1 5 根据上述定义 易得递推式 An An 1X 且 A1 E 六阶单位矩阵 可得到 An 的表达式为 An Xn 1 那么 ans 就是矩阵 Xn 1 的 36 个元素之和 注意最后侧面的 4 n 也要二分幂不然会爆炸 1 include 2 include 3 define N 1007 4 using namespace std 5 6 struct Matrix 7 8 long long a 6 6 9 Matrix int x 10 11 memset a 0 sizeof a 12 for int i 0 i 6 i a i i x 13 14 15 16 Matrix operator const Matrix 19 for int i 0 i 6 i 20 for int j 0 j 6 j 21 for int k 0 k 1 37 38 return ret 39 40 41 int main 42 43 Matrix z 0 44 for int i 0 i 6 i 45 for int j 0 j n m 51 for int i 0 i t1 t2 55 z a t1 1 t2 2 6 0 56 z a t2 1 t1 2 6 0 57 58 Matrix ret 0 59 ret fast mod z n 1 60 long long ans 0 61 for int i 0 i 6 i 62 63 for int j 0 j 1 80 81 cout ans endl 82 return 0 83 矩阵快速幂 第十题 程序设计 31 生命之树 在 X 森林里 上帝创建了生命之树 他给每棵树的每个节点 叶子也称为一个节点 上 都标了一个整数 代表这个点的和谐 值 上帝要在这棵树内选出一个非空节点集 S 使得对于 S 中的任意两个点 a b 都存在一个 点列 a v1 v2 vk b 使得这个点列中的每个点都是 S 里面的元素 且序列中相邻两 个点间有一条边相连 在这个前提下 上帝要使得 S 中的点所对应的整数的和尽量大 这个最大的和就是上帝给生命之树的评分 经过 atm 的努力 他已经知道了上帝给每棵树上每个节点上的整数 但是由于 atm 不擅 长计算 他不知道怎样有效的求评分 他需要你为他写一个程序来计算一棵树的分数 输入格式 第一行一个整数 n 表示这棵树有 n 个节点 第二行 n 个整数 依次表示每个节点的评分 接下来 n 1 行 每行 2 个整数 u v 表示存在一条 u 到 v 的边 由于这是一棵树 所 以是不存在环的 输出格式 输出一行一个数 表示上帝给这棵树的分数 样例输入 5 1 2 3 4 5 4 2 3 1 1 2 2 5 样例输出 8 数据范围 对于 30 的数据 n 10 对于 100 的数据 0 n 10 5 每个节点的评分的绝对值不超过 10 6 资源约定 峰值内存消耗 256M CPU 消耗 3ms 请严格按要求输出 不要画蛇添足地打印类似 请您输入 的多余内容 所有代码放在同一个源文件中 调试通过后 拷贝提交该源码 注意 main 函数需要返回 0 注意 只使用 ANSI C ANSI C 标准 不要调用依赖于编译环境或操作系统的特殊函数 注意 所有依赖的函数必须明确地在源文件中 include 不能通过工程设置而省 略常用头文件 提交时 注意选择所期望的编译器类型 题解 没有系统的学过树和图 不知道什么方法 我精通的只有 floyd 所以考场上只想 去骗 30 的数据 n 最大就是 10 考场的时候我直接穷举了点集的所有子集 最多就是 1024 种情况 判断是否连通 连通的话算出来 可惜时间不够差了一点 所以拿了 0 分 考场程序 详解 二进制法子集生成穷举 给定 n 用二进制法做出集合 0 1 2 n 1 的 2n 1 个非空子集 然后去判断每个子集是否 是连通树的一部分 权值再求和即可 1 define DEBUG 2 include 3 include 4 include 5 using namespace std 6 7 const int maxn 105 8 int n 9 int ver maxn 10 bool arc maxn maxn 11 vector vv 12 long long ans 1007 13 14 void subset int s 15 16 vv clear 17 for int i 0 i n i 18 19 if s 20 21 22 int len vv size t 0 23 for int i 0 i len i 24 25 for int j 0 j len j 26 27 if arc vv i vv j t 28 29 30 if t 2 len 1 return 31 32 long long sum 0 33 for int i 0 i ans ans sum 35 36 37 int main 38 39 ifdef DEBUG 40 pragma warning disable 4996 41 freopen d input txt r stdin 42 freopen d output txt w stdout 43 endif 44 memset ver 0 sizeof ver 45 memset arc 0 sizeof arc 46 cin n 47 for int i 0 i ver i 50 51 for int i 0 i temp1 temp2 55 arc temp1 1 temp2 1 true 56 arc temp2 1 temp1 1 true 57 58 for int i 1 i 1 n i 59 60 subset i 61 62 cout ans endl 63 return 0 64 考场程序 n 只要 20 出头就爆炸了 只能拿 30 多的分数 AC 版本 二叉链表 树形 dp 详解 题目给出的树是邻接表的构造法 这里用二叉链表表示二叉树 因此需要用 dfs 求 出这棵树的扩展前序遍历来构造树 树建立完成后 用经典的树形 dp 求出答案即可 1 define DEBUG 2 include 3 include 4 include 5 using namespace std 6 7 const int maxn 105 8 vector preorder 9 int pre 0 10 int value maxn 11 vector arc maxn 12 13 void build 14 15 int num 16 cin num 17 for int i 0 i value i 20 21 int temp1 temp2 22 for int i 1 i temp1 temp2 25 arc temp1 push back temp2 26 arc temp2 push back temp1 27 28 29 30 void dfs preorder int root int last 31 32 preorder push back root 33 int len arc root size 34 for int i 0 i len i 35 36 if arc root i last continue 37 dfs preorder arc root i root 38 39 if root last len 40 for int i len i left creat bt left 62 bt right creat bt right 63 64 return bt 65 66 67 递归求一个结点到另一个结点的路径上的最大和 68 class Solution 69 70 public 71 long long tmp 72 int maxPathSum TreeNode root 73 如果没有子树则最大值就是自己 74 if root NULL 75 结点空返回 76 return 0 77 78 tmp root val tmp 存放结点路径数值 79 MaxSubTree root 递归 80 return tmp 81 82 83 int MaxSubTree TreeNode subtree 84 求解子树 85 long long root subtree val 递归时将根结点放在子树 的第一个结点上 86 long long left 0 right 0 左右两个递归子树的 sum 均初 始为 0 87 if subtree left NULL 88 当结点不为空时 89 left MaxSubTree subtree left 继续递归 90 tmp tmp left tmp left 91 92 if subtree right NULL 93 同上 94 right MaxSubTree subtree right 95 tmp tmp right tmp right 96 97 long long Lsum root left 递归至空时 将左子树和 结点相加作为左边总和 98 long long Rsum root right 右边总和 99 long long SUM root left right 总和 100 long long MaxTmp max max max Lsum Rsum SUM root 考虑负 数的情况 101 tmp max tmp MaxTmp 102 return MaxTmp 103 104 105 10